13 ms·

Atomics and Concurrency

145 points by LAC-Tech 1y ago

ozgrakkurt 1y ago
This is great, also looking for information about performance impact of using atomics like atomically reference counting etc. if anyone can recommend something to learn from
- cmrdporcupine 1y ago
  https://travisdowns.github.io/blog/2020/07/06/concurrency-costs.html https://travisdowns.github.io/blog/2020/07/06/concurrency-co...
- j_seigh 1y ago
  Performance from using atomics in reference counting is going to degrade quite a bit under heavy usage due to cache contention. If you are in that situation, you should be looking at something else like RCU or hazard Pointers.
  - tialaramex 1y ago
    Note that these strategies (collectively, "delayed reclamation") lose one benefit of the RAII concept. With Rust's Drop or C++ destructors we are guaranteed that when we don't need this Goat the clean-up-unused-goat code we wrote will run now - unlike with a Garbage Collector where that code either runs at some unspecified future time or not at all. Delayed reclamation means that "when we don't need this Goat" will sometimes be arbitrarily delayed after we apparently didn't need it, and it's no longer possible to say for sure by examining the program. This will almost always be a trade you're willing to make, but you need to know it exists, this is not a fun thing to discover while debugging.
    - zozbot234 1y ago
      With RCU the "we don't need this Goat" occurs as soon as the last readers are done with the earlier version of Goat, modulo a limited grace period in some RCU implementations. New readers always get the latest version, so there is no risk of waiting for an "unspecified" or "arbitrary" amount of time. Hazard pointers are a bit fiddlier AIUI, since the reclamation step must be triggered explicitly and verify that no hazard pointers exist to the object being reclaimed, so it is quite possible that you won't promptly reclaim the object.
      - tialaramex 1y ago
        From the point of view of any particular updater, the death of every current reader (who would keep the Goat alive) is arbitrary. Obviously in a real system it won't literally be unbounded, but I don't think it will usually make sense to work out how long that could take - in terms of clock cycles, or wall clock time, or any external metric - it won't necessarily be immediate but it will happen "eventually" and so just write software accordingly. Maybe I'm wrong for some reason and there is a practical limit in play for RCU but not Hazard Pointers, I don't think so though.
        PaulDavisThe1st 1y ago
        One of the central purposes of RCU is to decouple the updater/writer(s) from the reader(s). It doesn't matter to the writer if there is still a reader "out there" using the old version. And it likewise doesn't matter to (most) readers that the version they have is now old. What is delayed is the actual destruction/deallocation of the RCU-managed objects. Nobody cares about that delay unless the objects control limited resources (in which case, RCU is likely a bad fit) or there are so many objects and/or they are so large that the delay in deallocating them could cause memory pressure of some type.
        tialaramex 1y ago
        Sure, that's exactly my understanding.
    - manwe150 1y ago
      > we are guaranteed that when we don't need this Goat the clean-up-unused-goat code we wrote will run now Not to put too fine a point on things, but rust (and c++) very explicitly don’t guarantee this. They are both quite explicit about being allowed to leak memory and never free it (due to reference cycles), something a GC is not typically allowed to do. So yes it usually happens, it just is not guaranteed.
      - Maxatar 1y ago
        Your point that reference counting can result in memory leaks is absolutely correct and a worthwhile point. However, it's also worth pointing out that tracing garbage collectors like those used by Java are also allowed to leak memory and never free it. In the most extreme scenario you have the epsilon garbage collector, which leaks everything: https://openjdk.org/jeps/318 https://openjdk.org/jeps/318 Implementing a garbage collector that is guaranteed to free memory when it's actually no longer needed is equivalent to solving the halting problem (via Rice's theorem), and so any garbage collection algorithm is going to have to leak some memory, it's simply unavoidable.
      - tialaramex 1y ago
        All you're getting to is that we're not obliged in Rust to ever decide we didn't need the Goat - but I didn't argue that we are. The "finalizer problem" in the Garbage Collected languages isn't about a Goat which never becomes unused, it's about a situation where the Goat is unused but the clean-up never happens.
        j_seigh 1y ago
        You used quotes so I can't tell if you think it's a real problem or just a self inflicted one because the warning that finalizers aren't guaranteed to run was ignored. If the finalizer was for an object that is just memory, it's not a problem. The GC has decided it doesn't need to recover the memory used by that object just yet. I've seen this with heaps defined to be large enough to handle a memory spike. When the spikes stop happening, a lot of stuff in the old gen pool just stays there. At one point I was looking at 50GB heap dumps looking for memory leaks. It is a problem when the object has non memory resources like a socket descriptor. You can run out of descriptors. So not relying on GC and using try with resource is a good idea.
pythops 1y ago
For Rust, I highly recommend this book https://marabos.nl/atomics/ https://marabos.nl/atomics/
- reitzensteinm 1y ago
  This is such a great book, especially the section on operating system primitives, which made the book wider in scope and more practical. After all, you're probably not building exotic data structures by hand in memory without also needing high performance IO. It's been a hobby of mine to collect concurrency examples from books and blog posts and simulating them in Temper, my Rust memory model simulator. As far as I know, it's the largest Rust/C++11 memory model test suite on the internet (but I'm happy to be corrected). This is the file for Rust Atomics and Locks: https://github.com/reitzensteinm/temper/blob/main/memlog/tests/atomics_and_locks.rs https://github.com/reitzensteinm/temper/blob/main/memlog/tes... I didn't find any bugs in the examples, but with how good the book was, I didn't expect to :) The Williams book for C++ contains many of the same ideas (Rust's memory model is a copy/paste from C++11 without the now deprecated Consume) and I can highly recommend that too.
  - pythops 1y ago
    absolutely ! This book is useful for even non rust developers I think
