mention the sparse uninit vec trick

diff --git a/ralf/_posts/2019-07-14-uninit.md b/ralf/_posts/2019-07-14-uninit.md
index d3fb0fe41cfa9f69261497a47a2429258ffa12ca..b1c479ab9a4a5c66049c12ec9d07bad2180bb033 100644 (file)
--- a/ralf/_posts/2019-07-14-uninit.md
+++ b/ralf/_posts/2019-07-14-uninit.md
@@ -91,6 +91,14 @@ Over time, we will come to some kind of compromise here.
 The important part (for both Rust and C/C++) however is that we have this discussion with a clear mental model in our minds for *what uninitialized memory is*.
 I see Rust on a good path here; I hope the C/C++ committees will eventually follow suit.
 
 The important part (for both Rust and C/C++) however is that we have this discussion with a clear mental model in our minds for *what uninitialized memory is*.
 I see Rust on a good path here; I hope the C/C++ committees will eventually follow suit.
 

+Ruling out any operation on uninitialized values also makes it impossible to implement [this cute data structure](https://research.swtch.com/sparse).
+The `is-member` function there relies on the assumption that "observing" an uninitialized value (`sparse[i]`) twice gives the same result, which as we have seen above is not the case.
+This could be fixed by providing a "freeze" operation that, given any data, replaces the uninitialized bytes by *some* non-deterministically chosen *initialized* bytes.
+It is called "freeze" because its effect is that the value "stops changing each time you observe it".
+`is-member` would freeze `sparse[i]` once and then know for sure that "looking at it" twice will give consistent results.
+Unfortunately, since C/C++ do not acknowledge that their memory model is what it is, we do not have crucial operations such as "freeze" officially supported in compilers.
+At least for LLVM, that [might change though](http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf).
+

 ## "What the hardware does" considered harmful
 
 Maybe the most important lesson to take away from this post is that "what the hardware does" is most of the time *irrelevant* when discussing what a Rust/C/C++ program does.
 ## "What the hardware does" considered harmful
 
 Maybe the most important lesson to take away from this post is that "what the hardware does" is most of the time *irrelevant* when discussing what a Rust/C/C++ program does.