6 ms·

> The safe thing to do here is to always choose Ordering::SeqCst, "sequential consistency", which provides the strongest guarantees. ... This is often good enou

by loeg 3y ago

> The safe thing to do here is to always choose Ordering::SeqCst, "sequential consistency", which provides the strongest guarantees. ... This is often good enough in practice, and switching to a weaker Ordering is only necessary to squeeze out the last bit of performance. If you're going to write lock-free algorithms using atomics, the least you can do is learn about ordering semantics and use the correct abstract semantics for your design's actual needs. It is much easier to do it at design time than to try to figure out if it is safe to relax SeqCst later. (This is one of the major flaws of C++ std::atomic's default SeqCst semantics.) If you aren't going to bother understanding ordering semantics, it is unlikely you can write a safe lock-free algorithm anyway. (It's really hard to do!)

jamesmunns 3y ago
Back then, there weren't as good references for explaining atomic ordering, and the blog post had gotten long enough. Mentioning SeqCst was a bit of a cop out, though both Andrea and I didn't end up using SeqCst past the inital impl anyway. Today I would have just linked to https://marabos.nl/atomics/ https://marabos.nl/atomics/, Mara does a much better job of explaining atomics than I could have then or now.
- hinkley 3y ago
  Back then? Do you mean 2019? Or a different “then”? Because there was plenty of material in CS about this subject even in 2010. Java was wrestling with this twenty years ago, and databases long before that.
  - jamesmunns 3y ago
    I meant 2019, and there weren't any materials that I would consider as clear and well defined as Mara's linked docs explaining the different orderings used by C, C++, and Rust (Relaxed, Release, Acquire, AcqRel, and SeqCst). I'm very sure there were discussions and teaching materials then, but none (that I was aware of) focused on Rust, and something I'd link to someone who had never heard of atomic ordering before.
  - anonymous-panda 3y ago
    I think the hard part of it is that x86 only has one atomic ordering and none of the other modes do anything. As such, it’s really hard to build intuition about it unless you spend a lot of time writing such code on ARM which wasn’t that common in the industry and today most people use higher level abstractions. By databases, do you mean those running on DEC Alphas? Cause that was a niche system that few would have had experience with. If you meant to compare in terms if consistency semantically, sure but there’s meaningful differences between database consistency semantics of concurrent transactions and atomic ordering in a multithreaded concept. Java’s memory model “wrestling” was about defining it formally in an era of multithreading and it’s largely sequentially consistent - no weakly consistent ordering allowed. The c++ memory model was definitely the first large scale adoption of weaker consistency models I’m aware of and was done so that ARM CPUs could be properly optimized for since this was c++11 when mobile CPUs were very much front of mind. Weak consistency remains really difficult to reason about and even harder to play around with if you primarily work with x86 and there’s very little tooling around to validate that can help you get confidence about whether your code is correct. Of course, you can follow common “patterns” (eg loads are always acquire and stores are release), but fully grokking correctness and being able to play with the model in interesting ways is no small task no matter how many learning resources are out there.
    - gpderetta 3y ago
      Nit: x86 has acquire/release and seq_cst for load/stores (it technically also has relaxed, but it is not useful to map it to c++11 relaxed). What x86 lacks is weaker ordering for RMW, but there are a lot of useful lock free algorithms that are implementable just or mostly with load and stores and it can be a significant win to use non-seq-cst stores for this on x86
      - haberman 3y ago
        Indeed there is different code generated by seq_cst for stores. Though for loads it appears to be the same: https://godbolt.org/z/WbvEcM83q https://godbolt.org/z/WbvEcM83q
- nyanpasu64 3y ago
  Chapter 7 doesn't test if performing loads on a reader thread makes a writer thread any slower to perform relaxed writes. Does a concurrent reader slow down writes or not (the LMAX Disruptor relies on variables with one writer and many readers, and claims it's fast), and does it depend on the CPU's cache coherence protocol?
jcelerier 3y ago
> It is much easier to do it at design time Is it? I always worked the second way (starting from seq_cst and then when the core design matured enough and didn't change for a few months, trying to see what could actually be relaxed). I'd be very afraid that in the first case, you start with say relaxed semantics somewhere, them you change the design because the requirements changed, and now you have to go again through all the atomic operations to make sure the assumptions all still hold.
- jamesmunns 3y ago
  Back when this post was written, I would have agreed with you. But Mara's book makes a good case for this: https://marabos.nl/atomics/memory-ordering.html#common-misconceptions https://marabos.nl/atomics/memory-ordering.html#common-misco... More importantly, when reading code, SeqCst basically tells the reader: "this operation depends on the total order of every single SeqCst operation in the program," which is an incredibly far-reaching claim. The same code would likely be easier to review and verify if it used weaker memory ordering instead, if possible... It is advisable to see SeqCst as a warning sign.
- gpderetta 3y ago
  If you change the design of a lock free algo you very likely have to go through all the atomic operations to make sure that all assumptions hold anyway.
ajross 3y ago
Completely agree, though the more iconoclastic corrolary that goes unspoken there is that putting The Final Word on memory ordering semantics into programming language standards was a terrible mistake. Memory ordering is a hardware behavior. It needs to be specified at the hardware level, and hardware vendors have been very mixed on clarity. And more importantly, lockless algorithms (that rely on memory ordering control) are really, really hard, and demand clarity over all things. And instead we're crippling those poor programmers with nonsense like "sequentially consistent"[1] or trying to figure out what on earth "consume" means[2]. x86 does this pretty well with their comparatively simple model of serializing instructions. Traditional ARM ISAs did only a little worse by exposing the interface as read/write barrier instructions. Everyone else... meh. But if you really want to do this (and you probably don't) do the analysis yourself at the level of ISA/architecture/hardware, cite your references, and be prepared to handle whatever portability works is needed on your own. [1] A statement about desired final state, not hardware behavior! [2] Nothing, on any hardware you will ever use. Don't ask.
- gpderetta 3y ago
  On the contrary, fixing the memory model on a widely used language like C++ forced hardware vendors to get their act together and provide more rigorous memory model explanations. For example intel went from Processor Ordering to TSO, and arm started offering explicit acquire/release operations. Java had the opportunity as well, but by initially only providing a stronger, mostly sequentially consistent MO, the hardware vendors managed to get away a little longer.
  - ajross 3y ago
    I don't think that's the case with Intel at all, the events are off by a decade at least; do you have a blog or something to cite there? I'd be curious to read it. And as for ARM, "explicit acquire/release" is objectively less informative and harder to reason about than the xxxSB instructions were (and yes, I've used both). ARM went backwards to accommodate C++'s nonsense. Again, the language standard writers aren't remotely the experts here, the hardware designers are. That C++ invented its own metaphors instead of listening to the experts is a bug, not a feature.