- pimeys 1y ago
  Yes. This is how I learned the atomics and memory ordering. It's so much fun to read, and super interesting. Highly recommend!
tialaramex 1y ago
> TSan is a reliable way of detecting data races in your code, instead of trying to repeatedly run the code in a loop hoping for a data race to occur. I'm sure this doesn't intend to be misleading but I think it can mislead people anyway. TSan should detect races but just like "repeatedly run the code in a loop" it's not actually checking what you wrote doesn't have races, it's just reporting any which happened during testing. This is valuable - if you eliminate a race you've almost certainly fixed a real bug, maybe a very subtle bug you'd have cursed for years otherwise, but you can't use TSan to prove there are no further bugs of this kind. Tools to prove this stuff are often much harder to bring into a project, but you should put that work in if the difference between "It's probably fine" and "I proved it's correct" sounds necessary to you or for your work. I don't want my pacemaker to be "probably fine" but it's OK if the Youtube music player on my phone wasn't proved correct.
- dataflow 1y ago
  My (limited) understanding is that the way TSAN works is better than what you're comparing it to. You don't have to rerun TSAN in a loop to finally catch a race. As long as your test has coverage of that scenario (i.e. it executes the lines of interest once within a reasonable time window) it should get caught. Of course, being dynamic, it can't catch code that you never execute during testing, but that's not such a huge problem because you can verify code coverage through other means. It's quite a bit of a different from having to make stars align by looping until some e.g. rare timing issue comes up. The real issue here isn't that TSAN is low-confidence about absence of data races in C++. The issue is that even if it statically proved the absence of data races in the C++ sense, that still wouldn't imply that your algorithm is race-free. Because it's trivial to patch every single instance of a data race by using an atomic to get TSAN to shut up, but that in no way implies the higher-level concurrent algorithm works correctly. (e.g., if two threads perform an atomic load of some variable, then add one, then perform an atomic store back in, they would obviously stomp on each other, but TSAN wouldn't care.) It's more like a UB checker than a correctness verifier.
  - withoutboats3 1y ago
    The occurrence of data races depends on the specific non-deterministic sequence of execution of concurrent codepaths. Just because you have 100% code coverage does not mean you've covered every potential execution sequence, and its almost never practical to actually execute every possibility to ensure the absence of data races. Depending on the probability that your data race will occur, it could indeed be something you have to make stars align for TSAN to catch. Not to talk my own book, but there is a well-known alternative to C++ that can actually guarantee the absence of data races.
gpderetta 1y ago
Probably I'm missing something, but enqueue dereferences the current tail node. What prevents it dereferencing a node that has just been deleted by dequeue. Actually, nothing ever sets head so I'm not sure how anything is ever dequeued. Probably the implementation is incomplete and the queue needs a sentinel node somewhere.
john-h-k 1y ago
> The important thing to remember is that each of these cannot be split into separate instructions. Nitpick, but they absolutely can be split into several instructions, and this is the most common way it’s implemented on RISClike processors, and also single instructions aren’t necessarily atomic. The actual guarantee is that the entire operation (load, store, RMW, whatever) occurs in one “go” and no other thread can perform an operation on that variable during this atomic operation (it can’t write into the low byte of your variable as you read it). It’s probably best euphemismed by imagining that every atomic operation is just the normal operation wrapped in a mutex, but implemented in a much more efficient manner. Of course, with large enough types, Atomic variables may well be implemented via a mutex
- khrbtxyz 1y ago
  https://en.wikipedia.org/wiki/Load-link/store-conditional https://en.wikipedia.org/wiki/Load-link/store-conditional
- OskarS 1y ago
  > It’s probably best euphemismed by imagining that every atomic operation is just the normal operation wrapped in a mutex Sort-of, but that's not quite right: if you imagine it as "taking a mutex on the memory", there's a possibility of starvation. Imagine two threads repeatedly "locking" the memory location to update it. With a mutex, it's possible that one of them get starved, never getting to update the location, stalling indefinitely. At least x86 (and I'm sure ARM and RISC-V as well) make a much stronger progress guarantee than a mutex would: the operation is effectively wait-free. All threads are guaranteed to make progress in some finite amount of time, no one will be starved. At least, that's my understanding from reading much smarter people talking about the cache synchronization protocols of modern ISAs. Given that, I think a better mental model is roughly something like the article describes: the operation might be slower under high contention, but not "blocking" slow, it is guaranteed to finish in a finite amount of time and atomically ("in one combined operation").
  - john-h-k 1y ago
    x86 and modern ARM64 has instructions for this, but original ARM and RISC approaches are literally a hardware-assisted polling loop. Unsure what guarantees they make, I shall look. Definitely a good clarification though yeah, important
