X-Git-Url: https://git.ralfj.de/web.git/blobdiff_plain/f1e93146eae099784ef2a73000a04e579cf6f06f..929cce8205b2d5e3969a51654fe0db2212af3b26:/ralf/_posts/2019-07-14-uninit.md?ds=inline diff --git a/ralf/_posts/2019-07-14-uninit.md b/ralf/_posts/2019-07-14-uninit.md index 702ac47..b1c479a 100644 --- a/ralf/_posts/2019-07-14-uninit.md +++ b/ralf/_posts/2019-07-14-uninit.md @@ -54,7 +54,7 @@ However, if you [run the example](https://play.rust-lang.org/?version=stable&mod ## What *is* uninitialized memory? How is this possible? -The answer is that every byte in memory cannot just have a value in `0..256`, it can also be "uninitialized". +The answer is that every byte in memory cannot just have a value in `0..256` (this is Rust syntax for a left-inclusive right-exclusive range), it can also be "uninitialized". Memory *remembers* if you initialized it. The `x` that is passed to `always_return_true` is *not* the 8-bit representation of some number, it is an uninitialized byte. Performing operations such as comparison on uninitialized bytes is undefined behavior. @@ -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. +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.