C++ Concurrency Model on x86 for Dummies (2020)

Thanks for correcting my hand-wavy-ness on that. The thrust of my comment was that blog posts like this need to be handled with some care: this is just enough detail to be dangerous without enough context to be truly helpful.

Getting a bunch of people excited to go start relaxing their loads and stores with mostly-truths like "The CPU's store buffer must be flushed to L1 cache to make the write visible to other threads through cache coherency." is just leaving loaded guns lying around. I'm only mostly sure that some uarchs will read from the store buffer without engaging the cache-coherency stuff at least in an HT/ILP world, but that is kind of the point: playing intrinsics jazz is a very asymmetrical bet. You can win big if you absolutely nail it for your particular chip, but you usually lose it all when it's not correct.

For a slightly more detailed treatment I like this SO answer: https://stackoverflow.com/a/62480523/19734375. It sketches out a better intuition about how the store buffer and speculative stores play out in practice and is very well footnoted.

For those that want to go a level deeper I can't recommend Chips and Cheese highly enough. This treatment of Golden Cove is typical of their rigor in understanding what really pushes architecture-specific performance on cutting-edge gear: https://chipsandcheese.com/2021/12/02/popping-the-hood-on-go....

Edit: Even this comment is self-contradictory. I pulled that SO answer out of my `x86_64 arcana` bookmark folder, and on re-reading it cites a primary source that store buffers are partitioned amongst logical cores by the spec. This stuff is tricky!

There's a constant tension between bit-packing and rich semantics older than me! As you likely know C.A.R. Hoare calls `null` his "billion-dollar mistake": https://www.youtube.com/watch?v=ybrQvs4x0Ps.

I linked the Cliff Click talk because it's the best example that I know about of someone using some semi-formal rigor around valid states and the transitions between them in the context of raw atomic operations to get a quite clearly correct result with a legitimate performance imperative: he had a machine with 768 cores, customers who bought that machine to have 768 threads jump on a hash table all at once and wanted ~~700x more throughput having paid for the machine.

But even Cliff Click made sure that both his conceptual states and their physical representations were going A -> B -> C w.r.t. a given conceptual "register".

I'm not trying to knock the serious concurrency pros who need atomic and/or relaxed operations in some super hot path: there are unambiguous use cases for this stuff. I've legitimately needed these things once or twice myself.

Lock-free is a bad default. Even the elite concurrency pros work very hard to get something that's both robust and still a win after the constant factors. I'm saying "proceed with high caution, and on the basis of measurement", not "never ever do this".

You're going to eat some cost on any speculative/out-of-order chip to get loads and stores ordered bidirectionally relative to getting it down to the `MFENCE` or whatever by hand, though a great deal less than not having a speculative execution pipeline.

The statement you're calling "grossfully incorrect" was double-qualified by "IIRC" and "basically", which I thought was enough to make clear that I was oversimplifying a bit.

The Google doc I linked starts with this:

"Most engineers reach for atomic operations in an attempt to produce some lock-free mechanism. Furthermore, programmers enjoy the intellectual puzzle of using atomic operations. Both of these lead to clever implementations which are almost always ill-advised and often incorrect."

They're being generous.

I'm well aware that it gets up the ass of every self-styled Ghemawat to point out that most people shouldn't be playing jazz on this stuff, but if even one hacker doesn't fuck up something important because I urged some caution, I'll live.

I mean it's not hard to read the source for your platform. On Linux/x86_64/libc++ it's roughly:

- https://github.com/llvm-mirror/libcxx/blob/master/include/__...

- https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=nptl/...

I don't particularly care to comb through it to see if anything has changed, but historically it was a a little spin-CAS to make the non-contended path fast and then dropping into a https://en.wikipedia.org/wiki/Futex, which is about as good as it gets for staying mostly in userspace but still letting it be scheduler aware so you're not burning up a core busy-polling, which is what often happens when people try to roll their own shit.

Google wants a bit more latitude on the heuristics and degrees of freedom around read/write ownership, so they did it like this: https://github.com/abseil/abseil-cpp/blob/master/absl/synchr... which is quite a bit better commented/legible.

If anyone reading this can do better than the `abseil-cpp` folks, not only would Google take their PR, they'd probably offer them a job.

