more precise about what the HW does

[web.git] / personal / _posts / 2019-07-14-uninit.md

diff --git a/personal/_posts/2019-07-14-uninit.md b/personal/_posts/2019-07-14-uninit.md
index f454bfd30fad10fddfa12e9de1be9feb145ec9ac..72b26c76ab5207fec12d8d5c3bdfbdff5b4ff9e1 100644 (file)
--- a/personal/_posts/2019-07-14-uninit.md
+++ b/personal/_posts/2019-07-14-uninit.md
@@ -1,6 +1,7 @@
 ---
 title: '"What The Hardware Does" is not What Your Program Does: Uninitialized Memory'
 categories: rust
 ---
 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.
 ---
 
 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?
 ## 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.
 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.
 
 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
 
 ## "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).
 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.
 
 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.
 
 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
 #### Footnotes