13 ms·

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

129 points by greghn 4y ago

blasrodri 4y ago
What a great article. I have been trying to compile some examples here https://github.com/blasrodri/atomic-story https://github.com/blasrodri/atomic-story Will try to extend it a bit more based on what I've learned from this text
jcalvinowens 4y ago
I've always hated the modern C++ atomic stuff. Atomicity is not a property of the thing being accessed, it is a property of the instructions performing the access: trying to shoehorn that reality into an object-based model was wrong from the beginning. A library of fence primitives is much easier to work with and understand, IMHO. [1] is the best example I know of. If you've never tried to write code that way, have a crack at it: you'll definitely learn something. I think lots of programmers struggle to understand memory ordering because the C++ model makes it so much more difficult to understand than it really is. When you actually deal with the fences directly, everything makes a lot more sense. Also, the word "atomic" is unfortunately really overloaded. Nearly all X86 instructions are "atomic" with aligned pointers, in the sense that the result of two racing MOV instructions will be one or the other value, not some corrupt combination of the two. [1] https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt
- gpderetta 4y ago
  I for one vastly prefer fenced operations as opposed to separate fences. The synchronizes-with model is much easier to understand than anything reordering based. Also it is nice that the typesystem helps making sure that atomic things are handled atomically. When it is not enough now there is atomic_ref.
  - jcalvinowens 4y ago
    > The synchronizes-with model is much easier to understand than anything reordering based. Why do you think that?
    - gpderetta 4y ago
      Empirically it is much easier to reason about and be confident of the correctness of the result, at least to me and to many people I have discussed the matter with. I find it easier to reason in term of DAGs instead of all possible interleaved executions. The DAGs are stil dynamic and execution dependent, but you have to consider less combinations. One you know that some algorithm violates the happen before relation is easy to go back and find the reordering that would cause it.
deleted 4y ago
[deleted]
Koshkin 4y ago
> C++ And using pointers instead of references.
- wudangmonk 4y ago
  yes? what am I missing here?. I've always prefered pointers in my c++ code.
  - dxuh 4y ago
    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.
    - pizza 4y ago
      I am not familiar with the capabilities of the compiler but is there any optimization reason to prefer references as well? Like the compiler may be able to figure out an efficient way to keep a referenced object ‘nearby’ for subsequent function calls that also refer to the object, maybe in some register or reordering which code gets run when. Whereas sometimes the compiler might not be able to do something like that with a pointer, incurring mem access costs. Hm slightly tangential but could you install some kind of page-fault handler on a reference such that the control flow jumps on write back to the last place it was accessed? Not that you’d want to do that in the real world, but it would be an interesting “pub-sub” type control flow..
      - Sharlin 4y ago
        In C++, there are no differences between pointer and reference semantics except that the former are a) nullable and b) reseatable (can be changed to point to something else).
    - amalcon 4y ago
      The other major use-case is where other code constrains you, e.g. it's being passed as a callback to a C library. There are also a number of cases where passing a pointer into a template function can be more concise. E.g. since pointers are iterators, if you have a generic function that iterates over things and you just want it to look at one thing (or zero) for testing, you can usually do this with pointer arithmetic.
Sharlin 4y ago
For a somewhat less "for dummies" treatment of the C++ memory model, see Herb Sutter's classic talk "atomic<> Weapons" [1]. [1] https://www.youtube.com/watch?v=A8eCGOqgvH4 https://www.youtube.com/watch?v=A8eCGOqgvH4
- dragontamer 4y ago
  This is a good talk. A good set of blogposts is Preshing as well: https://preshing.com/20120710/memory-barriers-are-like-source-control-operations/ https://preshing.com/20120710/memory-barriers-are-like-sourc... https://preshing.com/20120913/acquire-and-release-semantics/ https://preshing.com/20120913/acquire-and-release-semantics/ (etc. etc. Preshing wrote a lot on this subject, browse the blog) Not quite on C++ atomics or the C++11 concurrency model. But more of generic discussion on this extremely complex subject.
- dataflow 4y ago
  Turns out the C++ memory model has some issues that came to light after that talk. See https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0668r5.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p06...