latchkey 1y ago
Previously: Atomics and Concurrency https://news.ycombinator.com/item?id=38964675 https://news.ycombinator.com/item?id=38964675 (January 11, 2024 — 106 points, 48 comments)
coolThingsFirst 1y ago
Amazing, i have decided to learn cpp for fun and wow the designers of the lang had serious gray matter. Binary search provided. Pair abstraction provided. Lower bound for binary search yup. Auto for type inference and fast as hell on top of it. Crazy powerful lang and also multiplayform threads.
- tialaramex 1y ago
  C++ auto isn't type inference, as so often in C++ it's something weirder which they call type deduction. In languages with type inference when it could be A or B and it's left to infer the type the compiler just always says it could be A or B, so the programmer needs to disambiguate. But with deduction in some cases C++ will deduce that you meant A even though you could instead have explicitly chosen B here instead, and too bad if you did mean B because that's not what it deduced.
  - coolThingsFirst 1y ago
    Can you show me some examples where the deduction is not the expected type?
    - tialaramex 1y ago
      Here's an easy to understand example https://cpp.godbolt.org/z/hTaPbM3a4 https://cpp.godbolt.org/z/hTaPbM3a4
miljanm 1y ago
Shared-Memory Synchronization by Michael L. Scott https://link.springer.com/book/10.1007/978-3-031-38684-8 https://link.springer.com/book/10.1007/978-3-031-38684-8

