6 ms·

You don't need that full documentation. Really, I could simplify what most programmers would need to understand about memory ordering down to this text: There

You don't need that full documentation. Really, I could simplify what most programmers would need to understand about memory ordering down to this text: There are a few models of cross-thread memory ordering that you can choose between. If you have never been exposed to this field before, the naïve model of memory ordering you probably think is going on is sequential consistency. This is not implemented in hardware because oh-gosh-it's-expensive, and if there's no indication of what memory ordering model your library or language is using, it's likely defaulting to sequential consistency. But don't worry, you don't have to worry about the more complex memory orderings, because you get to pretend everything is sequentially consistent if you write proper synchronization. The easiest way to satisfy proper synchronization is an acquire-release model. Before reading any data that may have been written by a different thread, you need to do an acquire load. After writing any data that may be read by a different thread, you need to do a release store. The basic flow is write then release store, then change thread, then acquire load, then read. Follow this rules, and things stay simple. There is a theoretical slight relaxation of the above model that works on most hardware called release-consume in the C/C++ memory model. It isn't implemented by any compiler for arcane compiler reasons I won't get into, but the Linux kernel (which implements the memory model itself for $REASONS) does rely heavily on it. The final major memory ordering is relaxed atomics. Their semantics are... weird. Essentially, you get what the hardware gives you, plus whatever fun the compiler can toss in, and the guarantees are minimal. I can't recommend many cases where you can safely use it, and if you have to ask if you should use it, the answer is no.

notacoward 3y ago
Oh, you suppose the authors spent their time writing that for no reason? You know better than them? Your explanation is so incomplete I hardly know where to begin. Maybe with the fact that you're talking about local ordering as it may or may not be perturbed by a compiler, while the document is talking about the observed order elsewhere (other processors or main memory). That observed order can vary depending on the processor's ordering model, and to ensure it (e.g. across all modifications to a complex shared data structure) without doing the memory equivalent of an fsync() on every file write (disastrous!) you need memory barriers. All of the bugs I mentioned, all of which were crashes, were related to exactly the distinction you're missing. Yours is the kind of mythology that OP sought to address. Please read the document - particularly the section on CPU memory barriers and anywhere that mentions Alpha - before spreading more misinformation.
- jcranmer 3y ago
  > Oh, you suppose the authors spent their time writing that for no reason? Your explanation is so incomplete I hardly know where to begin. No. I am suggesting that you don't need the full rigor of understanding the memory barrier semantics to be able to effectively write multithreaded code correctly. Completeness was never a goal of my explanation; sufficiency was. Furthermore, my focus is on a software memory model, not the hardware memory model. > Maybe with the fact that doing acquire/release for one value has varying effect (sometimes none) on others, so you'd have to do it separately for all of the many values that might have changed. You have misinterpreted my words, I think. At no point do I suggest that you should insert an acquire/release for each, individual value. Rather, you need to do an acquire at the beginning of a block of code (wherein you can read and write multiple values) and a release at the end of a block of code, much as you would with a mutex (except it's not necessary that the regions of code actually be mutually excluded from executing on multiple threads). The only requirement is that the store be followed by a release operation that crosses threads to an acquire operation that is followed by a load. > Then we can move on to the concept of dependent reads, and so on. I allude to those under the part where I mention "There is a theoretical slight relaxation of the above model that works on most hardware called release-consume in the C/C++ memory model." That you did not pick up on that is perhaps because you yourself are unfamiliar with the release-consume portion of the C/C++ memory model. If you need a refresher, I might point you to the thread where I actually go into why it exists, and why it's not implemented by compilers, here: https://news.ycombinator.com/item?id=36059369 https://news.ycombinator.com/item?id=36059369. (There's a reason I'm not going into it in a facile explanation!) > Please read the document before you spread more misinformation. Oh, do trust me, I have read that document, and far more, on memory models. I am not spreading misinformation. Perhaps my word choice and my writing is inartful or oversimplified in the goal of making the topic more accessible rather than seeking to enshrine comprehensive knowledge in thick tomes that many will give up reading. Perhaps you yourself may not be sufficiently informed as to pick up on the specific terminology that I use, which derives from the dominant memory model in use by, well, everybody.
  - notacoward 3y ago
    > dominant memory model in use by, well, everybody. "...by, well, x86" Fixed that for you.
klabb3 3y ago
I’m nowhere near as deep in this rabbit hole. But I recall running/seeing some benchmarks on different memory orderings and the differences were not.. that big, on x86 I believe. Obviously there’s a lot that can go wrong with micro-benchmarks in these incredibly complex systems, but I still got the feeling that memory orderings are perhaps not worth the immense complexity that they introduce, for let’s say the majority of programmers, even low level folks. What are your thoughts on this?
- jcranmer 3y ago
  As noted elsewhere, x86 itself really doesn't have much difference. But it matters a lot more on other architectures--I caused like a 20-30% regression in JS performance on ARM by changing one atomic variable in the engine to sequentially-consistent instead of release-acquire. My recommendations boil down to the following: * If you're ever truly unsure, just stick with sequentially-consistent unless performance is so critical you need to get off of it. Correctness is more important that speed! * You can use acquire/release if you've got something that smells sufficiently like a lock (there's a clear scope with beginning and end, and most of the memory accesses outside the acquire/release themselves are regular, unsynchronized accesses). Most of this code should probably be hidden in libraries anyways, but this probably should be your basic default if you're working with atomics if there's only one atomic variable in play. * The other memory orderings I wouldn't recommend at all. Release/consume, even were it implemented by compilers as intended, requires a particular (though common) set of circumstances to work correctly. Relaxed affords no synchronization opportunities, and the one use case I can think of for it involves atomic read-modify-write operations, which I think all hardware makes as strong as an release+acquire anyways. In short, worrying about sequential consistency versus release/acquire can be helpful, and I think there are simple enough rules-of-thumb to make it worthwhile to summarize it. The other memory orderings, not so much.
  - klabb3 3y ago
    > I caused like a 20-30% regression in JS performance on ARM by changing one atomic variable in the engine to sequentially-consistent instead of release-acquire. Very interesting. Was this overall performance? What type of workload was involved? Yeah it seems like acq-rel is the only other one worth keeping an eye out for. When using atomics you have different logical ops with a certain happens-before relation between them anyway. Figuring out whether these ops map to acq-rel seems like a reasonable task to take on, given the total effort. The main argument against it is lack of testing infrastructure (since indeed correctness is more important). With something like Loom (the Rust project) it’s significantly easier to prevent subtle bugs. I wish it was more widely available.
