8 ms·

It's worth noting that for a lot of people for a long time, Intel TSO was the memory model in practice (which IIRC makes `std::memory_order_seq_cst` pretty much

It's worth noting that for a lot of people for a long time, Intel TSO was the memory model in practice (which IIRC makes `std::memory_order_seq_cst` pretty much free on Intel). Many clothes have been torn and many teeth gnashed porting C++ from Intel to more relaxed architectures. Back in the day that usually meant like SPARC, today that usually means ARM. "Acquire" and "Release" are relatively comprehensible in isolated examples, but the intuitions don't compose well. It's realllly easy to end up with an ABA type issue or an architecture dependency even with the simplest lock-free primitives like CAS. 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. Google engineers have more experience with this than probably anyone, and they've summed it up nicely here: https://abseil.io/docs/cpp/atomic_danger https://abseil.io/docs/cpp/atomic_danger. Doing raw atomics isn't quite "roll your own cryptography", but it's clearly in "if you have to ask, don't use it" territory. I've lost count of how many times I've fuzzed something to Mars and back to show it "correct" and not been able to justify it compared to `pthread` when the profiles were in. With that disclaimer, people are going to do it, and so I should probably leave an example of it done well: https://www.youtube.com/watch?v=HJ-719EGIts https://www.youtube.com/watch?v=HJ-719EGIts

tialaramex 4y ago
> 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...
- benreesman 4y ago
  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/__threading_support#L262 https://github.com/llvm-mirror/libcxx/blob/master/include/__... - https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=nptl/pthread_mutex_lock.c;hb=HEAD 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 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/synchronization/mutex.cc 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.
  - gpderetta 4y ago
    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.
    - benreesman 4y ago
      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
    - mgaunard 4y ago
      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.
vardump 4y ago
> 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.
- gpderetta 4y ago
  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.
  - benreesman 4y ago
    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.
- benreesman 4y ago
  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 https://gist.github.com/jboner/2841832.
sharikous 4y ago
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.
- benreesman 4y ago
  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/src/gauge.cc#L22 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.
ColonelPhantom 4y ago
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.
- benreesman 4y ago
  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 https://github.com/standardsemiconductor/lion, highly recommend!
an_d_rew 4y ago
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!
dataflow 4y ago
> 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.
- benreesman 4y ago
  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 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-golden-cove/ 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!
  - gpderetta 4y ago
    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.
zozbot234 4y ago
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.
- benreesman 4y ago
  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 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".
mgaunard 4y ago
This is grossfully incorrect. Using sequential consistency on x86 does require extra expensive fence instructions. What's free on x86 is acquire/release.
- benreesman 4y ago
  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.
  - deleted 4y ago
    [deleted]

tialaramex 4y ago

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

benreesman 4y ago
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/__threading_support#L262 https://github.com/llvm-mirror/libcxx/blob/master/include/__... - https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=nptl/pthread_mutex_lock.c;hb=HEAD 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 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/synchronization/mutex.cc 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.
- gpderetta 4y ago
  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.
  - benreesman 4y ago
    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
  - mgaunard 4y ago
    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.

vardump 4y ago

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

gpderetta 4y ago
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.
- benreesman 4y ago
  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.
benreesman 4y ago
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 https://gist.github.com/jboner/2841832.

sharikous 4y ago

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.

benreesman 4y ago
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/src/gauge.cc#L22 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.

ColonelPhantom 4y ago

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.

benreesman 4y ago
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 https://github.com/standardsemiconductor/lion, highly recommend!

an_d_rew 4y ago

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!

dataflow 4y ago

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

benreesman 4y ago
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 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-golden-cove/ 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!
- gpderetta 4y ago
  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.

zozbot234 4y ago

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.

benreesman 4y ago
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 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".

mgaunard 4y ago

This is grossfully incorrect. Using sequential consistency on x86 does require extra expensive fence instructions. What's free on x86 is acquire/release.

benreesman 4y ago
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.
- deleted 4y ago
  [deleted]