145 points by LAC-Tech 1y ago

This is great, also looking for information about performance impact of using atomics like atomically reference counting etc. if anyone can recommend something to learn from

cmrdporcupine 1y ago
https://travisdowns.github.io/blog/2020/07/06/concurrency-costs.html https://travisdowns.github.io/blog/2020/07/06/concurrency-co...
j_seigh 1y ago
Performance from using atomics in reference counting is going to degrade quite a bit under heavy usage due to cache contention. If you are in that situation, you should be looking at something else like RCU or hazard Pointers.
- tialaramex 1y ago
  Note that these strategies (collectively, "delayed reclamation") lose one benefit of the RAII concept. With Rust's Drop or C++ destructors we are guaranteed that when we don't need this Goat the clean-up-unused-goat code we wrote will run now - unlike with a Garbage Collector where that code either runs at some unspecified future time or not at all. Delayed reclamation means that "when we don't need this Goat" will sometimes be arbitrarily delayed after we apparently didn't need it, and it's no longer possible to say for sure by examining the program. This will almost always be a trade you're willing to make, but you need to know it exists, this is not a fun thing to discover while debugging.
  - zozbot234 1y ago
    With RCU the "we don't need this Goat" occurs as soon as the last readers are done with the earlier version of Goat, modulo a limited grace period in some RCU implementations. New readers always get the latest version, so there is no risk of waiting for an "unspecified" or "arbitrary" amount of time. Hazard pointers are a bit fiddlier AIUI, since the reclamation step must be triggered explicitly and verify that no hazard pointers exist to the object being reclaimed, so it is quite possible that you won't promptly reclaim the object.
    - tialaramex 1y ago
      From the point of view of any particular updater, the death of every current reader (who would keep the Goat alive) is arbitrary. Obviously in a real system it won't literally be unbounded, but I don't think it will usually make sense to work out how long that could take - in terms of clock cycles, or wall clock time, or any external metric - it won't necessarily be immediate but it will happen "eventually" and so just write software accordingly. Maybe I'm wrong for some reason and there is a practical limit in play for RCU but not Hazard Pointers, I don't think so though.
      - PaulDavisThe1st 1y ago
        One of the central purposes of RCU is to decouple the updater/writer(s) from the reader(s). It doesn't matter to the writer if there is still a reader "out there" using the old version. And it likewise doesn't matter to (most) readers that the version they have is now old. What is delayed is the actual destruction/deallocation of the RCU-managed objects. Nobody cares about that delay unless the objects control limited resources (in which case, RCU is likely a bad fit) or there are so many objects and/or they are so large that the delay in deallocating them could cause memory pressure of some type.
        tialaramex 1y ago
        Sure, that's exactly my understanding.
  - manwe150 1y ago
    > we are guaranteed that when we don't need this Goat the clean-up-unused-goat code we wrote will run now Not to put too fine a point on things, but rust (and c++) very explicitly don’t guarantee this. They are both quite explicit about being allowed to leak memory and never free it (due to reference cycles), something a GC is not typically allowed to do. So yes it usually happens, it just is not guaranteed.
    - Maxatar 1y ago
      Your point that reference counting can result in memory leaks is absolutely correct and a worthwhile point. However, it's also worth pointing out that tracing garbage collectors like those used by Java are also allowed to leak memory and never free it. In the most extreme scenario you have the epsilon garbage collector, which leaks everything: https://openjdk.org/jeps/318 https://openjdk.org/jeps/318 Implementing a garbage collector that is guaranteed to free memory when it's actually no longer needed is equivalent to solving the halting problem (via Rice's theorem), and so any garbage collection algorithm is going to have to leak some memory, it's simply unavoidable.
    - tialaramex 1y ago
      All you're getting to is that we're not obliged in Rust to ever decide we didn't need the Goat - but I didn't argue that we are. The "finalizer problem" in the Garbage Collected languages isn't about a Goat which never becomes unused, it's about a situation where the Goat is unused but the clean-up never happens.
      - j_seigh 1y ago
        You used quotes so I can't tell if you think it's a real problem or just a self inflicted one because the warning that finalizers aren't guaranteed to run was ignored. If the finalizer was for an object that is just memory, it's not a problem. The GC has decided it doesn't need to recover the memory used by that object just yet. I've seen this with heaps defined to be large enough to handle a memory spike. When the spikes stop happening, a lot of stuff in the old gen pool just stays there. At one point I was looking at 50GB heap dumps looking for memory leaks. It is a problem when the object has non memory resources like a socket descriptor. You can run out of descriptors. So not relying on GC and using try with resource is a good idea.

pythops 1y ago

For Rust, I highly recommend this book https://marabos.nl/atomics/ https://marabos.nl/atomics/

reitzensteinm 1y ago
This is such a great book, especially the section on operating system primitives, which made the book wider in scope and more practical. After all, you're probably not building exotic data structures by hand in memory without also needing high performance IO. It's been a hobby of mine to collect concurrency examples from books and blog posts and simulating them in Temper, my Rust memory model simulator. As far as I know, it's the largest Rust/C++11 memory model test suite on the internet (but I'm happy to be corrected). This is the file for Rust Atomics and Locks: https://github.com/reitzensteinm/temper/blob/main/memlog/tests/atomics_and_locks.rs https://github.com/reitzensteinm/temper/blob/main/memlog/tes... I didn't find any bugs in the examples, but with how good the book was, I didn't expect to :) The Williams book for C++ contains many of the same ideas (Rust's memory model is a copy/paste from C++11 without the now deprecated Consume) and I can highly recommend that too.
- pythops 1y ago
  absolutely ! This book is useful for even non rust developers I think