haberman 3y ago
I've never actually seen a production lock-free algorithm that uses SeqCst. I have a hard time even imagining an algorithm where SeqCst is the right choice. It seems like SeqCst was chosen as a default to reduce the surprises and gotchas around lock-free programming. But lock-free programming is inherently tricky; if you're trying to avoid surprises and gotchas you should probably use a mutex.
- senderista 3y ago
  It is the right choice whenever you need linearizability. I can't believe you've never seen a (correct) production lock-free algorithm impl that used SeqCst. Many lock-free algorithms require SeqCst for correctness. Here's a trivial example: hazard pointers. Any thread publishing its hazard pointer must use a StoreLoad barrier (equivalent to SeqCst) to ensure any GC thread scanning the publication list sees its hazard pointer, before it deallocates pointers in the limbo list that didn't appear in the scan. MemSQL actually wrote a blog post on a nasty bug in their database arising from their use of AcqRel for this operation instead of SeqCst: https://www.singlestore.com/blog/common-pitfalls-in-writing-lock-free-algorithms/ https://www.singlestore.com/blog/common-pitfalls-in-writing-....
  - loeg 3y ago
    This blog post leaves a lot to the imagination. > Here’s the case that broke our stack: Thread 1, in preparation for a Pop operation, reads the head of the stack. Thread 1 writes the current head to its hazard pointer (using only release semantics, which are weaker than sequentially consistent semantics). Thread 1 reads the head of the stack again. Thread 2 removes head from the stack, and passes it to the garbage collector thread (using sequentially consistent memory semantics). The garbage collector scans the hazard pointers,\ and (because the assignment was not done with sequentially consistent memory semantics) is not guaranteed to see thread 1’s hazard pointer pointing to the node. The garbage collector deletes the node Thread 1 dereferences the node, and segfaults. My interpretation is that with release semantics for the store, the 2nd read (load) in Thread 1 is actually allowed to be reordered before the release store to the hazard pointer. But they are not very explicit about it. > So if thread 2 removing the pointer happens first, thread 1 will see a different value on its second read and not attempt to dereference it. Thread 1 will see thread 2's remove even with release semantics for that store -- the store has a data dependency on the first load; they cannot be reordered. > If thread 1 writes to its hazard pointer first, the garbage collector is guaranteed to see that value and not delete the node. Yeah, this must be it. Thread 1 fails to notice the GC happened while it was writing its HP because its second load actually happened before the HP store. Folly's hazard pointer implementation uses a release store to update the hazard pointer (here: reset_protection()), but uses some sort of SeqCst barrier between the store and the 2nd load (with acquire semantics): https://github.com/facebook/folly/blob/main/folly/synchronization/HazptrHolder.h#L120-L125 https://github.com/facebook/folly/blob/main/folly/synchroniz...
