3 ms·

Compiler optimizations are one of the primary culprits in making it difficult to reason about lock-free programs. Semantics-preserving optimizations in a single

Compiler optimizations are one of the primary culprits in making it difficult to reason about lock-free programs. Semantics-preserving optimizations in a single-threaded context are not necessarily semantics-preserving in a multi-threaded, lock-free context. For example, if you're writing a spin-lock, the compiler may lift a read of the lock value out of a loop because, assuming a single thread, the value will never change. This can result in a non-terminating spin-lock. For more see Linux's ACCESS_ONCE. The example you gave is unfortunate but the consequences of optimizing loops carelessly can be serious.

colanderman 8y ago
Isn't this the purpose of well-defined atomic primitives? After all, not just the compiler, but also the processor can reorder operations. So you have to annotate synchronizing memory operations regardless of whether the compiler is optimizing. e.g., a lock-free algorithm implemented using only volatile (what ACCESS_ONCE does), even with -O0, is almost certainly wrong. The alternative to explicit annotation is for the compiler to generate full memory barriers around every memory access. That would indeed preserve semantics in a multithreaded context, at a ridiculous performance cost.
- johnbender 8y ago
  > well-defined atomic primitives The example I gave is simple and relates to the example of the parent but there are more complex cases for which it is a matter of ongoing research to define a semantics that also admits compiler optimizations. For example the "well-defined" semantics of (C|C++)11's atomics admits executions where values can materialize out of thin air [1]. The broader point I was hoping to make is that optimizations are great but are not free in a multi-threaded context with data-races (even benign ones). As a consequence the choice to just remove many of them is one that is supported by many people in the weak-memory community and even appears in newer memory models [2]. For example preventing read-write reorderings to prevent causal cycles. [1] https://www.cl.cam.ac.uk/~pes20/cpp/notes42.html https://www.cl.cam.ac.uk/~pes20/cpp/notes42.html [2] http://gee.cs.oswego.edu/dl/html/j9mm.html http://gee.cs.oswego.edu/dl/html/j9mm.html (ruling out po U rf cycles)
wbl 8y ago
So use a language with proper semantics, like later C versions. Why would you ever expect the compiler to honor a contract that was never written?
- johnbender 8y ago
  See my comment to sibling [1]. In the case of C and the JMM, "proper semantics" is not. [1] https://news.ycombinator.com/item?id=18312101 https://news.ycombinator.com/item?id=18312101

colanderman 8y ago

Isn't this the purpose of well-defined atomic primitives? After all, not just the compiler, but also the processor can reorder operations. So you have to annotate synchronizing memory operations regardless of whether the compiler is optimizing. e.g., a lock-free algorithm implemented using only volatile (what ACCESS_ONCE does), even with -O0, is almost certainly wrong. The alternative to explicit annotation is for the compiler to generate full memory barriers around every memory access. That would indeed preserve semantics in a multithreaded context, at a ridiculous performance cost.

johnbender 8y ago
> well-defined atomic primitives The example I gave is simple and relates to the example of the parent but there are more complex cases for which it is a matter of ongoing research to define a semantics that also admits compiler optimizations. For example the "well-defined" semantics of (C|C++)11's atomics admits executions where values can materialize out of thin air [1]. The broader point I was hoping to make is that optimizations are great but are not free in a multi-threaded context with data-races (even benign ones). As a consequence the choice to just remove many of them is one that is supported by many people in the weak-memory community and even appears in newer memory models [2]. For example preventing read-write reorderings to prevent causal cycles. [1] https://www.cl.cam.ac.uk/~pes20/cpp/notes42.html https://www.cl.cam.ac.uk/~pes20/cpp/notes42.html [2] http://gee.cs.oswego.edu/dl/html/j9mm.html http://gee.cs.oswego.edu/dl/html/j9mm.html (ruling out po U rf cycles)

wbl 8y ago

So use a language with proper semantics, like later C versions. Why would you ever expect the compiler to honor a contract that was never written?

johnbender 8y ago
See my comment to sibling [1]. In the case of C and the JMM, "proper semantics" is not. [1] https://news.ycombinator.com/item?id=18312101 https://news.ycombinator.com/item?id=18312101