pimeys 1y ago
Yes. This is how I learned the atomics and memory ordering. It's so much fun to read, and super interesting. Highly recommend!

tialaramex 1y ago

> TSan is a reliable way of detecting data races in your code, instead of trying to repeatedly run the code in a loop hoping for a data race to occur. I'm sure this doesn't intend to be misleading but I think it can mislead people anyway. TSan should detect races but just like "repeatedly run the code in a loop" it's not actually checking what you wrote doesn't have races, it's just reporting any which happened during testing. This is valuable - if you eliminate a race you've almost certainly fixed a real bug, maybe a very subtle bug you'd have cursed for years otherwise, but you can't use TSan to prove there are no further bugs of this kind. Tools to prove this stuff are often much harder to bring into a project, but you should put that work in if the difference between "It's probably fine" and "I proved it's correct" sounds necessary to you or for your work. I don't want my pacemaker to be "probably fine" but it's OK if the Youtube music player on my phone wasn't proved correct.

dataflow 1y ago
My (limited) understanding is that the way TSAN works is better than what you're comparing it to. You don't have to rerun TSAN in a loop to finally catch a race. As long as your test has coverage of that scenario (i.e. it executes the lines of interest once within a reasonable time window) it should get caught. Of course, being dynamic, it can't catch code that you never execute during testing, but that's not such a huge problem because you can verify code coverage through other means. It's quite a bit of a different from having to make stars align by looping until some e.g. rare timing issue comes up. The real issue here isn't that TSAN is low-confidence about absence of data races in C++. The issue is that even if it statically proved the absence of data races in the C++ sense, that still wouldn't imply that your algorithm is race-free. Because it's trivial to patch every single instance of a data race by using an atomic to get TSAN to shut up, but that in no way implies the higher-level concurrent algorithm works correctly. (e.g., if two threads perform an atomic load of some variable, then add one, then perform an atomic store back in, they would obviously stomp on each other, but TSAN wouldn't care.) It's more like a UB checker than a correctness verifier.
- withoutboats3 1y ago
  The occurrence of data races depends on the specific non-deterministic sequence of execution of concurrent codepaths. Just because you have 100% code coverage does not mean you've covered every potential execution sequence, and its almost never practical to actually execute every possibility to ensure the absence of data races. Depending on the probability that your data race will occur, it could indeed be something you have to make stars align for TSAN to catch. Not to talk my own book, but there is a well-known alternative to C++ that can actually guarantee the absence of data races.

gpderetta 1y ago

Probably I'm missing something, but enqueue dereferences the current tail node. What prevents it dereferencing a node that has just been deleted by dequeue. Actually, nothing ever sets head so I'm not sure how anything is ever dequeued. Probably the implementation is incomplete and the queue needs a sentinel node somewhere.

john-h-k 1y ago

> The important thing to remember is that each of these cannot be split into separate instructions. Nitpick, but they absolutely can be split into several instructions, and this is the most common way it’s implemented on RISClike processors, and also single instructions aren’t necessarily atomic. The actual guarantee is that the entire operation (load, store, RMW, whatever) occurs in one “go” and no other thread can perform an operation on that variable during this atomic operation (it can’t write into the low byte of your variable as you read it). It’s probably best euphemismed by imagining that every atomic operation is just the normal operation wrapped in a mutex, but implemented in a much more efficient manner. Of course, with large enough types, Atomic variables may well be implemented via a mutex

khrbtxyz 1y ago
https://en.wikipedia.org/wiki/Load-link/store-conditional https://en.wikipedia.org/wiki/Load-link/store-conditional
OskarS 1y ago
> It’s probably best euphemismed by imagining that every atomic operation is just the normal operation wrapped in a mutex Sort-of, but that's not quite right: if you imagine it as "taking a mutex on the memory", there's a possibility of starvation. Imagine two threads repeatedly "locking" the memory location to update it. With a mutex, it's possible that one of them get starved, never getting to update the location, stalling indefinitely. At least x86 (and I'm sure ARM and RISC-V as well) make a much stronger progress guarantee than a mutex would: the operation is effectively wait-free. All threads are guaranteed to make progress in some finite amount of time, no one will be starved. At least, that's my understanding from reading much smarter people talking about the cache synchronization protocols of modern ISAs. Given that, I think a better mental model is roughly something like the article describes: the operation might be slower under high contention, but not "blocking" slow, it is guaranteed to finish in a finite amount of time and atomically ("in one combined operation").
- john-h-k 1y ago
  x86 and modern ARM64 has instructions for this, but original ARM and RISC approaches are literally a hardware-assisted polling loop. Unsure what guarantees they make, I shall look. Definitely a good clarification though yeah, important

