4 ms·

Why aren't undefined bytes like these treated in the same way as I/O data? That is, arbitrary but fixed data? This seems to align fairly well with how I think a

Why aren't undefined bytes like these treated in the same way as I/O data? That is, arbitrary but fixed data? This seems to align fairly well with how I think about uninitialized data.

YawningAngel 7y ago
Because it's faster not to do that and these compilers don't attempt to behave in safe or predictable ways when UB is invoked.
- martinhath 7y ago
  Of course it's faster - any program can be compiled into something "faster" by making the entire thing do nothing. What I mean is, why isn't uninitialized memory properly defined to be an arbitrary fixed string of bytes? In the example of the post, the compiler would look into `always_returns_true`, and either say "okay, is `x < 150`: well, I have no idea what `x` is, so I can't tell for sure", OR "Ah, for any value of `x` this expression is true, so let's replace it with `true`". There would be no 257th value of "uninitialized"; the value of `x` would definitely be a single value in the allowed range of that type, but it's indeterminable.
  - cesarb 7y ago
    It's like you suggested in your parent comment: uninitialized memory is similar to I/O data, which can change at any moment without warning. That is, it can be 200 at the "x < 150" and moments later 100 at the "x > 120". > In the example of the post, the compiler would look into `always_returns_true` You can't look at each function in isolation. One important optimization all modern compilers use is inlining: short functions (like this `always_returns_true`) or functions that are only used once (like this `always_returns_true`) have their body inserted directly into the caller function, which allows further optimizations like constant propagation.
    - martinhath 7y ago
      Ah, I knew my analogy would bite me :) I didn't mean IO as in "can change at any moment", but as in "read from a file but you have no idea what it is". You definitely _can_ look at each function in isolation (in this example it's even sufficient to get the "best" possible version of that function"), but I do know that you'd usually do an inline pass, and further optimization passes afterwards. I don't see how that changes anything, though. If the function was inlined you'd get the same expression, and still you'd be unable to tell anything about `x`, except that it would have a definite value that you cannot observe. Again, you could argue that no matter the value, the expression would be `true`, so you could replace it.
  - comex 7y ago
    To be clear, the compiler is not forbidden from optimizing `always_returns_true` to unconditionally return true. After all, undefined behavior can cause anything to happen, and that includes returning true. Normally LLVM would perform exactly that optimization. But in this case `always_returns_true` is inlined first, so it becomes something like `undef < 150 || undef > 120`; LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false. But `always_returns_true` is not an example of how this particular undefined behavior can be useful as an optimization, merely an example of how it can be dangerous. For some examples of how it can be useful: - Document describing the origins of `undef` in LLVM: http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value", especially when the code has been transformed to SSA form. - Some architectures literally have a 257th possible value, like Itanium [1] [2]. On Itanium, every register can be set to "Not a Thing", i.e. uninitialized, and the CPU will trap if you try to store such a value to memory. Ironically, NaT was created in order to make the CPU's behavior more defined in a certain case, or at least more predictable... argh, I'm too tired to explain it properly; look at section 2.3.1 of [2] for a somewhat confusing explanation. [1] https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41003 https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41... [2] https://www.cse.unsw.edu.au/~cs9244/06/seminars/07-gaol.pdf https://www.cse.unsw.edu.au/~cs9244/06/seminars/07-gaol.pdf
    - martinhath 7y ago
      I _think_ I understand the rationale behind `undef` in LLVM, but I still think it's a bad one, since it can, and does, lead to very surprising behaviour. > LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false. I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is. > Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value" This feels really contrived; in what setting would this actually be useful?
lmm 7y ago
If you're asking why the C standard didn't originally define it that way, it's because some architectures might use a trap/invalid representation (that traps when accessed) and we want compilers to be free to reorder memory accesses.
- martinhath 7y ago
  I think I'm mostly asking why this isn't a good solution for Rust, as I think C and C++'s design decisions should be absolutely irrelevant for it's development. However, since rustc uses LLVM, this seems to be difficult :( I suppose it could be enlightening to understand why it wasn't a good decision for C or C++ at the time either. > some architectures might use a trap/invalid representation Traps on what? Access of an invalid representation? What if such representations doesn't exist?
  - lmm 7y ago
    > Traps on what? Access of an invalid representation? Yeah - certain bit-patterns are just "invalid" rather than representing any given value. It's much nicer to debug, because you get an immediate failure (at the point where your code tries to access the uninitialized variable) rather than having a corrupt value propagate through your program. > What if such representations doesn't exist? Then you can't implement that strategy (other than by emulating it with considerable overhead, e.g. by having an extra marker byte for each variable in your program and checking it on every access). Hence why the C standard doesn't require you to do this. As originally intended, C left the behaviour undefined so that users on platforms that did have trap representations would be able to take advantage of them. (It's very hard to rigorously specify what accessing a trap representation should do without impeding the compiler's ability to reorder memory accesses). Unfortunately it's ended up being used to do the opposite by modern compilers - not only do they not trap on access to uninitialized values, they abuse the undefined behaviour rules to propagate unexpected behaviour even further from the code that caused it.
    - Faark 7y ago
      But then this should be documented in the types definition. I don't see this "can also be something else than 0-255" in the in the types documentation (that is arguably not at all detailed). We use types to restrain complexity. It was a mistake in C# to allow every object to be null. A better type system would allow devs to make a contract to easily disallow this and they try to fix this. Now here we have a blog post that seems to be fine with a function parameter of type u8 not actually being of 0-255. That's a huge change I always understood the type. Do I now have to do implement a null-check equivalent? Undefined behavior for unsafe code is fine. But there has to be a transition were we go back to classical behavior. And in the blog posts example, this should be somewhere in main. Certainly not the seemingly safe always_returns_true.

Why aren't undefined bytes like these treated in the same way as I/O data? That is, arbitrary but fixed data? This seems to align fairly well with how I think about uninitialized data.

YawningAngel 7y ago

Because it's faster not to do that and these compilers don't attempt to behave in safe or predictable ways when UB is invoked.

martinhath 7y ago
Of course it's faster - any program can be compiled into something "faster" by making the entire thing do nothing. What I mean is, why isn't uninitialized memory properly defined to be an arbitrary fixed string of bytes? In the example of the post, the compiler would look into `always_returns_true`, and either say "okay, is `x < 150`: well, I have no idea what `x` is, so I can't tell for sure", OR "Ah, for any value of `x` this expression is true, so let's replace it with `true`". There would be no 257th value of "uninitialized"; the value of `x` would definitely be a single value in the allowed range of that type, but it's indeterminable.
- cesarb 7y ago
  It's like you suggested in your parent comment: uninitialized memory is similar to I/O data, which can change at any moment without warning. That is, it can be 200 at the "x < 150" and moments later 100 at the "x > 120". > In the example of the post, the compiler would look into `always_returns_true` You can't look at each function in isolation. One important optimization all modern compilers use is inlining: short functions (like this `always_returns_true`) or functions that are only used once (like this `always_returns_true`) have their body inserted directly into the caller function, which allows further optimizations like constant propagation.
  - martinhath 7y ago
    Ah, I knew my analogy would bite me :) I didn't mean IO as in "can change at any moment", but as in "read from a file but you have no idea what it is". You definitely _can_ look at each function in isolation (in this example it's even sufficient to get the "best" possible version of that function"), but I do know that you'd usually do an inline pass, and further optimization passes afterwards. I don't see how that changes anything, though. If the function was inlined you'd get the same expression, and still you'd be unable to tell anything about `x`, except that it would have a definite value that you cannot observe. Again, you could argue that no matter the value, the expression would be `true`, so you could replace it.