Uncontended mutex operations are cheap and do not require core-core communication.

Contended operations are expensive, whether they are mutex acquisitions, atomic RMW or plain writes.

The dominant term in the type of scenario you're describing is contention, not mutexes. I forget how big they're making Zen3 EPYCs right now, I think you can get like 64-128 physical cores. I can walk all over 128 different mutexes on each of those 128 cores for less than the cost of an L3 hit on that same EPYC box [1].

If I fuck up the affinity and they're all banging on one data structure? Yeah, it can jam the whole machine. This is why people who write good logging libraries are always playing games with buffering in thread-local storage and stuff. And sometimes you do need a bunch of producer threads dumping into a queue that simply can't be striped by anything (it's somewhat rare but it happens): in which case you want `folly::MPMCQueue` (or whatever Intel TBB calls their version of that) which Nathan Bronson was kind enough to get right so that other people don't have to end up with something both slow and wrong.

A truly novel lock-free data structure that advances the SOTA in production software is a masters thesis, not a blog post.

[1] This is a bit dated but it's good enough for eyeball work: https://gist.github.com/jboner/2841832.

Rust does have some very cool mechanisms for safety, including in the presence of concurrency.

But this thread is generating blowback from someone saying: “slow down there with the hand-rolled atomic operations, you can hand-roll your multi-threaded locking strategy and it’ll be way safer at a modest cost!”

So, probably not the target audience for Rust ;)

I use a lot of C++ still because there are libraries I want and I have a significant investment in existing code, but I’d love to get to something more modern.

Hand-rolled atomics and load/store relaxation in application code make even seasoned C++ hackers a bit nervous: we saw this shit from business logic hackers at FB all the time and my colleague coined the term “aggressively intermediate” for the style.

I don’t mean to pick on the author of a quite good library (and it is quite good), but I ran across this the other day:

https://github.com/jupp0r/prometheus-cpp/blob/master/core/sr...

It’s correct (I think, very easy to be wrong about this sort of thing), but what are we measuring here where we can’t delegate that CAS into pthread? Branch mispredictions?

Either threads are fighting over whatever cache line that’s on (exclusive -> invalid -> exclusive -> invalid), or not. If they are, I’ve just deprived the scheduler of the opportunity to wake me up when the other 59 threads are done. If they’re not, I’ve maybe saved like one line in my L1.

And in something like a metrics library, you could be wrong for a very long time before someone pinned it down.

That’s fascinating about the M1. In retrospect it seems like kind of a no-brainer but I doubt I would have thought of it.

SPARC had different memory models at different ISA revs IIRC: it’s been like 20 years since I was dealing with SPARC so I might be misremembering the details. Alpha would have been a better example.

RISC-V is really interesting. I’ve been slowly working through this: https://github.com/standardsemiconductor/lion, highly recommend!

> The synchronizes-with model is much easier to understand than anything reordering based.

Why do you think that?

It shouldn't be a matter of preference. Use a pointer if you need it to be relocatable or if you need it to be optional (it may be nullptr). Otherwise use a reference.

Code following this style (e.g. lots of code following GSG or GSG-derived styles), tends to have large amounts of

  void func(ParamType* param) {
    assert(param != nullptr);
    ...
  }

because passing via pointer introduced undesired nullability. And if that null pointer check isn't present, or is done wrong, you've easily introduced the potential for undefined behavior into the codebase. C++ specifically gives you mutable references to express the desired behavior in these cases, and using a nullable (and memory-unsafe nullable at that) pointer is actively less clear (you now need to document the non-null precondition separately, rather than in the signature itself).

Lots of people say this... they’re wrong but the day this

I do prefer references, because they can't be null. It is less state to worry about.

I agree that not having explicit out-parameters makes this a trade-off. It is possible to use an out-parameter wrapper type to get the best of both worlds, but nobody does this.

The problem with this is that once you get any deeper than the first call, that helpful "&arg" goes away and it's just "arg".

I would argue this sometimes-there single character is incredibly brittle for the claimed benefits, and illustrative of the unwillingness of large parts of the C++ community to use any reasonable tools that would do a better job instead (e.g. very basic syntax highlighting would be far more consistent in indicating mutability).

It depends. What if "f" is macro?