4 ms·

Obviously Odin does not use C's memory model. And in instances where LLVM optimizes Odin for UB, it is a bug, and not a feature. Odin explicitly opts out of a

Obviously Odin does not use C's memory model. And in instances where LLVM optimizes Odin for UB, it is a bug, and not a feature. Odin explicitly opts out of all optimization passes that depend or leverage UB, but that's a moving target. For example, as mentioned in the article, Odin does not leverage LLVM's poison value optimizations, which are derived from optimizations exploiting undefined behavior. Sure, some code is slowed. But can you point to a well known and well used algorithm whose runtime characteristics depend upon exploiting UB? If you code goes fast because it's doing undefined things the compiler strips away, that's a structural bug in the application, in my view.

spacechild1 4y ago
> Obviously Odin does not use C's memory model. How is that obvious? And which memory model does Odin use? Just to be clear: a "memory model" is not about memory management, it is about the behaviour of multithreaded programs: https://en.m.wikipedia.org/wiki/Memory_model_(programming) https://en.m.wikipedia.org/wiki/Memory_model_(programming)
- jessermeyer 4y ago
  Thanks. I was thinking of strict-aliasing and the associated undefined behavior, which Odin forbids. Odin's atomic intrinsics model after C11 closely (and require the programmer to emit memory barriers when cache behavior must be controlled by instructions). I believe the final memory model will be platform defined. There is no built-in atomic data type in Odin. Only atomic operations are available, and most sync primitives are implemented in the standard library wrapping OS capabilities (WaitOnAddress), etc. The parent comment said: >then have a data race, it's functionally equivalent to undefined behavior This is a matter of interpretation but there is a categorical difference between "this read is undefined so the compiler will silently omit it" and "this read will read whatever value is in the CPU cache at this address, even if the cache is stale". The difference is a matter of undefined behavior from the language versus the application being in an undefined state.
  - spacechild1 4y ago
    > This is a matter of interpretation but there is a categorical difference between "this read is undefined so the compiler will silently omit it" and "this read will read whatever value is in the CPU cache at this address, even if the cache is stale". The difference is a matter of undefined behavior from the language versus the application being in an undefined state. I totally agree.