- comex 7y ago
  To be clear, the compiler is not forbidden from optimizing `always_returns_true` to unconditionally return true. After all, undefined behavior can cause anything to happen, and that includes returning true. Normally LLVM would perform exactly that optimization. But in this case `always_returns_true` is inlined first, so it becomes something like `undef < 150 || undef > 120`; LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false. But `always_returns_true` is not an example of how this particular undefined behavior can be useful as an optimization, merely an example of how it can be dangerous. For some examples of how it can be useful: - Document describing the origins of `undef` in LLVM: http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value", especially when the code has been transformed to SSA form. - Some architectures literally have a 257th possible value, like Itanium [1] [2]. On Itanium, every register can be set to "Not a Thing", i.e. uninitialized, and the CPU will trap if you try to store such a value to memory. Ironically, NaT was created in order to make the CPU's behavior more defined in a certain case, or at least more predictable... argh, I'm too tired to explain it properly; look at section 2.3.1 of [2] for a somewhat confusing explanation. [1] https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41003 https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41... [2] https://www.cse.unsw.edu.au/~cs9244/06/seminars/07-gaol.pdf https://www.cse.unsw.edu.au/~cs9244/06/seminars/07-gaol.pdf
  - martinhath 7y ago
    I _think_ I understand the rationale behind `undef` in LLVM, but I still think it's a bad one, since it can, and does, lead to very surprising behaviour. > LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false. I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is. > Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value" This feels really contrived; in what setting would this actually be useful?

lmm 7y ago

If you're asking why the C standard didn't originally define it that way, it's because some architectures might use a trap/invalid representation (that traps when accessed) and we want compilers to be free to reorder memory accesses.

martinhath 7y ago
I think I'm mostly asking why this isn't a good solution for Rust, as I think C and C++'s design decisions should be absolutely irrelevant for it's development. However, since rustc uses LLVM, this seems to be difficult :( I suppose it could be enlightening to understand why it wasn't a good decision for C or C++ at the time either. > some architectures might use a trap/invalid representation Traps on what? Access of an invalid representation? What if such representations doesn't exist?
- lmm 7y ago
  > Traps on what? Access of an invalid representation? Yeah - certain bit-patterns are just "invalid" rather than representing any given value. It's much nicer to debug, because you get an immediate failure (at the point where your code tries to access the uninitialized variable) rather than having a corrupt value propagate through your program. > What if such representations doesn't exist? Then you can't implement that strategy (other than by emulating it with considerable overhead, e.g. by having an extra marker byte for each variable in your program and checking it on every access). Hence why the C standard doesn't require you to do this. As originally intended, C left the behaviour undefined so that users on platforms that did have trap representations would be able to take advantage of them. (It's very hard to rigorously specify what accessing a trap representation should do without impeding the compiler's ability to reorder memory accesses). Unfortunately it's ended up being used to do the opposite by modern compilers - not only do they not trap on access to uninitialized values, they abuse the undefined behaviour rules to propagate unexpected behaviour even further from the code that caused it.
  - Faark 7y ago
    But then this should be documented in the types definition. I don't see this "can also be something else than 0-255" in the in the types documentation (that is arguably not at all detailed). We use types to restrain complexity. It was a mistake in C# to allow every object to be null. A better type system would allow devs to make a contract to easily disallow this and they try to fix this. Now here we have a blog post that seems to be fine with a function parameter of type u8 not actually being of 0-255. That's a huge change I always understood the type. Do I now have to do implement a null-check equivalent? Undefined behavior for unsafe code is fine. But there has to be a transition were we go back to classical behavior. And in the blog posts example, this should be somewhere in main. Certainly not the seemingly safe always_returns_true.