Hacker News Reader

Comment by loeg | Hacker News Reader

> 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!)

View on HN

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/, Mara does a much better job of explaining atomics than I could have then or now.

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.

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.

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.

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

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

Yes, seqcst loads map to plain loads on x86.

Re: the godbolt example, note that release semantics are not meaningful for load operations.

> If order is one of std::memory_order_release and std::memory_order_acq_rel, the behavior is undefined.

https://en.cppreference.com/w/cpp/atomic/atomic/load

I would have to imagine you mean x86-64 right? I would imagine 32bit x86 doesn’t have those instructions?

I’m also kind of curious if a lot of modern code compiled to x86 would see consistency issues running on old CPUs before TSO was formalized (like a p2 multiprocessor server).

32-bit x86 has many of the same instructions, including cmpxchg8b (in models dating to the 90s).

X86 might but devices connected to it in embedded world have had to be very very aware of this stuff since the 90s.

Embedded devices did not necessarily use the c++ memory model, and definitely not in the 90s and were highly likely in order CPUs to boot with no crazy compilers and thus atomics didn’t matter too much anyway (volatile was sufficient). They had a weaker memory model maybe but at the same time multi threading on embedded did not really exist as it was only being introduced into the industry with any real seriousness around that time (threading on Linux started to shake out around the mid 90s).

SMP systems were widely in use in the 1990s, but you’re correct the dual core MIPS was 2003ish in emedded.

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?

> 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.

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-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.

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.

> 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.

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.

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-....

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/synchroniz...

Yes, the store to the HP entry must happen-before both the second load of the global pointer in the publishing thread and any load of the HP entry in another (GC) thread. (The first load + store + second load emulates an atomic memory-to-memory copy of the global pointer to the HP entry.)

You certainly need a #storeload to update the hazard pointer, but do you really need seq_cst? Is a total order of all updates really necessary? Wouldn't, say, an acq_rel exchange be sufficient?

I need to read that article, it seems interesting.

To set a HP on Linux, Folly just does a relaxed load of the src pointer, release store of the HP, compiler-only barrier, and acquire load. (This prevents the compiler from reordering the 2nd load before the store, right? But to my understanding does not prevent a hypothetical CPU reordering of the 2nd load before the store, which seems potentially problematic!)

Then on the GC/reclaim side of things, after protected object pointers are stored, it does a more expensive barrier[0] before acquire-loading the HPs.

I'll admit, I am not confident I understand why this works. I mean, even on x86, loads can be reordered before earlier program-order stores. So it seems like the 2nd check on the protection side could be ineffective. (The non-Linux portable version just uses an atomic_thread_fence SeqCst on both sides, which seems more obviously correct.) And if they don't need the 2nd load on Linux, I'm unclear on why they do it.

[0]: https://github.com/facebook/folly/blob/main/folly/synchroniz...

(This uses either mprotect to force a TLB flush in process-relevant CPUs, or the newer Linux membarrier syscall if available.)

Ah, yes it uses an asynchronous barrier trick. Basically it promotes the compiler barrier to a full barrier. It makes sense for throughput if one side is executed significantly more often than the other like in this case. The cost is latency spikes.

I don't yet understand how the other side promotes a compiler barrier to a full barrier, but I'll take your word for it and try to read more about it later. :-)

There's a good in-depth discussion here: https://pvk.ca/Blog/2019/01/09/preemption-is-gc-for-memory-r...

Yeah, kinda, although this is pretty much the entire discussion on how the asymmetric fence works:

> The slow path can execute its write(s) before making a membarrier syscall. Once the syscall returns, any fast path write that has yet to be visible (hasn’t retired yet), along with every subsequent instruction in program order, started in a state where the slow path’s writes were visible.

(I've actually seen this blog post before, but did not remember this part in detail.)

"promoting" is just a short-hand, what happens is a bit more complicated.

First of all remember that the corresponding membar on the collector would only synchronize with the last membar executed on the mutator thread. So if the collector executes significantly less often the mutator, all the executed mutator membars except the last one is wasted overhead. So ideally we want to elide all mutator membars except those that are actually needed.

What actually happens is that the collector thread remotely executes some code (either directly via a signal or indirectly via mprotect or sys_membar) on the mutator thread that executes the #StoreLoad on its behalf. Sending the required interprocess interrupt is very expensive, but this is ideally offsetted by only doing it when truly required.

You can model[1] this as a signal handler executing on the mutator thread that issues an actual atomic_thread_fence to synchronize with the collector, while the mutator itself only need a atomic_signal_fence (i.e. a compiler barrier) to synchronize with the signal handler.

[1] even if this is not necessarily what happens when using mprotect or sys_membar.

Thanks for explaining the details. In my application though (millions of TPS executing in an MVCC system) I just can't wait possibly tens of ms for membarrier(2) to return: way too much garbage could accumulate in the meantime. From my POV this isn't much better than EBR in terms of low/deterministic latency (it is better in terms of fault-tolerance, if you have out-of-proc clients, but I can reliably detect crashed clients anyway via a Unix domain stream socket and clean up their garbage for them).

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.

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.

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.

The hardware designers were involved on the standardization process. I don't have citations at hand, I think most of the mailing lists were the discussion re the c++ MO happened have been lost, but (as a lurker trying to learn this stuff) I was following the process closely.

The question was, given PO, whether it was at all possible to recover sequential consistently on intel either with mfence or a lock xchg, given the possibility of IRIW. Intel then updated their MO to exclude IRIW, de facto standardizing on TSO.

This was early 2000s. I think both ARM and IBM published revisions to their architecture clarifying details around the same time.

This spawned a set of academic papers that proved the correctness of the agreed mapping of the C++ memory model to those architecture s.

> The hardware designers were involved on the standardization process.

That sounds cyclic then. You're saying that Intel's SDM was ambiguous[1] (which it was) and that it was sorted out as part of a standardization process. I'm saying that it doesn't really matter what the SDM said, it mattered whether or not you could reliably write lockless code on x86 using the hardware and docs available at the time, and you could. And further, I'm saying that the standard ended up making things worse by perpetuating arguments like this about what some buggy English text in an SDM said and not about actual hardware behavior.

[1] In ways that AFAICT didn't actually impact hardware. I found this, which is probably one of the papers you're citing. It's excellent work in standards-writing, but it's also careful to note that the IRIW cases were never observed on hardware. https://www.cl.cam.ac.uk/~pes20/weakmemory/x86tso-paper.tpho...

It didn't impact hardware because intel hadn't taken advantage yet of the additional latitude offered by their original model. Then they closed the hole and they guaranteed no IRIW[1]. But in the meantime if your algorithm was susceptible to this reordering, there was no written guarantee that an mfence would fix it. But most importantly as the model was informal and not self consistent, there was no possibility to write formal proofs of correctness of an algorithm or run it against a model checker.

[1] in practice this means no store-forwarding from sibling hyper thread store buffers, something that for example POWER allows and is observed in real hardware.

C++ is a bug that can’t be fixed

Although, like many bugs, it's also a feature.

Reply on news.ycombinator.com