benreesman 4y ago
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.

129 points by greghn 4y ago

What a great article. I have been trying to compile some examples here https://github.com/blasrodri/atomic-story https://github.com/blasrodri/atomic-story Will try to extend it a bit more based on what I've learned from this text

jcalvinowens 4y ago

I've always hated the modern C++ atomic stuff. Atomicity is not a property of the thing being accessed, it is a property of the instructions performing the access: trying to shoehorn that reality into an object-based model was wrong from the beginning. A library of fence primitives is much easier to work with and understand, IMHO. [1] is the best example I know of. If you've never tried to write code that way, have a crack at it: you'll definitely learn something. I think lots of programmers struggle to understand memory ordering because the C++ model makes it so much more difficult to understand than it really is. When you actually deal with the fences directly, everything makes a lot more sense. Also, the word "atomic" is unfortunately really overloaded. Nearly all X86 instructions are "atomic" with aligned pointers, in the sense that the result of two racing MOV instructions will be one or the other value, not some corrupt combination of the two. [1] https://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt

gpderetta 4y ago
I for one vastly prefer fenced operations as opposed to separate fences. The synchronizes-with model is much easier to understand than anything reordering based. Also it is nice that the typesystem helps making sure that atomic things are handled atomically. When it is not enough now there is atomic_ref.
- jcalvinowens 4y ago
  > The synchronizes-with model is much easier to understand than anything reordering based. Why do you think that?
  - gpderetta 4y ago
    Empirically it is much easier to reason about and be confident of the correctness of the result, at least to me and to many people I have discussed the matter with. I find it easier to reason in term of DAGs instead of all possible interleaved executions. The DAGs are stil dynamic and execution dependent, but you have to consider less combinations. One you know that some algorithm violates the happen before relation is easy to go back and find the reordering that would cause it.

deleted 4y ago

[deleted]

Koshkin 4y ago

> C++ And using pointers instead of references.

wudangmonk 4y ago
yes? what am I missing here?. I've always prefered pointers in my c++ code.
- dxuh 4y ago
  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.
  - pizza 4y ago
    I am not familiar with the capabilities of the compiler but is there any optimization reason to prefer references as well? Like the compiler may be able to figure out an efficient way to keep a referenced object ‘nearby’ for subsequent function calls that also refer to the object, maybe in some register or reordering which code gets run when. Whereas sometimes the compiler might not be able to do something like that with a pointer, incurring mem access costs. Hm slightly tangential but could you install some kind of page-fault handler on a reference such that the control flow jumps on write back to the last place it was accessed? Not that you’d want to do that in the real world, but it would be an interesting “pub-sub” type control flow..
    - Sharlin 4y ago
      In C++, there are no differences between pointer and reference semantics except that the former are a) nullable and b) reseatable (can be changed to point to something else).
  - amalcon 4y ago
    The other major use-case is where other code constrains you, e.g. it's being passed as a callback to a C library. There are also a number of cases where passing a pointer into a template function can be more concise. E.g. since pointers are iterators, if you have a generic function that iterates over things and you just want it to look at one thing (or zero) for testing, you can usually do this with pointer arithmetic.

Sharlin 4y ago

For a somewhat less "for dummies" treatment of the C++ memory model, see Herb Sutter's classic talk "atomic<> Weapons" [1]. [1] https://www.youtube.com/watch?v=A8eCGOqgvH4 https://www.youtube.com/watch?v=A8eCGOqgvH4

dragontamer 4y ago
This is a good talk. A good set of blogposts is Preshing as well: https://preshing.com/20120710/memory-barriers-are-like-source-control-operations/ https://preshing.com/20120710/memory-barriers-are-like-sourc... https://preshing.com/20120913/acquire-and-release-semantics/ https://preshing.com/20120913/acquire-and-release-semantics/ (etc. etc. Preshing wrote a lot on this subject, browse the blog) Not quite on C++ atomics or the C++11 concurrency model. But more of generic discussion on this extremely complex subject.
dataflow 4y ago
Turns out the C++ memory model has some issues that came to light after that talk. See https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0668r5.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p06...

benreesman 4y ago

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.