more precise about what the HW does
[web.git] / personal / _posts / 2019-07-14-uninit.md
index f454bfd30fad10fddfa12e9de1be9feb145ec9ac..72b26c76ab5207fec12d8d5c3bdfbdff5b4ff9e1 100644 (file)
@@ -1,6 +1,7 @@
 ---
 title: '"What The Hardware Does" is not What Your Program Does: Uninitialized Memory'
 categories: rust
+forum: https://internals.rust-lang.org/t/what-the-hardware-does-is-not-what-your-program-does-uninitialized-memory/10561
 ---
 
 This post is about uninitialized memory, but also about the semantics of highly optimized "low-level" languages in general.
@@ -53,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/Ruby 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.
@@ -90,14 +91,24 @@ 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.
+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, unless you *already established that there is no undefined behavior*.
 Sure, hardware (well, [most hardware](https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41003)) does not have a notion of "uninitialized memory".
 But *the Rust program you wrote does not run on your hardware*.
 It runs on the Rust abstract machine, and that machine (which only exists in our minds) *does* have a notion of "uninitialized memory".
 The real, physical hardware that we end up running the compiled program on is a very efficient *but imprecise* implementation of this abstract machine, and all the rules that Rust has for undefined behavior work together to make sure that this imprecision is not visible for *well-behaved* (UB-free) programs.
 But for programs that do have UB, this "illusion" breaks down, and [anything is possible](https://raphlinus.github.io/programming/rust/2018/08/17/undefined-behavior.html).
+UB-free programs can be made sense of by looking at their assembly, but *whether* a program has UB is impossible to tell on that level.
+For that, you need to think in terms of the abstract machine.
 
 This does not just apply to uninitialized memory: for example, in x86 assembly, there is no difference between "relaxed" and "release"/"acquire"-style atomic memory accesses.
 But when writing Rust programs, even when writing Rust programs that you only intend to compile to x86, "what the hardware does" just does not matter.
@@ -113,4 +124,6 @@ I hope C/C++ will come around to do the same, and there is some [great work in t
 If you want to do me a favor, please spread the word!
 I am trying hard to combat the myth of "what the hardware does" in Rust discussions whenever I see it, but I obviously don't see all the discussions---so the next time you see such an argument, no matter whether it is about uninitialized memory or [concurrency](http://hboehm.info/boehm-hotpar11.pdf) or [out-of-bounds memory accesses](https://github.com/rust-lang/rust/issues/32976#issuecomment-446775360) or anything else, please help by steering the discussion towards "what the Rust abstract machine does", and how we can design and adjust the Rust abstract machine in a way that it is most useful for programmers and optimizing compilers alike.
 
+As usual, if you have any comments, suggestions or questions, [let me know in the forums](https://internals.rust-lang.org/t/what-the-hardware-does-is-not-what-your-program-does-uninitialized-memory/10561).
+
 #### Footnotes