4 ms·

A Proposal Fix for C/C++ Relaxed Atomics in Practice

39 points by signa11 3y ago

deadbeeves 3y ago
I don't really get it. Why is { P0:r0 = 1; P1:r0 = 1 } not an allowed final state? What code code could the compiler generate that would definitely prevent the threads from interleaving their loads and stores on any given architecture?
- xKingfisher 3y ago
  I think it's just a very confusing, hard to use correctly behavior. And according to the article, very bug prone in implementations. In the example given, the result is that both writes happened before both reads, which directly contradicts the source. There's a valid explanation for why it happens, but it's still paradoxical. I remember at work a C++ standards committee member was giving examples of atomic and how to use them safely with different memory models, when someone pointed out his toy example for relaxed order was wrong. It took 5 people debating for a week to figure out what a safe/correct behavior would be. For a 10 line sample class. As times your second question, the article recommends Hans Boehm's proposal to add a no-op conditional branch after the read. I guess it forces the load to be resolved and enforces a sequenced-before behavior on the individual threads. So at least one read must resolve before one write in the example.
  - twoodfin 3y ago
    Yes, relaxed memory semantics are exceedingly difficult to reason about. Hard to believe this is news to the C++ standards committee. I find the premise of this article confusing, and assume it must be because I’m missing something crucial—obviously Hans Boehm knows what he’s talking about. Why do (opt in!) relaxed semantics need to be fixed?
    - dataflow 3y ago
      > relaxed memory semantics are exceedingly difficult to reason about People say this but I don't understand how? They're basically just like ordinary variables. Except even better, because you can use them from multiple threads. And it's guaranteed that a given thread will only ever see values that were actually written by the program (like it's guaranteed the compiler won't introduce spurious writes during optimization). There's no ordering guarantee, just like there's no ordering guarantee across threads for ordinary variables. If relaxed atomics are too hard then aren't ordinary variables too hard? You can certainly use them in a way that's confusing, but that's not because they're themselves complicated - it's because you're writing confusing code. You can do that in a single thread too, with ordinary variables. It's not specific to relaxed atomics. In fact, in my experience, the most confusing atomics are the sequentially consistent ones! I never know when I need to use them in practice vs. acquire/release.
      - twoodfin 3y ago
        There's no ordering guarantee, just like there's no ordering guarantee across threads for ordinary variables. This is what makes them hard to reason about. C++ makes “as if” ordering guarantees within a single thread trivial: If you can observe things happening out of the order in which your defined-behavior code sequenced them, you have a bug in your compiler or your CPU. Relaxed ordering (on purpose) throws out all implicit sequencing guarantees when threads observe each other. My confusion is that I believed this was all well-understood by implementers and programmers decades ago. That relaxed is harder than sequential to get right was as true on the Alpha as it is on modern ARMs. But this article seems to suggest what should be obvious consequences of relaxed semantics are unexpected & undesirable for C++!
        dataflow 3y ago
        > This is what makes them hard to reason about. [...] I think we're speaking past each other. You're implicitly assuming there is some piece of code using atomics, and you're saying it's harder to reason about its behavior when the atomics are made to be relaxed (versus, say, sequentially consistent). That's true enough, but it misses my point. I'm coming at this from the opposite direction: I have certain kinds of atomics available, and then I'm using them to write the code. In such a scenario, it's quite easy to distinguish between "I might care about ordering" vs. "I don't care about ordering". In the first case, you probably shouldn't use relaxed atomics - good luck figuring out what to use, it may very well be tricky. If you insist on using relaxed atomics for those, it will definitely be tricky to get it right if it's at all possible, but that's when you should avoid relaxed atomics if at all possible. In the latter case, you should use relaxed atomics, and it's not tricky because you already know ordering doesn't matter. Example: relaxed atomics are trivial to reason about in single-writer situations that aren't signaling any kind of event. Like when a worker is just trying to report progress to the foreground UI with minimal overhead. In this example, the writer (which is on a background thread) simply loads its progress indicator, adds 1, then stores back the variable. There isn't even a need for an atomic RMW, let alone any ordering. The worst case is the user will see "100% done" a few milliseconds too early, which is a non-issue (and already bound to happen due to rounding etc. anyway). Using relaxed atomics doesn't introduce any complexity in such a situation; it's basically exactly what you'd expect from ordinary variables without write-tearing. You run into problems if you try to depend on the "100% progress" indicator to mean "everything is finished" (so you can, say, clean up data structures), but at that point you clearly need ordering and shouldn't use a relaxed atomic to begin with; you'd want release semantics (or stronger), and those are trickier. > My confusion is that I believed this was all well-understood by implementers and programmers decades ago. I definitely agree with this part. I didn't think in 2023 I would read that programmers are shocked that relaxed atomics can be reordered. That's... their entire point. It's like being shocked that compilers propagate constants during optimization.