gpderetta 3y ago
> You get to pretend everything is sequentially consistent if you write proper synchronization. The easiest way to satisfy proper synchronization is an acquire-release model But acquire/release give, generally,a partial ordering, not a total order like sequential consistency. That's often enough of course.
- jcranmer 3y ago
  The data-race-free theorem states that, in the absence of data races, acquire/release is indistinguishable from sequential consistency. Define data races to be UB, as C/C++ do, and you get to the state that acquire/release lets you pretend everything (except atomic operations themselves) is sequentially consistent.
  - gpderetta 3y ago
    My understanding is that that only applies to programs that use mutex lock/unlock operations (which do have acquire/release semantics), but not to programs that use acq/rel memory operations in general. For example: https://www.hboehm.info/c++mm/sc_proof.html https://www.hboehm.info/c++mm/sc_proof.html which contains the the SC proof for lock operations that you mention, but also a counterexample for acq/rel atomics.
    - jcranmer 3y ago
      The original data-race-free models are based on acquire/release semantics that underlie the C++ memory model (https://pages.cs.wisc.edu/~markhill/papers/topds93_drf1.pdf https://pages.cs.wisc.edu/~markhill/papers/topds93_drf1.pdf), so the use of acquire/release atomics should provide the same guarantees as mutex lock/unlock. However, the sequential consistency guarantee doesn't necessarily apply to atomics themselves, and I think the difference between the data-race-free-0 and data-race-free-1 models is whether not they would extend the guarantee to the release-acquire atomic operations.
      - gpderetta 3y ago

notacoward 3y ago

Oh, you suppose the authors spent their time writing that for no reason? You know better than them? Your explanation is so incomplete I hardly know where to begin. Maybe with the fact that you're talking about local ordering as it may or may not be perturbed by a compiler, while the document is talking about the observed order elsewhere (other processors or main memory). That observed order can vary depending on the processor's ordering model, and to ensure it (e.g. across all modifications to a complex shared data structure) without doing the memory equivalent of an fsync() on every file write (disastrous!) you need memory barriers. All of the bugs I mentioned, all of which were crashes, were related to exactly the distinction you're missing. Yours is the kind of mythology that OP sought to address. Please read the document - particularly the section on CPU memory barriers and anywhere that mentions Alpha - before spreading more misinformation.

jcranmer 3y ago
> Oh, you suppose the authors spent their time writing that for no reason? Your explanation is so incomplete I hardly know where to begin. No. I am suggesting that you don't need the full rigor of understanding the memory barrier semantics to be able to effectively write multithreaded code correctly. Completeness was never a goal of my explanation; sufficiency was. Furthermore, my focus is on a software memory model, not the hardware memory model. > Maybe with the fact that doing acquire/release for one value has varying effect (sometimes none) on others, so you'd have to do it separately for all of the many values that might have changed. You have misinterpreted my words, I think. At no point do I suggest that you should insert an acquire/release for each, individual value. Rather, you need to do an acquire at the beginning of a block of code (wherein you can read and write multiple values) and a release at the end of a block of code, much as you would with a mutex (except it's not necessary that the regions of code actually be mutually excluded from executing on multiple threads). The only requirement is that the store be followed by a release operation that crosses threads to an acquire operation that is followed by a load. > Then we can move on to the concept of dependent reads, and so on. I allude to those under the part where I mention "There is a theoretical slight relaxation of the above model that works on most hardware called release-consume in the C/C++ memory model." That you did not pick up on that is perhaps because you yourself are unfamiliar with the release-consume portion of the C/C++ memory model. If you need a refresher, I might point you to the thread where I actually go into why it exists, and why it's not implemented by compilers, here: https://news.ycombinator.com/item?id=36059369 https://news.ycombinator.com/item?id=36059369. (There's a reason I'm not going into it in a facile explanation!) > Please read the document before you spread more misinformation. Oh, do trust me, I have read that document, and far more, on memory models. I am not spreading misinformation. Perhaps my word choice and my writing is inartful or oversimplified in the goal of making the topic more accessible rather than seeking to enshrine comprehensive knowledge in thick tomes that many will give up reading. Perhaps you yourself may not be sufficiently informed as to pick up on the specific terminology that I use, which derives from the dominant memory model in use by, well, everybody.
- notacoward 3y ago
  > dominant memory model in use by, well, everybody. "...by, well, x86" Fixed that for you.

klabb3 3y ago

I’m nowhere near as deep in this rabbit hole. But I recall running/seeing some benchmarks on different memory orderings and the differences were not.. that big, on x86 I believe. Obviously there’s a lot that can go wrong with micro-benchmarks in these incredibly complex systems, but I still got the feeling that memory orderings are perhaps not worth the immense complexity that they introduce, for let’s say the majority of programmers, even low level folks. What are your thoughts on this?

jcranmer 3y ago
As noted elsewhere, x86 itself really doesn't have much difference. But it matters a lot more on other architectures--I caused like a 20-30% regression in JS performance on ARM by changing one atomic variable in the engine to sequentially-consistent instead of release-acquire. My recommendations boil down to the following: * If you're ever truly unsure, just stick with sequentially-consistent unless performance is so critical you need to get off of it. Correctness is more important that speed! * You can use acquire/release if you've got something that smells sufficiently like a lock (there's a clear scope with beginning and end, and most of the memory accesses outside the acquire/release themselves are regular, unsynchronized accesses). Most of this code should probably be hidden in libraries anyways, but this probably should be your basic default if you're working with atomics if there's only one atomic variable in play. * The other memory orderings I wouldn't recommend at all. Release/consume, even were it implemented by compilers as intended, requires a particular (though common) set of circumstances to work correctly. Relaxed affords no synchronization opportunities, and the one use case I can think of for it involves atomic read-modify-write operations, which I think all hardware makes as strong as an release+acquire anyways. In short, worrying about sequential consistency versus release/acquire can be helpful, and I think there are simple enough rules-of-thumb to make it worthwhile to summarize it. The other memory orderings, not so much.
- klabb3 3y ago
  > I caused like a 20-30% regression in JS performance on ARM by changing one atomic variable in the engine to sequentially-consistent instead of release-acquire. Very interesting. Was this overall performance? What type of workload was involved? Yeah it seems like acq-rel is the only other one worth keeping an eye out for. When using atomics you have different logical ops with a certain happens-before relation between them anyway. Figuring out whether these ops map to acq-rel seems like a reasonable task to take on, given the total effort. The main argument against it is lack of testing infrastructure (since indeed correctness is more important). With something like Loom (the Rust project) it’s significantly easier to prevent subtle bugs. I wish it was more widely available.

gpderetta 3y ago

> You get to pretend everything is sequentially consistent if you write proper synchronization. The easiest way to satisfy proper synchronization is an acquire-release model But acquire/release give, generally,a partial ordering, not a total order like sequential consistency. That's often enough of course.

jcranmer 3y ago
The data-race-free theorem states that, in the absence of data races, acquire/release is indistinguishable from sequential consistency. Define data races to be UB, as C/C++ do, and you get to the state that acquire/release lets you pretend everything (except atomic operations themselves) is sequentially consistent.
- gpderetta 3y ago
  My understanding is that that only applies to programs that use mutex lock/unlock operations (which do have acquire/release semantics), but not to programs that use acq/rel memory operations in general. For example: https://www.hboehm.info/c++mm/sc_proof.html https://www.hboehm.info/c++mm/sc_proof.html which contains the the SC proof for lock operations that you mention, but also a counterexample for acq/rel atomics.
  - jcranmer 3y ago
    The original data-race-free models are based on acquire/release semantics that underlie the C++ memory model (https://pages.cs.wisc.edu/~markhill/papers/topds93_drf1.pdf https://pages.cs.wisc.edu/~markhill/papers/topds93_drf1.pdf), so the use of acquire/release atomics should provide the same guarantees as mutex lock/unlock. However, the sequential consistency guarantee doesn't necessarily apply to atomics themselves, and I think the difference between the data-race-free-0 and data-race-free-1 models is whether not they would extend the guarantee to the release-acquire atomic operations.
    - gpderetta 3y ago