Hacker News Reader

> which IIRC makes `std::memory_order_seq_cst` pretty much free on Intel

The article explains how that is only true for loads, not stores.

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!

If they weren't partioned, it would be hard to preserve TSO as a core would be able to see not only its own stores out of order but the sibling hyperthread as well.

This is the case on POWER for example but it is allowed by its more relaxed memory model.

> Combine that with how cheap `std::mutex` is on most platforms

This is suspiciously hand-wavy. How "cheap" do you think std::mutex is, and on what platforms?

The thrust of your argument makes sense, but one reason it's so tempting is that many C++ programmers are (or at least want to believe they are) writing performance sensitive code and yet the C++ language and standard library prioritize compatibility over any other consideration.

So there's a good chance even though the obvious way to design a mutex on your platform today is a small integer plus OS support, writing std::mutex gets you some huge unwieldy mess because that's compatible with programs written when the "First Black President" was still a white guy named Bill...

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.

I am always disappointed when someone talks about std::mutex poorly. On Linux it is as good as it can possibly be for a generic catch all lock and by that I mean it is really really good for most usecases. If you want to use a spinlock to outperform std::mutex you will at least have to do the legwork of using real time scheduling and guaranteeing that any spinlock you are locking will be unlocked within a finite amount of time with a known upper bound. Any less and your spinlock will cause problems when your thread locks it and then gets interrupted by the OS scheduler.

> On Linux it is as good as it can possibly be for a generic catch all lock

A futex is a 32-bit aligned value, thus it needs 4 bytes. But std::mutex on Linux is 40 bytes, ten times larger. Now, maybe where you come from "ten times larger than it needs to be" is "as good as it can possibly be" but where I come from that's not very good.

The only issue with std::mutex on libstdc++ is that it is larger than it needs to be for ABI reasons. Otherwise it is perfectly adequate for many use cases.

Great point. The `libstdc++` ABI is very low on my list of favorite things. Who doesn't love spilling cache lines because of 1990s layouts and taking L3 misses for `auto s = std::string{"hello world"};` because modern SSO breaks that ABI and... /s

It's adequate if you're happy yielding to the kernel and needing some other thread to issue a system call to wake you up.

Some uses of C++ have stricter latency and real-time requirements which aren't compatible with this.

If you're in a serious multicore setting and you don't take waiting threads off the contended cache line while the other 50 threads take their turn with the underlying contended thing it's very easy to end up way worse off than if you had just let the scheduler drop those threads into e.g. a futex and wake them up when it's their turn.

I'm not sure how deep you'd need to go into the low-power or embedded or hard-realtime worlds before `std::mutex` doesn't do a modest number of spin-CAS rounds before dropping into the futex, I'm sure it exists.

And maybe you work at Optiver and you've got an FPGA interacting with the link-layer and you literally never leave userspace after startup and you've got your own hand-crafted DMA busy-poll situation going because you build your machines with the exact number of cores for the number of threads you need and throw them away when the software changes. There are domains like that. </modest-hyperbole>

The number of "aggressively intermediate" people working at serious companies who roll their own concurrency shit because it's Just Fucking Metal Man is terrifyingly high. And it's dangerous, because if you are someone who needs custom concurrency you know, but if you aren't someone who needs custom concurrency, you often still think you know.

As soon as you yield, things become non-deterministic, so aren't compatible with real-time requirements.

If you have 50 threads trying to access the same thing then what you have is a software design problem. Most synchronization should be done through spsc queues, which are easy to make lock-free (or even wait-free) and efficient, so long as you're aware of how to deal with backoff on the producing side and idle work on the consuming side.

The Optiver model you're describing is pretty much how I'd build any low-latency application. It doesn't really require special hardware to do these things (you can use io_uring to bypass the kernel context switches for anything). It's also much simpler than what you hint at.

I'm willing to accept that a London-based crypto startup (i.e. LMAX-integrated) could have a use for extreme low-latency, extreme low-variance soft-realtime C++. In the sub-mike p99 regime you probably want to keep multithreading out of it entirely in fact.

Hopefully you can accept that nitpicking the use of well-tested concurrency primitives on a forum full of impressionable up-and-coming hackers is almost certainly going to create downward pressure on sensible engineering choices amongst readers of your comments.

Have you been googling me? A few inaccuracies there ;).

>As soon as you yield, things become non-deterministic, so aren't compatible with real-time requirements.

SCHED_FIFO and SCHED_RR.

Although linux is not really an RT OS.

Once again, exactly right.

I deeply appreciate you helping to steer this little tire fire of a comment thread I seem to have created off the rocks, I meant well but it seems to have ended up as an advertisement for insane defaults.

With that said, the parent seems pretty committed. And for all I know, is actually doing sub-microsecond software HFT or hard-realtime signal processing.

Thread: listen to this person ^.

Threads can be derailed, that's usually how interesting things come up.

Fast implementations of std::mutex spin for a bounded amount of time before yielding, if you unlock the mutex fast enough it will have roughly the performance of a spinlock and if your locking thread gets interrupted by the scheduler, other threads waiting for the mutex will stop spinning and yield.

I already mentioned real time scheduling which is well outside of the scope of the vast majority of userspace applications.

I think this is pretty much exactly right with the caveat that "fast implementations" is probably "the overwhelming majority of implementations". `libpthread` on GNU has been doing this since smart phones were quite the novelty. I'm sure it exists, but I'm having a hard time imagining who wrote a C++11 compliant standard library and didn't do this optimization.

RISC-V is pretty interesting in this regard; it uses weak memory ordering by default, but a CPU that implements TSO can simply flag Ztso, and I believe that would be enough to get x86-like memory semantics.

IIRC, Apple M1 uses a similar technique to make sure Rosetta 2 can run translated x86 code without worrying about the memory model. However, M1's implementation can be switched at runtime, while Ztso is not. On the other hand, Ztso is standardized while M1's TSO is not.

Also, the text for Ztso mentions that SPARC uses TSO, just like x86. ARM however is indeed more relaxed.

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!

> Combine that with how cheap `std::mutex` is on most platforms and it's just really a last resort, at least on server-class gear.

Mere 10-20M std::mutex operations per second can bring a server to a total halt. CPU interconnects and CPU internal core-to-core buses are quickly saturated by required synchronization traffic.

So I wouldn't call it a particularly cheap operation. In fact, I can't think of many more expensive operations a CPU could perform. I guess just page walks and interrupts might qualify.

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.

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.

Ah I missed your comment when writing my sibling. Your comment is much more succinct while making the point at least as well if not better.

This is grossfully incorrect. Using sequential consistency on x86 does require extra expensive fence instructions.

What's free on x86 is acquire/release.

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.

CAS is pretty much tailored for read-modify-write (RMW) of atomically-sized data. ABA is an issue if it can result in the same bit pattern having a different meaning (thus, CAS is sometimes less intuitive than e.g. LL/SC), but there are plenty of cases where it is enough, even in a straightforward "composable" way.

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

Wait, wait, there can be even more confusion! IIRC nvidia’s Denver and Carmel Aarch64 cores, and one of Fujitsu’s, also uses TSO...

...so your tested Intel-to-ARM port might work just fine until run on a different vendor’s core!

POWER/PowerPC has a relaxed memory model, too.

Anyway this is another case where (hopefully) Rust shields the programmer from complexity. This stuff is very difficult to get correct and efficient.

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.