- dataflow 3y ago
  Yeah I don't understand it either. There's no dependency between the load and store, so there's no inherent ordering. The entire point of relaxed atomics is to let you reorder them freely - otherwise, why aren't you using acquire/release or such?
  - gpderetta 3y ago
    My understanding is that actual hardware is stronger than C++11 relaxed atomic, but weaker than the revised memory model. The revised memory model closes some theoretical holes in C++11 (for example out-of-thin-air values that don't happen on actual hardware) so it is desirable for some people especially those trying to prove the correctness of compiler transformations, while others do not want to add additional overhead unless necessary. The question is whether there are programs and optimizations that care.
mgaunard 3y ago
Even the name of their compiler flag already is an oxymoron. Relaxed atomics are not ordered. If you want some ordering guarantees that are weaker than acquire or consume just add a new word for it.
- ajross 3y ago
  Or just don't. Lockless algorithms are hard enough with explicit and clear barrier operations. The idea that somehow empowering optimizers to further confuse things is a feature and not a bug is just completely bewildering to me. Leave the clever optimization to the sequential code and leave the lockless work explicit. Please.
raphlinus 3y ago
I'm not sure how I feel about this. Are there nontrivial programs that depend on the (1, 1) outcome of the LB litmus test being forbidden? (See section 2.3 of the Lahav paper[1] for definitions and context) If so, then these programs are at significant risk of miscompilation on compilers today. Strengthening the standard would mean that this risk continues until compilers are updated. If not, then the proposal is asking for an (admittedly modest) performance regression to address what might not be a real problem. Rust doesn't have a formal memory model yet, but the loom tool reports the (1, 1) outcome as not allowed[2]. I also ran it as normal threaded Rust code (not using a model checker) on M1 Max (which in theory is subject to the same miscompilation), and was not able to reproduce the failures as reported in the linked paper[3], but that doesn't mean much, as it's notoriously tricky to observe memory model violations. In GPU-land, the (1, 1) outcome is allowed, as can be verified in the Vulkan memory model by the Alloy test in the second file of [2]. Neither HLSL nor Metal Shading Language have proper memory models, so it's hard to say, but in general it's fair to expect that anything allowed by the Vulkan memory model can be observed in other GPU implementations. Perhaps what is called for is a finer gradation of strength, where the author explicitly asks for the guarantees needed, and the compiler inserts the BAL when it's needed, and skips it if not. Already I can see a lot of value in an explicit "unordered" value for ordering, which would be even weaker than relaxed (allowing more compiler optimization). [1]: https://plv.mpi-sws.org/scfix/paper.pdf https://plv.mpi-sws.org/scfix/paper.pdf [2]: https://gist.github.com/raphlinus/41d78d04d117ab0ba3b77065b9927966 https://gist.github.com/raphlinus/41d78d04d117ab0ba3b77065b9... [3]: https://arxiv.org/pdf/2310.12337.pdf https://arxiv.org/pdf/2310.12337.pdf
- deleted 3y ago
  [deleted]
rnrn 3y ago
Response from arm: https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/arm-technical-view-on-relaxed-atomics https://community.arm.com/arm-community-blogs/b/architecture... > The characterization in the post of there being "thousands of bug instances related to relaxed atomics accesses" on Arm systems is unfounded – the comparison is not against the C23 specification, but against an, as yet unadopted, proposed tightening of the specification (specifically Section 2.3 as it is understood that this paper otherwise proposes changes which have been ratified) IMO the “out of thin air” problem is a purely academic limitation of the models and matters not much in reality (since an implementation that generates values out of thin air would be a bit insane - no such hardware exists and no such compiler should either) and therefore it does not make sense to add ordering requirements on relaxed atomics to fix what is a non-issue in practice.
- raphlinus 3y ago
  Thanks for this, quite useful. There's also more discussion in [1], linked from there, which contains perspective from real memory model experts. I think it's fair to say they're skeptical of the proposal. In particular, they've debunked the SC-DRF claim, which seemed fishy to me, but I didn't want to say anything before gathering more evidence. [1]: https://discourse.llvm.org/t/rfc-strengthen-relaxed-atomics-implementation-behind-mstrict-rlx-atomics-flag/74473 https://discourse.llvm.org/t/rfc-strengthen-relaxed-atomics-...
- dataflow 3y ago
  > IMO the “out of thin air” problem is a purely academic limitation This article is not about the out of thin air problem, is it? I think you're thinking of something else?
  - rnrn 3y ago
    The motivation for the branch after load proposal and the addition of ordering constraints on relaxed atomic discussed in the article is the out of thin air problem See Boehm’s original 2013 proposal (linked in the article) for details
  - 3y ago
JonChesterfield 3y ago
Relaxed atomics are not broken. They are not hard to reason about. This proposed "fix" is misguided and reflects a fundamental error made by C++ when defining their memory model. The most informative paper on the subject is probably "improved support for bidirectional fences", https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2633.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n26.... There are _two_ different atomic memory models in flight in C++. Relaxed atomic operations are perfect for one and something of a nonsense for the other. One model involves controlling the order of atomic operations within a thread of execution using memory fences. The fences amount to limiting reordering in store buffers or invalidation queues. This is what we had before the C++ memory model, though the operations were called "volatile" then. It's what the hardware ISAs expose, with varying details on cost of different types of fence. This is where relaxed atomic operations are the right thing. The threads do not "synchronise with" one another. The second model involves atomic variables that synchronise with one another in different threads. Mechanism unspecified. As far as I can tell this is largely an invention of the C++ committee based on enthusiasm for methods on class instantiations. The paper linked above seems to be the point where this model accepted that it can't express everything it needs to. It's characterised by memory order annotations on methods on variables and wondering what the compiler is going to do with your code. The "synchronises with" model favoured by C++ can be mechanically translated to the "relaxed with fences" model that the hardware implements. The inverse is not true. One piece of the puzzle I don't have is _why_ this is the state of the art. Given a straightforward, existing model for describing concurrent programming on mutable state, somehow we've ended up with a much more complicated one pasted on top. Which leads to various costs, including this article.
- comex 3y ago
  "Relaxed with fences" is not always what the hardware implements. ARMv8 [1] provides straight-up load-acquire and store-release instructions, matching C++. [1] https://developer.arm.com/documentation/102336/0100/Load-Acquire-and-Store-Release-instructions https://developer.arm.com/documentation/102336/0100/Load-Acq...
  - gpderetta 3y ago

39 points by signa11 3y ago

I don't really get it. Why is { P0:r0 = 1; P1:r0 = 1 } not an allowed final state? What code code could the compiler generate that would definitely prevent the threads from interleaving their loads and stores on any given architecture?

xKingfisher 3y ago
I think it's just a very confusing, hard to use correctly behavior. And according to the article, very bug prone in implementations. In the example given, the result is that both writes happened before both reads, which directly contradicts the source. There's a valid explanation for why it happens, but it's still paradoxical. I remember at work a C++ standards committee member was giving examples of atomic and how to use them safely with different memory models, when someone pointed out his toy example for relaxed order was wrong. It took 5 people debating for a week to figure out what a safe/correct behavior would be. For a 10 line sample class. As times your second question, the article recommends Hans Boehm's proposal to add a no-op conditional branch after the read. I guess it forces the load to be resolved and enforces a sequenced-before behavior on the individual threads. So at least one read must resolve before one write in the example.
- twoodfin 3y ago
  Yes, relaxed memory semantics are exceedingly difficult to reason about. Hard to believe this is news to the C++ standards committee. I find the premise of this article confusing, and assume it must be because I’m missing something crucial—obviously Hans Boehm knows what he’s talking about. Why do (opt in!) relaxed semantics need to be fixed?
  - dataflow 3y ago
    > relaxed memory semantics are exceedingly difficult to reason about People say this but I don't understand how? They're basically just like ordinary variables. Except even better, because you can use them from multiple threads. And it's guaranteed that a given thread will only ever see values that were actually written by the program (like it's guaranteed the compiler won't introduce spurious writes during optimization). There's no ordering guarantee, just like there's no ordering guarantee across threads for ordinary variables. If relaxed atomics are too hard then aren't ordinary variables too hard? You can certainly use them in a way that's confusing, but that's not because they're themselves complicated - it's because you're writing confusing code. You can do that in a single thread too, with ordinary variables. It's not specific to relaxed atomics. In fact, in my experience, the most confusing atomics are the sequentially consistent ones! I never know when I need to use them in practice vs. acquire/release.
    - twoodfin 3y ago
      There's no ordering guarantee, just like there's no ordering guarantee across threads for ordinary variables. This is what makes them hard to reason about. C++ makes “as if” ordering guarantees within a single thread trivial: If you can observe things happening out of the order in which your defined-behavior code sequenced them, you have a bug in your compiler or your CPU. Relaxed ordering (on purpose) throws out all implicit sequencing guarantees when threads observe each other. My confusion is that I believed this was all well-understood by implementers and programmers decades ago. That relaxed is harder than sequential to get right was as true on the Alpha as it is on modern ARMs. But this article seems to suggest what should be obvious consequences of relaxed semantics are unexpected & undesirable for C++!
      - dataflow 3y ago
        > This is what makes them hard to reason about. [...] I think we're speaking past each other. You're implicitly assuming there is some piece of code using atomics, and you're saying it's harder to reason about its behavior when the atomics are made to be relaxed (versus, say, sequentially consistent). That's true enough, but it misses my point. I'm coming at this from the opposite direction: I have certain kinds of atomics available, and then I'm using them to write the code. In such a scenario, it's quite easy to distinguish between "I might care about ordering" vs. "I don't care about ordering". In the first case, you probably shouldn't use relaxed atomics - good luck figuring out what to use, it may very well be tricky. If you insist on using relaxed atomics for those, it will definitely be tricky to get it right if it's at all possible, but that's when you should avoid relaxed atomics if at all possible. In the latter case, you should use relaxed atomics, and it's not tricky because you already know ordering doesn't matter. Example: relaxed atomics are trivial to reason about in single-writer situations that aren't signaling any kind of event. Like when a worker is just trying to report progress to the foreground UI with minimal overhead. In this example, the writer (which is on a background thread) simply loads its progress indicator, adds 1, then stores back the variable. There isn't even a need for an atomic RMW, let alone any ordering. The worst case is the user will see "100% done" a few milliseconds too early, which is a non-issue (and already bound to happen due to rounding etc. anyway). Using relaxed atomics doesn't introduce any complexity in such a situation; it's basically exactly what you'd expect from ordinary variables without write-tearing. You run into problems if you try to depend on the "100% progress" indicator to mean "everything is finished" (so you can, say, clean up data structures), but at that point you clearly need ordering and shouldn't use a relaxed atomic to begin with; you'd want release semantics (or stronger), and those are trickier. > My confusion is that I believed this was all well-understood by implementers and programmers decades ago. I definitely agree with this part. I didn't think in 2023 I would read that programmers are shocked that relaxed atomics can be reordered. That's... their entire point. It's like being shocked that compilers propagate constants during optimization.
dataflow 3y ago
Yeah I don't understand it either. There's no dependency between the load and store, so there's no inherent ordering. The entire point of relaxed atomics is to let you reorder them freely - otherwise, why aren't you using acquire/release or such?
- gpderetta 3y ago
  My understanding is that actual hardware is stronger than C++11 relaxed atomic, but weaker than the revised memory model. The revised memory model closes some theoretical holes in C++11 (for example out-of-thin-air values that don't happen on actual hardware) so it is desirable for some people especially those trying to prove the correctness of compiler transformations, while others do not want to add additional overhead unless necessary. The question is whether there are programs and optimizations that care.

mgaunard 3y ago

Even the name of their compiler flag already is an oxymoron. Relaxed atomics are not ordered. If you want some ordering guarantees that are weaker than acquire or consume just add a new word for it.

ajross 3y ago
Or just don't. Lockless algorithms are hard enough with explicit and clear barrier operations. The idea that somehow empowering optimizers to further confuse things is a feature and not a bug is just completely bewildering to me. Leave the clever optimization to the sequential code and leave the lockless work explicit. Please.

raphlinus 3y ago

I'm not sure how I feel about this. Are there nontrivial programs that depend on the (1, 1) outcome of the LB litmus test being forbidden? (See section 2.3 of the Lahav paper[1] for definitions and context) If so, then these programs are at significant risk of miscompilation on compilers today. Strengthening the standard would mean that this risk continues until compilers are updated. If not, then the proposal is asking for an (admittedly modest) performance regression to address what might not be a real problem. Rust doesn't have a formal memory model yet, but the loom tool reports the (1, 1) outcome as not allowed[2]. I also ran it as normal threaded Rust code (not using a model checker) on M1 Max (which in theory is subject to the same miscompilation), and was not able to reproduce the failures as reported in the linked paper[3], but that doesn't mean much, as it's notoriously tricky to observe memory model violations. In GPU-land, the (1, 1) outcome is allowed, as can be verified in the Vulkan memory model by the Alloy test in the second file of [2]. Neither HLSL nor Metal Shading Language have proper memory models, so it's hard to say, but in general it's fair to expect that anything allowed by the Vulkan memory model can be observed in other GPU implementations. Perhaps what is called for is a finer gradation of strength, where the author explicitly asks for the guarantees needed, and the compiler inserts the BAL when it's needed, and skips it if not. Already I can see a lot of value in an explicit "unordered" value for ordering, which would be even weaker than relaxed (allowing more compiler optimization). [1]: https://plv.mpi-sws.org/scfix/paper.pdf https://plv.mpi-sws.org/scfix/paper.pdf [2]: https://gist.github.com/raphlinus/41d78d04d117ab0ba3b77065b9927966 https://gist.github.com/raphlinus/41d78d04d117ab0ba3b77065b9... [3]: https://arxiv.org/pdf/2310.12337.pdf https://arxiv.org/pdf/2310.12337.pdf

deleted 3y ago
[deleted]

rnrn 3y ago

Response from arm: https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/arm-technical-view-on-relaxed-atomics https://community.arm.com/arm-community-blogs/b/architecture... > The characterization in the post of there being "thousands of bug instances related to relaxed atomics accesses" on Arm systems is unfounded – the comparison is not against the C23 specification, but against an, as yet unadopted, proposed tightening of the specification (specifically Section 2.3 as it is understood that this paper otherwise proposes changes which have been ratified) IMO the “out of thin air” problem is a purely academic limitation of the models and matters not much in reality (since an implementation that generates values out of thin air would be a bit insane - no such hardware exists and no such compiler should either) and therefore it does not make sense to add ordering requirements on relaxed atomics to fix what is a non-issue in practice.

raphlinus 3y ago
Thanks for this, quite useful. There's also more discussion in [1], linked from there, which contains perspective from real memory model experts. I think it's fair to say they're skeptical of the proposal. In particular, they've debunked the SC-DRF claim, which seemed fishy to me, but I didn't want to say anything before gathering more evidence. [1]: https://discourse.llvm.org/t/rfc-strengthen-relaxed-atomics-implementation-behind-mstrict-rlx-atomics-flag/74473 https://discourse.llvm.org/t/rfc-strengthen-relaxed-atomics-...
dataflow 3y ago
> IMO the “out of thin air” problem is a purely academic limitation This article is not about the out of thin air problem, is it? I think you're thinking of something else?
- rnrn 3y ago
  The motivation for the branch after load proposal and the addition of ordering constraints on relaxed atomic discussed in the article is the out of thin air problem See Boehm’s original 2013 proposal (linked in the article) for details
- 3y ago

JonChesterfield 3y ago

Relaxed atomics are not broken. They are not hard to reason about. This proposed "fix" is misguided and reflects a fundamental error made by C++ when defining their memory model. The most informative paper on the subject is probably "improved support for bidirectional fences", https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2633.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n26.... There are _two_ different atomic memory models in flight in C++. Relaxed atomic operations are perfect for one and something of a nonsense for the other. One model involves controlling the order of atomic operations within a thread of execution using memory fences. The fences amount to limiting reordering in store buffers or invalidation queues. This is what we had before the C++ memory model, though the operations were called "volatile" then. It's what the hardware ISAs expose, with varying details on cost of different types of fence. This is where relaxed atomic operations are the right thing. The threads do not "synchronise with" one another. The second model involves atomic variables that synchronise with one another in different threads. Mechanism unspecified. As far as I can tell this is largely an invention of the C++ committee based on enthusiasm for methods on class instantiations. The paper linked above seems to be the point where this model accepted that it can't express everything it needs to. It's characterised by memory order annotations on methods on variables and wondering what the compiler is going to do with your code. The "synchronises with" model favoured by C++ can be mechanically translated to the "relaxed with fences" model that the hardware implements. The inverse is not true. One piece of the puzzle I don't have is _why_ this is the state of the art. Given a straightforward, existing model for describing concurrent programming on mutable state, somehow we've ended up with a much more complicated one pasted on top. Which leads to various costs, including this article.

comex 3y ago
"Relaxed with fences" is not always what the hardware implements. ARMv8 [1] provides straight-up load-acquire and store-release instructions, matching C++. [1] https://developer.arm.com/documentation/102336/0100/Load-Acquire-and-Store-Release-instructions https://developer.arm.com/documentation/102336/0100/Load-Acq...
- gpderetta 3y ago