6 ms·

Keep in mind lockless algorithms are not necessarily more scalable than lock-based algorithms, usually have higher constant overheads, and are significantly eas

Keep in mind lockless algorithms are not necessarily more scalable than lock-based algorithms, usually have higher constant overheads, and are significantly easier to get wrong. However, this post is, in part, about how to implement locks.

taneq 9y ago
> However, this post is, in part, about how to implement locks. I haven't read the article in-depth but yeah, it seems like it maybe would have been better titled "What every C++ systems programmer should know about std::atomic". Which is still cool but from the title I was expecting some fancy voodoo algorithms for threadsafe non-locking FIFO queues or something.
- buserror 9y ago
  Completely agree with this, the topic is much wider than the meat of the paper. A bit of a clickbait here.
- banachtarski 9y ago
  I think it's meant to be pretty fundamental. It's not supposed to include "voodoo algorithms" because it literally says "what every systems programmer should know...". The voodoo algorithm is a voodoo algorithm because not everyone needs to know it. In contrast, a mutex and all of that stuff is a consequence of how memory sequencing on a CPU works. If you understand those concepts, the rest is a hop, skip, and a jump away.
  - taneq 9y ago
    I guess my beef was mostly in response to the word "lockless", which I'd hoped meant "not using any wait-for-other-thread type semantics" but in this context seems to mean "implementing locking without using OS-provided locking primitives, although standard library is fine." I was hoping that there was some cool new trick I'd missed or fundamentally different way to do concurrency than locking. I get disappointed easily in cases like this. :/
- johndubchak 9y ago
  I think that might be what parts of this upcoming release might contain: https://www.amazon.com/C-Concurrency-Action-Anthony-Williams/dp/1617294691/ref=sr_1_2?ie=UTF8&qid=1509644435&sr=8-2&keywords=Anthony+Williams+C%2B%2B+Concurrency+in+Action https://www.amazon.com/C-Concurrency-Action-Anthony-Williams...
- Animats 9y ago
  Me too. If you can do lockless add-to-queue and remove-from-queue, that's valuable. It's hard to get that right, especially on non x86/amd64 platforms. Every network packet, and often every interrupt, goes through a queue operation like that. Not stalling the other CPUs on each interrupt is important.
banachtarski 9y ago
I think it's worth thinking in terms of the probability of contention per cycle. If the odds of contention is very low, lock-free will be much better (imagine accessing a shared data structure which is vast compared to the range of usage in a typical use). Also, I think it's worth noting that it's really not that much more complicated than a simple mutex if you use the default sequential consistency memory order on an atomic. When you start attempting to optimize around certain patterns using the weaker memory orders, yea, things get a lot tougher.
- yason 9y ago
  If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer. I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.
  - banachtarski 9y ago
    Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.
    - gpderetta 9y ago
      Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
sdenton4 9y ago
As the text puts it: "And as always, consider the tradeoffs you make between complexity and performance. Lockless programming is a perilous activity with a proud tradition of code that is ever so subtly wrong."
saas_co_de 9y ago
Lock-free using CAS type operations looks good in theory but having to do a cache flush for every atomic operation really bogs things down when you get into complex algorithms so the simple lock ends up being cheaper. An alternative lock-free approach is to segmented memory between threads and then coordinate between threads using messages passed with ring buffers. This can be done entirely without atomic operations but hits other scaling problems and is also extremely difficult to implement so probably not widely applicable.
- gpderetta 9y ago
  CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).
  - dragontamer 9y ago
    > CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Perhaps "Cache Flush" is the wrong word, but as long as cores are forced to communicate, you're going to get a performance penalty. I know when you do a simple atomic_increment on x86_64 platforms, things can be 2x slower at a minimum than a non-atomic increment. "Cache Coherence" simply means that the CPU handles all of those edge cases for you. But it still needs to be handled, and that entails a performance penalty. If you have a 4-core / 8-thread machine (Like a recent Intel i7), its faster to have 8-Non Atomic counters that are added up at the end... rather than to have 1-atomic counter with 8-threads doing atomic-increment on it. ---------------- Any core that modifies a memory location invalidates the cache for all other cores. (ie: Core 1 does atomic_inc(x), implies that Core2/Core3/Core4 all have an invalid value of "x". So atomic_inc(x) causes a cache-flush on Core2/Core3/Core4) Again, I'm not an expert, but that's my understanding of how modern systems work. ------- I looked up the Intel Architecture Manual, and they have the following table: https://imgur.com/uesh8co https://imgur.com/uesh8co If the data is in another core's L1 cache, the latency increases dramatically, especially on a "Dirty Hit". (ie: Core1 is trying to read "x", but Core3 is telling the other cores that "x" has changed) In effect, its more efficient for an Intel CPU to access something from L3 cache than for it to access a "Dirty" value from another core. Heck, based on these numbers, even a "Clean" hit is more costly than using the L3 cache!