latchkey 1y ago

Previously: Atomics and Concurrency https://news.ycombinator.com/item?id=38964675 https://news.ycombinator.com/item?id=38964675 (January 11, 2024 — 106 points, 48 comments)

coolThingsFirst 1y ago

Amazing, i have decided to learn cpp for fun and wow the designers of the lang had serious gray matter. Binary search provided. Pair abstraction provided. Lower bound for binary search yup. Auto for type inference and fast as hell on top of it. Crazy powerful lang and also multiplayform threads.

tialaramex 1y ago
C++ auto isn't type inference, as so often in C++ it's something weirder which they call type deduction. In languages with type inference when it could be A or B and it's left to infer the type the compiler just always says it could be A or B, so the programmer needs to disambiguate. But with deduction in some cases C++ will deduce that you meant A even though you could instead have explicitly chosen B here instead, and too bad if you did mean B because that's not what it deduced.
- coolThingsFirst 1y ago
  Can you show me some examples where the deduction is not the expected type?
  - tialaramex 1y ago
    Here's an easy to understand example https://cpp.godbolt.org/z/hTaPbM3a4 https://cpp.godbolt.org/z/hTaPbM3a4

miljanm 1y ago

Shared-Memory Synchronization by Michael L. Scott https://link.springer.com/book/10.1007/978-3-031-38684-8 https://link.springer.com/book/10.1007/978-3-031-38684-8