derefr 3y ago
> If you aren't going to bother understanding ordering semantics, it is unlikely you can write a safe lock-free algorithm anyway. I think the implicit suggestion here is that the target audience for this abstraction is actually two separate developers: 1. A developer who doesn’t know much about locking semantics, but can write the simple-but-slow case correctly. 2. Another developer, much later on — probably a senior SRE type — who can revisit this code and optimize it with full understanding of the constraints. (This might also be the same person, years later, with more experience under their belt.) The benefit of the way this library is designed, is that the second developer doesn’t have to completely rewrite everything just to optimize it. The naive dev’s code has already been forced into an “almost but not quite” lock-free mold by the design of the library’s API surface.
deleted 3y ago
[deleted]

by loeg 3y ago

jamesmunns 3y ago

Back then, there weren't as good references for explaining atomic ordering, and the blog post had gotten long enough. Mentioning SeqCst was a bit of a cop out, though both Andrea and I didn't end up using SeqCst past the inital impl anyway. Today I would have just linked to https://marabos.nl/atomics/ https://marabos.nl/atomics/, Mara does a much better job of explaining atomics than I could have then or now.

hinkley 3y ago
Back then? Do you mean 2019? Or a different “then”? Because there was plenty of material in CS about this subject even in 2010. Java was wrestling with this twenty years ago, and databases long before that.
- jamesmunns 3y ago
  I meant 2019, and there weren't any materials that I would consider as clear and well defined as Mara's linked docs explaining the different orderings used by C, C++, and Rust (Relaxed, Release, Acquire, AcqRel, and SeqCst). I'm very sure there were discussions and teaching materials then, but none (that I was aware of) focused on Rust, and something I'd link to someone who had never heard of atomic ordering before.
