6 ms·

Dealing with caches, memory ordering, and memory barriers can be truly mind-warping stuff, even for those who have spent years dealing with basic cache coherenc

Dealing with caches, memory ordering, and memory barriers can be truly mind-warping stuff, even for those who have spent years dealing with basic cache coherency before. If you want a challenge, try to absorb all this in one sitting. https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt I kept an earlier version of this close to hand at all times a couple of jobs ago where we were using our own chips with a very weak memory ordering. The implementation team had mostly come from Alpha, which had the weakest memory ordering ever, and in the intervening years a lot of bugs related to missing memory barriers had crept into the kernel because nobody was using anything nearly as weak. I specifically remember at least one in NBD, at least one in NFS, and many in Lustre. Pain in the ass to debug, because by the time you can look at anything the values have "settled" and seem correct. For extra fun, as weak as the memory ordering was, the first run of chips didn't even get that right. LL/SC wouldn't work reliably unless the LL was issued twice, so we actually modified compilers to do that. Ew.

jcranmer 3y ago
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.

jcranmer 3y ago

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.