deleted 9y ago
[deleted]

taneq 9y ago

> However, this post is, in part, about how to implement locks. I haven't read the article in-depth but yeah, it seems like it maybe would have been better titled "What every C++ systems programmer should know about std::atomic". Which is still cool but from the title I was expecting some fancy voodoo algorithms for threadsafe non-locking FIFO queues or something.

buserror 9y ago
Completely agree with this, the topic is much wider than the meat of the paper. A bit of a clickbait here.
banachtarski 9y ago
I think it's meant to be pretty fundamental. It's not supposed to include "voodoo algorithms" because it literally says "what every systems programmer should know...". The voodoo algorithm is a voodoo algorithm because not everyone needs to know it. In contrast, a mutex and all of that stuff is a consequence of how memory sequencing on a CPU works. If you understand those concepts, the rest is a hop, skip, and a jump away.
- taneq 9y ago
  I guess my beef was mostly in response to the word "lockless", which I'd hoped meant "not using any wait-for-other-thread type semantics" but in this context seems to mean "implementing locking without using OS-provided locking primitives, although standard library is fine." I was hoping that there was some cool new trick I'd missed or fundamentally different way to do concurrency than locking. I get disappointed easily in cases like this. :/
johndubchak 9y ago
I think that might be what parts of this upcoming release might contain: https://www.amazon.com/C-Concurrency-Action-Anthony-Williams/dp/1617294691/ref=sr_1_2?ie=UTF8&qid=1509644435&sr=8-2&keywords=Anthony+Williams+C%2B%2B+Concurrency+in+Action https://www.amazon.com/C-Concurrency-Action-Anthony-Williams...
Animats 9y ago
Me too. If you can do lockless add-to-queue and remove-from-queue, that's valuable. It's hard to get that right, especially on non x86/amd64 platforms. Every network packet, and often every interrupt, goes through a queue operation like that. Not stalling the other CPUs on each interrupt is important.

banachtarski 9y ago

I think it's worth thinking in terms of the probability of contention per cycle. If the odds of contention is very low, lock-free will be much better (imagine accessing a shared data structure which is vast compared to the range of usage in a typical use). Also, I think it's worth noting that it's really not that much more complicated than a simple mutex if you use the default sequential consistency memory order on an atomic. When you start attempting to optimize around certain patterns using the weaker memory orders, yea, things get a lot tougher.

yason 9y ago
If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer. I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.
- banachtarski 9y ago
  Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.
  - gpderetta 9y ago
    Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.

sdenton4 9y ago

As the text puts it: "And as always, consider the tradeoffs you make between complexity and performance. Lockless programming is a perilous activity with a proud tradition of code that is ever so subtly wrong."

saas_co_de 9y ago

Lock-free using CAS type operations looks good in theory but having to do a cache flush for every atomic operation really bogs things down when you get into complex algorithms so the simple lock ends up being cheaper. An alternative lock-free approach is to segmented memory between threads and then coordinate between threads using messages passed with ring buffers. This can be done entirely without atomic operations but hits other scaling problems and is also extremely difficult to implement so probably not widely applicable.

gpderetta 9y ago
CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).
- dragontamer 9y ago
  > CAS don't do cache flushes. Caches are fully coherent so they never enter into the window in any lock-free algorithms. Perhaps "Cache Flush" is the wrong word, but as long as cores are forced to communicate, you're going to get a performance penalty. I know when you do a simple atomic_increment on x86_64 platforms, things can be 2x slower at a minimum than a non-atomic increment. "Cache Coherence" simply means that the CPU handles all of those edge cases for you. But it still needs to be handled, and that entails a performance penalty. If you have a 4-core / 8-thread machine (Like a recent Intel i7), its faster to have 8-Non Atomic counters that are added up at the end... rather than to have 1-atomic counter with 8-threads doing atomic-increment on it. ---------------- Any core that modifies a memory location invalidates the cache for all other cores. (ie: Core 1 does atomic_inc(x), implies that Core2/Core3/Core4 all have an invalid value of "x". So atomic_inc(x) causes a cache-flush on Core2/Core3/Core4) Again, I'm not an expert, but that's my understanding of how modern systems work. ------- I looked up the Intel Architecture Manual, and they have the following table: https://imgur.com/uesh8co https://imgur.com/uesh8co If the data is in another core's L1 cache, the latency increases dramatically, especially on a "Dirty Hit". (ie: Core1 is trying to read "x", but Core3 is telling the other cores that "x" has changed) In effect, its more efficient for an Intel CPU to access something from L3 cache than for it to access a "Dirty" value from another core. Heck, based on these numbers, even a "Clean" hit is more costly than using the L3 cache!

deleted 9y ago

[deleted]