- anonymous-panda 3y ago
  I think the hard part of it is that x86 only has one atomic ordering and none of the other modes do anything. As such, it’s really hard to build intuition about it unless you spend a lot of time writing such code on ARM which wasn’t that common in the industry and today most people use higher level abstractions. By databases, do you mean those running on DEC Alphas? Cause that was a niche system that few would have had experience with. If you meant to compare in terms if consistency semantically, sure but there’s meaningful differences between database consistency semantics of concurrent transactions and atomic ordering in a multithreaded concept. Java’s memory model “wrestling” was about defining it formally in an era of multithreading and it’s largely sequentially consistent - no weakly consistent ordering allowed. The c++ memory model was definitely the first large scale adoption of weaker consistency models I’m aware of and was done so that ARM CPUs could be properly optimized for since this was c++11 when mobile CPUs were very much front of mind. Weak consistency remains really difficult to reason about and even harder to play around with if you primarily work with x86 and there’s very little tooling around to validate that can help you get confidence about whether your code is correct. Of course, you can follow common “patterns” (eg loads are always acquire and stores are release), but fully grokking correctness and being able to play with the model in interesting ways is no small task no matter how many learning resources are out there.
  - gpderetta 3y ago
    Nit: x86 has acquire/release and seq_cst for load/stores (it technically also has relaxed, but it is not useful to map it to c++11 relaxed). What x86 lacks is weaker ordering for RMW, but there are a lot of useful lock free algorithms that are implementable just or mostly with load and stores and it can be a significant win to use non-seq-cst stores for this on x86
    - haberman 3y ago
      Indeed there is different code generated by seq_cst for stores. Though for loads it appears to be the same: https://godbolt.org/z/WbvEcM83q https://godbolt.org/z/WbvEcM83q
nyanpasu64 3y ago
Chapter 7 doesn't test if performing loads on a reader thread makes a writer thread any slower to perform relaxed writes. Does a concurrent reader slow down writes or not (the LMAX Disruptor relies on variables with one writer and many readers, and claims it's fast), and does it depend on the CPU's cache coherence protocol?

jcelerier 3y ago

> It is much easier to do it at design time Is it? I always worked the second way (starting from seq_cst and then when the core design matured enough and didn't change for a few months, trying to see what could actually be relaxed). I'd be very afraid that in the first case, you start with say relaxed semantics somewhere, them you change the design because the requirements changed, and now you have to go again through all the atomic operations to make sure the assumptions all still hold.

jamesmunns 3y ago
Back when this post was written, I would have agreed with you. But Mara's book makes a good case for this: https://marabos.nl/atomics/memory-ordering.html#common-misconceptions https://marabos.nl/atomics/memory-ordering.html#common-misco... More importantly, when reading code, SeqCst basically tells the reader: "this operation depends on the total order of every single SeqCst operation in the program," which is an incredibly far-reaching claim. The same code would likely be easier to review and verify if it used weaker memory ordering instead, if possible... It is advisable to see SeqCst as a warning sign.
gpderetta 3y ago
If you change the design of a lock free algo you very likely have to go through all the atomic operations to make sure that all assumptions hold anyway.

ajross 3y ago

Completely agree, though the more iconoclastic corrolary that goes unspoken there is that putting The Final Word on memory ordering semantics into programming language standards was a terrible mistake. Memory ordering is a hardware behavior. It needs to be specified at the hardware level, and hardware vendors have been very mixed on clarity. And more importantly, lockless algorithms (that rely on memory ordering control) are really, really hard, and demand clarity over all things. And instead we're crippling those poor programmers with nonsense like "sequentially consistent"[1] or trying to figure out what on earth "consume" means[2]. x86 does this pretty well with their comparatively simple model of serializing instructions. Traditional ARM ISAs did only a little worse by exposing the interface as read/write barrier instructions. Everyone else... meh. But if you really want to do this (and you probably don't) do the analysis yourself at the level of ISA/architecture/hardware, cite your references, and be prepared to handle whatever portability works is needed on your own. [1] A statement about desired final state, not hardware behavior! [2] Nothing, on any hardware you will ever use. Don't ask.