raphlinus 4y ago
I'll give a concrete example. It's not the most compelling optimization in the world, but I think illustrates the tradeoffs clearly. The following is pseudocode, not any particular language, but hopefully will be clear. let i = mystruct.i; if (i < array.length) { let x = expensive_computation(i); array[i] = x; } For the purpose of this example, let's say that the expensive computation is register-intensive but doesn't write any memory (so we don't need to get into alias analysis issues). Because it is register-intensive, our optimizer would like to free up the register occupied by i, replacing the second use of i by another load from mystruct.i. In C or unsafe Rust, this would be a perfectly fine optimization. If another thread writes struct.i concurrently, we have a time of check to time of use (TOCTOU) error. In C or unsafe Rust, that's accounted for by the fact that a data race is undefined behavior. One of the behaviors that's allowed (because basically all behavior are allowed) is for the two uses of i to differ, invalidating the bounds check. Different languages deal with this in different ways. Java succeeds in its goal of avoiding UB, disallowing this optimization; the mechanism for doing so in LLVM is to consider most memory accesses to have "unordered" semantics. However, this comes with its own steep tradeoff. To avoid tearing, all pointers must be "thin," specifically disallowing slices. Go, by contrast, has slices among its fat pointer types, so incurs UB when there's a data race. It's otherwise a fairly safe language, but this is one of the gaps in that promise. Basically, my argument is this. If you're really rigorous about avoiding UB, you essentially have to define a memory model, then make sure your use of LLVM (or whatever code generation technique) is actually consistent with that memory model. That's potentially an enormous amount of work, very easy to get subtly wrong, and at the end of the day gives you fewer optimization opportunities than C or unsafe Rust. Thus, it's certainly not a tradeoff I personally would make.
- jessermeyer 4y ago
  Thanks. Currently Odin would cache i on the stack for retrieval later, granting LLVM the ability to load it into a register if profitable with knowledge that after the read, `i` is constant, which bypasses the RAW hazard after the initial read. My view is that undefined behavior is a trash fire and serious effort should be undertaken to fix the situation before it gets even more out of hand.
- 4y ago
kristoff_it 4y ago
> If you code goes fast because it's doing undefined things the compiler strips away, that's a structural bug in the application, in my view. I think that's the inverse of what UB-based optimizations do. Those optimizations rely on you _never_ doing what is considered UB. That's what makes the optimization correct. The problem is that, in practice, what's usually considered UB is not something that the language can always statically ensure you're not doing, and so when you do make a mistake, you land in a situation where the optimization seems to make things worse, instead of protecting you.

spacechild1 4y ago

> Obviously Odin does not use C's memory model. How is that obvious? And which memory model does Odin use? Just to be clear: a "memory model" is not about memory management, it is about the behaviour of multithreaded programs: https://en.m.wikipedia.org/wiki/Memory_model_(programming) https://en.m.wikipedia.org/wiki/Memory_model_(programming)

jessermeyer 4y ago
Thanks. I was thinking of strict-aliasing and the associated undefined behavior, which Odin forbids. Odin's atomic intrinsics model after C11 closely (and require the programmer to emit memory barriers when cache behavior must be controlled by instructions). I believe the final memory model will be platform defined. There is no built-in atomic data type in Odin. Only atomic operations are available, and most sync primitives are implemented in the standard library wrapping OS capabilities (WaitOnAddress), etc. The parent comment said: >then have a data race, it's functionally equivalent to undefined behavior This is a matter of interpretation but there is a categorical difference between "this read is undefined so the compiler will silently omit it" and "this read will read whatever value is in the CPU cache at this address, even if the cache is stale". The difference is a matter of undefined behavior from the language versus the application being in an undefined state.
- spacechild1 4y ago
  > This is a matter of interpretation but there is a categorical difference between "this read is undefined so the compiler will silently omit it" and "this read will read whatever value is in the CPU cache at this address, even if the cache is stale". The difference is a matter of undefined behavior from the language versus the application being in an undefined state. I totally agree.

raphlinus 4y ago

I'll give a concrete example. It's not the most compelling optimization in the world, but I think illustrates the tradeoffs clearly. The following is pseudocode, not any particular language, but hopefully will be clear. let i = mystruct.i; if (i < array.length) { let x = expensive_computation(i); array[i] = x; } For the purpose of this example, let's say that the expensive computation is register-intensive but doesn't write any memory (so we don't need to get into alias analysis issues). Because it is register-intensive, our optimizer would like to free up the register occupied by i, replacing the second use of i by another load from mystruct.i. In C or unsafe Rust, this would be a perfectly fine optimization. If another thread writes struct.i concurrently, we have a time of check to time of use (TOCTOU) error. In C or unsafe Rust, that's accounted for by the fact that a data race is undefined behavior. One of the behaviors that's allowed (because basically all behavior are allowed) is for the two uses of i to differ, invalidating the bounds check. Different languages deal with this in different ways. Java succeeds in its goal of avoiding UB, disallowing this optimization; the mechanism for doing so in LLVM is to consider most memory accesses to have "unordered" semantics. However, this comes with its own steep tradeoff. To avoid tearing, all pointers must be "thin," specifically disallowing slices. Go, by contrast, has slices among its fat pointer types, so incurs UB when there's a data race. It's otherwise a fairly safe language, but this is one of the gaps in that promise. Basically, my argument is this. If you're really rigorous about avoiding UB, you essentially have to define a memory model, then make sure your use of LLVM (or whatever code generation technique) is actually consistent with that memory model. That's potentially an enormous amount of work, very easy to get subtly wrong, and at the end of the day gives you fewer optimization opportunities than C or unsafe Rust. Thus, it's certainly not a tradeoff I personally would make.

jessermeyer 4y ago
Thanks. Currently Odin would cache i on the stack for retrieval later, granting LLVM the ability to load it into a register if profitable with knowledge that after the read, `i` is constant, which bypasses the RAW hazard after the initial read. My view is that undefined behavior is a trash fire and serious effort should be undertaken to fix the situation before it gets even more out of hand.
4y ago

kristoff_it 4y ago

> If you code goes fast because it's doing undefined things the compiler strips away, that's a structural bug in the application, in my view. I think that's the inverse of what UB-based optimizations do. Those optimizations rely on you _never_ doing what is considered UB. That's what makes the optimization correct. The problem is that, in practice, what's usually considered UB is not something that the language can always statically ensure you're not doing, and so when you do make a mistake, you land in a situation where the optimization seems to make things worse, instead of protecting you.