gpderetta 3y ago
On the contrary, fixing the memory model on a widely used language like C++ forced hardware vendors to get their act together and provide more rigorous memory model explanations. For example intel went from Processor Ordering to TSO, and arm started offering explicit acquire/release operations. Java had the opportunity as well, but by initially only providing a stronger, mostly sequentially consistent MO, the hardware vendors managed to get away a little longer.
- ajross 3y ago
  I don't think that's the case with Intel at all, the events are off by a decade at least; do you have a blog or something to cite there? I'd be curious to read it. And as for ARM, "explicit acquire/release" is objectively less informative and harder to reason about than the xxxSB instructions were (and yes, I've used both). ARM went backwards to accommodate C++'s nonsense. Again, the language standard writers aren't remotely the experts here, the hardware designers are. That C++ invented its own metaphors instead of listening to the experts is a bug, not a feature.

haberman 3y ago

I've never actually seen a production lock-free algorithm that uses SeqCst. I have a hard time even imagining an algorithm where SeqCst is the right choice. It seems like SeqCst was chosen as a default to reduce the surprises and gotchas around lock-free programming. But lock-free programming is inherently tricky; if you're trying to avoid surprises and gotchas you should probably use a mutex.

senderista 3y ago
It is the right choice whenever you need linearizability. I can't believe you've never seen a (correct) production lock-free algorithm impl that used SeqCst. Many lock-free algorithms require SeqCst for correctness. Here's a trivial example: hazard pointers. Any thread publishing its hazard pointer must use a StoreLoad barrier (equivalent to SeqCst) to ensure any GC thread scanning the publication list sees its hazard pointer, before it deallocates pointers in the limbo list that didn't appear in the scan. MemSQL actually wrote a blog post on a nasty bug in their database arising from their use of AcqRel for this operation instead of SeqCst: https://www.singlestore.com/blog/common-pitfalls-in-writing-lock-free-algorithms/ https://www.singlestore.com/blog/common-pitfalls-in-writing-....
- loeg 3y ago
  This blog post leaves a lot to the imagination. > Here’s the case that broke our stack: Thread 1, in preparation for a Pop operation, reads the head of the stack. Thread 1 writes the current head to its hazard pointer (using only release semantics, which are weaker than sequentially consistent semantics). Thread 1 reads the head of the stack again. Thread 2 removes head from the stack, and passes it to the garbage collector thread (using sequentially consistent memory semantics). The garbage collector scans the hazard pointers,\ and (because the assignment was not done with sequentially consistent memory semantics) is not guaranteed to see thread 1’s hazard pointer pointing to the node. The garbage collector deletes the node Thread 1 dereferences the node, and segfaults. My interpretation is that with release semantics for the store, the 2nd read (load) in Thread 1 is actually allowed to be reordered before the release store to the hazard pointer. But they are not very explicit about it. > So if thread 2 removing the pointer happens first, thread 1 will see a different value on its second read and not attempt to dereference it. Thread 1 will see thread 2's remove even with release semantics for that store -- the store has a data dependency on the first load; they cannot be reordered. > If thread 1 writes to its hazard pointer first, the garbage collector is guaranteed to see that value and not delete the node. Yeah, this must be it. Thread 1 fails to notice the GC happened while it was writing its HP because its second load actually happened before the HP store. Folly's hazard pointer implementation uses a release store to update the hazard pointer (here: reset_protection()), but uses some sort of SeqCst barrier between the store and the 2nd load (with acquire semantics): https://github.com/facebook/folly/blob/main/folly/synchronization/HazptrHolder.h#L120-L125 https://github.com/facebook/folly/blob/main/folly/synchroniz...

derefr 3y ago

> If you aren't going to bother understanding ordering semantics, it is unlikely you can write a safe lock-free algorithm anyway. I think the implicit suggestion here is that the target audience for this abstraction is actually two separate developers: 1. A developer who doesn’t know much about locking semantics, but can write the simple-but-slow case correctly. 2. Another developer, much later on — probably a senior SRE type — who can revisit this code and optimize it with full understanding of the constraints. (This might also be the same person, years later, with more experience under their belt.) The benefit of the way this library is designed, is that the second developer doesn’t have to completely rewrite everything just to optimize it. The naive dev’s code has already been forced into an “almost but not quite” lock-free mold by the design of the library’s API surface.

deleted 3y ago

[deleted]