15 ms·

A flexible, lightweight, spin-lock barrier

83 points by kencausey 5y ago

atq2119 5y ago
It's a nice write up. I did this once with a slight modification. The phase really only needs one bit, and an arbitrary number of threads can be supported in a number of ways by having the last thread to arrive at the barrier clean up the state based on a second word that holds the number of threads. For example, compare the thread counter part of the "v" value to the number of threads. If equal, do an atomic store which writes the opposite phase with a thread count of 0. If not equal, spin until the phase bit changes. This approach avoids a division and can support threads that leave the barrier entirely. (And theoretically also entering the barrier, but that's always dicey regardless of the barrier implementation.)
- gpderetta 5y ago
  So, I understand that the difficulty is being able to reset the barrier without a quiescent period. It seems to me that a counter being able to count to n is enough and there is no need of an explicit phase bit: Wait(int *b, int n): 1: x = *b if (x == n-1) *b=0 //last, reset else if cas(b, x, x+1) 2: if *b goto 2 else goto 1
  - atq2119 5y ago
    Your spin loop could easily miss the time during which *b == 0. The article explains that. A separate phase bit is required.
    - gpderetta 5y ago
      Yes. I see it now.
dragontamer 5y ago
Hmmmm. A lot of the "difficult parts" of the barrier is the synchronization / memory-barrier part (not the same as a spin-lock barrier. Ugggh, we need someone to revamp the language of low-level multiprocessor programming). Anyway, the memory-barrier part is "solved" by using atomics and then handwaving all the loads/stores as sequentially-consistent. Yeah, that works, but would lead to subpar performance on all systems, as x86 has total-store ordering (less powerful than sequentially consistent), so x86-compilers would probably need to emit a memory barrier. ARM / POWER8/POWER9/POWER10 systems are "even weaker", so they need an even more powerful barrier to be emitted by the compiler. ------- There's also the "Hyperthread yield" instruction that should be placed somehwere in POWER/x86 systems. (Most ARM systems largely don't have hyperthreads/SMT, but the ARM E2 does...). Without "hyperthread yield", the pipeline is going to be uselessly full of load/store instructions from this tight inner-loop. EDIT: I had to search for it, but I now know the name of the instruction on x86. "PAUSE" is the hyperthread-yield instruction. https://www.felixcloutier.com/x86/pause https://www.felixcloutier.com/x86/pause You may be "livelock starving" your brother-hyperthread because your current thread is using up all of the pipeline / decoding bandwidth. By using "hyperthread yield", your code will use the minimum amount of decoding bandwidth. ----- The article does talk about memory-barriers, but seems to be missing the discussion on hyperthread yield. So its probably not "as efficient" as it could get yet. I can believe that the implementation works as discussed in the blogpost. But its still yet incomplete: a faster implementation probably exists, maybe not with "Fully Relaxed" atomics, but probably with acquire/release atomics (which are free on x86, and significantly faster on ARM/POWER9 than seq-cst atomics). Note: ARM8+ and POWER9+ now have load-acquire and store-release instructions, serving as an intermediate performance between fully relaxed atomics and seq-cst atomics. (These instructions may have existed earlier, but I know for sure they're in the modern version of these chips). Once acquire/release barriers are figured out in the right location, the use of hyperthread-yield on x86 and POWER systems would be best on highly-loaded systems. I'm not sure how to test the efficacy / throughput of hyperthread-yield however, I only know of its theoretical benefits. Coming up with a good test (to make sure we're actually improving performance) is itself a difficult question. TL;DR: Good first pass implementation, and good discussion to get things started. But there's still a long way before I consider it a top-end implementation! For many projects, what is seen here is probably sufficient (especially professional projects where you need to move onto some other programming task). But a hobby project could keep optimizing a bit longer to squeeze out a few more cycles of efficiency here. Coming up with a test to ensure the acquire-release is properly done is also somewhat difficult, and would require ARM / POWER hardware.
- gpderetta 5y ago
  It seems to me that a barrier primitive needs at the very least acq+rel semantics [1], which means that TSO implicit acquire and release are neither necessary nor sufficient[2]. In practice on x86 this means an atomic RMW which is seq-cst. I'm not familiar enough with ARM/Power to know if acq+rel is significantly faster than seq cst. [1] See the Laws of Orders paper. [2] without using asymmetric synchronization which is not appropriate for a general purpose barrier.
  - dragontamer 5y ago
    I admit that I'm not 100% perfect with the various memory models at play here. But my understanding is... 1. Seq-cst -- Strongest/slowest. (Aka: Java volatile) 2. Total Store order (aka: x86) 3. Acq-Release (aka: newer-ARM / newer-POWER) 4. Acq-Consume (aka: old-ARM / old-Power) 5. Relaxed -- Weakest/fastest, DEC Alpha. That is to say, acquire-release is often compiled into no-op on x86, because x86 Total-store ordering is "stronger" than acquire-release. Acquire-Consume was thought to be sufficient, but C++11 debate argued otherwise, and designed a stronger Acquire-release model. ARM/POWER designers then implemented acquire-release model. -------- I understand that things aren't perfectly linear, and that at the lower level the discussion is about read/read, read/write, write/read, and write/write barriers. But my brain has never really grok'd this level of detail. (Instead, I think in terms of the simplified list above). So please correct me if I'm wrong with the above assumptions.
    - gpderetta 5y ago
      An acquire+release fence is equivalent to two indivisible acquire and release fences but can't be implemented by simply issuing the two fences in isolation, as they would be unordered with each other. x86 has no native acq+relase fence and it can't be simulated, for example, with a load plus a store (i.e. separate acquire and release fences), but you need an mfence or atomic rmw. ARM and power do allow for indipendent reads of indipendent writes (or maybe only power) so in principle an acq+rel fence could be cheaper than a full seqctst one, although I don't know if it is in practice.
ativzzz 5y ago
This seems very similar to the centralized counting barrier described in [1] where each thread, upon hitting the barrier, decrements the count and spins until a global "sense" boolean is reversed. The last thread to hit the barrier, resets the counter and flips the "sense" freeing up all other threads. I guess the difference is this one treats the bool as odd/even values of an integer, but does that work for n_threads > 2? [1]http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf http://web.mit.edu/6.173/www/currentsemester/readings/R06-sc...
- hinkley 5y ago
  These boolean arrangements ("flipping") fail when the number of watchers is high and the interval is small. The toggle can switch twice while you're queued to be run again, and then all bets are off, because it looks to you like nothing has happened. Your messaging rate can only be half of the frequency guaranteed by the kernel for waking every thread. And many OSes offer no ironclad guarantee.
  - ativzzz 5y ago
    How? Only one thread, the last one when the counter is 0, flips the switch. Before the switch is flipped, the counter is reset, so the next flip will only happen when every thread once again hits the next barrier and the counter decrements to 0.
    - hinkley 5y ago
      State observed by thread 1: counter = 5, state = blue; State observed by threads 2-4: counter = [4,5,1,2,3,4,5,6], state = [blue, green, blue] Thread 1 wakes up, sees counter = 6, state = blue; Logical conclusion: system state is counter++, state unchanged. Actual scenario: counter+=6, state+=2 I believe this was first covered in my distributed computing class, but was probably most concretely illustrated in the case of concurrent garbage collection. Any unfairness in the thread scheduler can lead to some threads getting way more clock cycles than others. In low frequency scenarios you can convince yourself it's not a problem, only to be punished by success into finding out you're wrong when you have 10,000 active users instead of 10. This is especially true with spinlocks, because it's a greedy algorithm that trades fairness for responsiveness. It can result in low throughput or even priority inversion. They are a very sharp knife. Indispensable for very specific tasks, certain bloodshed for others.
MaxGanzII 5y ago
I may be wrong, but I don't see this working in theory. The basic problem is that for any physical core, there is no guarantee that any writes will ever be seen by any other core (unless the necessary extra magic is done to make this so). (There's a matching problem when reading, too, in that in theory writes made by another core can be never seen by the reading core, even if they have reached the domain covered by cache coherency, unless the necessary extra magic, etc.) So here with this code, in theory, the writes being made simply are never seen by another core, and so it doesn't work. As it is, in practise, writes typically make their way to other physical cores in a reasonably short time, whether or not the extra magic is performed; but this is not guaranteed. Also of course the ordering of the emergence of those writes is not guaranteed (although on some platforms, additional guarantees are provided - Intel is particular generous in this regard, and performance suffers because of it).
- dragontamer 5y ago
  > The basic problem is that for any physical core, there is no guarantee that any writes will ever be seen by any other core (unless the necessary extra magic is done to make this so). They're using atomic read/writes with sequential-consistency. This means that the compiler will automatically put memory-barriers in the appropriate locations to guarantee sequential-consistency, but probably at a significant performance cost. The implementation is likely correct, but its the slowest performance available (seq-cst is the simplest / most braindead atomic operation, but slowest because you probably don't need all those memory barriers). I'd expect that Acq-release style barriers is possible for this use case, which would be faster on x86, POWER, and ARM systems.
  - MaxGanzII 5y ago
    > They're using atomic read/writes with sequential-consistency. In the C11 code? I'm not up to speed with that version of the spec, but unless there is behaviour invoked by the use of _Atomic, the code looks to me to be performing normal, non-atomic read/writes. Another reply says there are full barriers being automatically used, but that doesn't address the problem I've described.
api 5y ago
Be careful with spin locks. We used to have one in the ZeroTier core. We pulled it due to a crazy insane bug where it would hang on single core machines and another one where it would run away on CPU usage on massively multicore machines. These bugs had the same cause. Think about it. Don't use spin locks unless you have profiled and have a clear understanding of the contention factors involved. Also be sure to test on single core and massively multicore. Also look at whether you can use atomics. Atomics are better than lock guarded things in almost every way. The only time locks beat atomics is when you are updating a bunch of things in which case it may be faster to lock once than to update 10 atomic variables. Message passing can also win sometimes over concurrent access even if it involves more copying. Profile and think.
- PaulDavisThe1st 5y ago
  > The only time locks beat atomics is when you are updating a bunch of things in which case it may be faster to lock once than to update 10 atomic variables. Locks are mandatory when you're updating data that does not fit into a single atomic type. You cannot use N atomics to create atomic update of a data structure that must be semantically atomic across its N members.
  - gpderetta 5y ago
    Technically any algorithm can be implemented in a lock free way and there are n-way CAS constructs that indeed allow updating N memory locations atomically. In practice they are very slow.
    - atq2119 5y ago
      You can use RCU to do this, but I'd argue that everything else ends up being more or less a lock by another name (maybe you could do read/write where the read is optimistic, but at least the write side will have some sort of lock). I'm curious what you had in mind?
      - deleted 5y ago
        [deleted]
BeeOnRope 5y ago
Nice writeup as usual by Chris, but I'm pretty sure there were public non-broken, efficient spin-only barrier implementations before this. Here's one I wrote: https://github.com/travisdowns/concurrency-hierarchy-bench/blob/30f30a7e37f2433c21528942ba7d27824be1d1b4/cyclic-barrier.hpp#L15 https://github.com/travisdowns/concurrency-hierarchy-bench/b... Now it is a lot larger and CAS based, rather than an unconditional increment, but that was to support the extra feature of having the "breaker" run a function and return the value, which I needed in this context, as well as reporting the number of spins, etc. The earlier iterations had an unconditional increment. The idea is substantially the same as Chris' and uses only 1 word of state (though my implementation stores the n, the break count, as a member, you could pass it in as Chris does): but it uses the sign bit rather than the (log(n) + 1)th bit to indicate the phase: the count goes negative when in the "draining" phase after the barrier is broken. It supports arbitrary break counts without division and the fast path is comparable to the one in the post, though "fast path" is kind of meaningless when you expect to spin most of the time (as long as you don't invoke the scheduler, at least). That said, Chris's bit manipulation approach is very compact and elegant!
bob1029 5y ago
I learned a lot about this stuff from this paper: https://lmax-exchange.github.io/disruptor/disruptor.html https://lmax-exchange.github.io/disruptor/disruptor.html I think the Disruptor is probably still the most ideal approach for serializing multiple producers on an x86 platform. The core idea is to decouple the producer and consumer so that they do not contend over the same CAS variable (position in a ring buffer). If you only have a single producer, the CAS goes entirely uncontended and you will get tens to hundreds of millions of items per second without issue. Even with multiple producers, the figures are fairly incredible. The trade off is that you basically have to sacrifice an entire core to busy-waiting if you want the world-class latency performance. Alternatives can yield or wait on conditions, but clearly would be slower.
- gpderetta 5y ago
  I don't see how you can use the Disruptor as a barrier, at least in a way that is remotely efficient.
  - bob1029 5y ago
    > I don't see how you can use the Disruptor as a barrier I am not advocating for this. I am simply demonstrating how the Disruptor leverages these kinds of techniques (memory barriers, et. al.) to provide a high performance outcome for its intended use cases. I would be exhilarated if someone could demonstrate an even faster way to do what the Disruptor does (for x86 platforms).
    - gpderetta 5y ago
      Sorry, I misunderstood. If you need a total message order and many-to-all messaging it is indeed hard to do better than the Disruptor, but that's kind of a very specialized need. If you can relax the message ordering for example, multiple 1-to-all queues can be significantly more efficient.
      - bob1029 5y ago
        > that's kind of a very specialized need I somewhat disagree with this. I have been able to build a lot of business systems that have nothing to do with fintech on top of the exact same abstraction. Order matching engines are not the only thing that can benefit from being able to deal with millions of serialized events per second. Most video games, especially multiplayer ones, can benefit from this style of abstraction too.

83 points by kencausey 5y ago

It's a nice write up. I did this once with a slight modification. The phase really only needs one bit, and an arbitrary number of threads can be supported in a number of ways by having the last thread to arrive at the barrier clean up the state based on a second word that holds the number of threads. For example, compare the thread counter part of the "v" value to the number of threads. If equal, do an atomic store which writes the opposite phase with a thread count of 0. If not equal, spin until the phase bit changes. This approach avoids a division and can support threads that leave the barrier entirely. (And theoretically also entering the barrier, but that's always dicey regardless of the barrier implementation.)

gpderetta 5y ago
So, I understand that the difficulty is being able to reset the barrier without a quiescent period. It seems to me that a counter being able to count to n is enough and there is no need of an explicit phase bit: Wait(int *b, int n): 1: x = *b if (x == n-1) *b=0 //last, reset else if cas(b, x, x+1) 2: if *b goto 2 else goto 1
- atq2119 5y ago
  Your spin loop could easily miss the time during which *b == 0. The article explains that. A separate phase bit is required.
  - gpderetta 5y ago
    Yes. I see it now.

dragontamer 5y ago

Hmmmm. A lot of the "difficult parts" of the barrier is the synchronization / memory-barrier part (not the same as a spin-lock barrier. Ugggh, we need someone to revamp the language of low-level multiprocessor programming). Anyway, the memory-barrier part is "solved" by using atomics and then handwaving all the loads/stores as sequentially-consistent. Yeah, that works, but would lead to subpar performance on all systems, as x86 has total-store ordering (less powerful than sequentially consistent), so x86-compilers would probably need to emit a memory barrier. ARM / POWER8/POWER9/POWER10 systems are "even weaker", so they need an even more powerful barrier to be emitted by the compiler. ------- There's also the "Hyperthread yield" instruction that should be placed somehwere in POWER/x86 systems. (Most ARM systems largely don't have hyperthreads/SMT, but the ARM E2 does...). Without "hyperthread yield", the pipeline is going to be uselessly full of load/store instructions from this tight inner-loop. EDIT: I had to search for it, but I now know the name of the instruction on x86. "PAUSE" is the hyperthread-yield instruction. https://www.felixcloutier.com/x86/pause https://www.felixcloutier.com/x86/pause You may be "livelock starving" your brother-hyperthread because your current thread is using up all of the pipeline / decoding bandwidth. By using "hyperthread yield", your code will use the minimum amount of decoding bandwidth. ----- The article does talk about memory-barriers, but seems to be missing the discussion on hyperthread yield. So its probably not "as efficient" as it could get yet. I can believe that the implementation works as discussed in the blogpost. But its still yet incomplete: a faster implementation probably exists, maybe not with "Fully Relaxed" atomics, but probably with acquire/release atomics (which are free on x86, and significantly faster on ARM/POWER9 than seq-cst atomics). Note: ARM8+ and POWER9+ now have load-acquire and store-release instructions, serving as an intermediate performance between fully relaxed atomics and seq-cst atomics. (These instructions may have existed earlier, but I know for sure they're in the modern version of these chips). Once acquire/release barriers are figured out in the right location, the use of hyperthread-yield on x86 and POWER systems would be best on highly-loaded systems. I'm not sure how to test the efficacy / throughput of hyperthread-yield however, I only know of its theoretical benefits. Coming up with a good test (to make sure we're actually improving performance) is itself a difficult question. TL;DR: Good first pass implementation, and good discussion to get things started. But there's still a long way before I consider it a top-end implementation! For many projects, what is seen here is probably sufficient (especially professional projects where you need to move onto some other programming task). But a hobby project could keep optimizing a bit longer to squeeze out a few more cycles of efficiency here. Coming up with a test to ensure the acquire-release is properly done is also somewhat difficult, and would require ARM / POWER hardware.

gpderetta 5y ago
It seems to me that a barrier primitive needs at the very least acq+rel semantics [1], which means that TSO implicit acquire and release are neither necessary nor sufficient[2]. In practice on x86 this means an atomic RMW which is seq-cst. I'm not familiar enough with ARM/Power to know if acq+rel is significantly faster than seq cst. [1] See the Laws of Orders paper. [2] without using asymmetric synchronization which is not appropriate for a general purpose barrier.
- dragontamer 5y ago
  I admit that I'm not 100% perfect with the various memory models at play here. But my understanding is... 1. Seq-cst -- Strongest/slowest. (Aka: Java volatile) 2. Total Store order (aka: x86) 3. Acq-Release (aka: newer-ARM / newer-POWER) 4. Acq-Consume (aka: old-ARM / old-Power) 5. Relaxed -- Weakest/fastest, DEC Alpha. That is to say, acquire-release is often compiled into no-op on x86, because x86 Total-store ordering is "stronger" than acquire-release. Acquire-Consume was thought to be sufficient, but C++11 debate argued otherwise, and designed a stronger Acquire-release model. ARM/POWER designers then implemented acquire-release model. -------- I understand that things aren't perfectly linear, and that at the lower level the discussion is about read/read, read/write, write/read, and write/write barriers. But my brain has never really grok'd this level of detail. (Instead, I think in terms of the simplified list above). So please correct me if I'm wrong with the above assumptions.
  - gpderetta 5y ago
    An acquire+release fence is equivalent to two indivisible acquire and release fences but can't be implemented by simply issuing the two fences in isolation, as they would be unordered with each other. x86 has no native acq+relase fence and it can't be simulated, for example, with a load plus a store (i.e. separate acquire and release fences), but you need an mfence or atomic rmw. ARM and power do allow for indipendent reads of indipendent writes (or maybe only power) so in principle an acq+rel fence could be cheaper than a full seqctst one, although I don't know if it is in practice.

ativzzz 5y ago

This seems very similar to the centralized counting barrier described in [1] where each thread, upon hitting the barrier, decrements the count and spins until a global "sense" boolean is reversed. The last thread to hit the barrier, resets the counter and flips the "sense" freeing up all other threads. I guess the difference is this one treats the bool as odd/even values of an integer, but does that work for n_threads > 2? [1]http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf http://web.mit.edu/6.173/www/currentsemester/readings/R06-sc...

hinkley 5y ago
These boolean arrangements ("flipping") fail when the number of watchers is high and the interval is small. The toggle can switch twice while you're queued to be run again, and then all bets are off, because it looks to you like nothing has happened. Your messaging rate can only be half of the frequency guaranteed by the kernel for waking every thread. And many OSes offer no ironclad guarantee.
- ativzzz 5y ago
  How? Only one thread, the last one when the counter is 0, flips the switch. Before the switch is flipped, the counter is reset, so the next flip will only happen when every thread once again hits the next barrier and the counter decrements to 0.
  - hinkley 5y ago
    State observed by thread 1: counter = 5, state = blue; State observed by threads 2-4: counter = [4,5,1,2,3,4,5,6], state = [blue, green, blue] Thread 1 wakes up, sees counter = 6, state = blue; Logical conclusion: system state is counter++, state unchanged. Actual scenario: counter+=6, state+=2 I believe this was first covered in my distributed computing class, but was probably most concretely illustrated in the case of concurrent garbage collection. Any unfairness in the thread scheduler can lead to some threads getting way more clock cycles than others. In low frequency scenarios you can convince yourself it's not a problem, only to be punished by success into finding out you're wrong when you have 10,000 active users instead of 10. This is especially true with spinlocks, because it's a greedy algorithm that trades fairness for responsiveness. It can result in low throughput or even priority inversion. They are a very sharp knife. Indispensable for very specific tasks, certain bloodshed for others.

MaxGanzII 5y ago

I may be wrong, but I don't see this working in theory. The basic problem is that for any physical core, there is no guarantee that any writes will ever be seen by any other core (unless the necessary extra magic is done to make this so). (There's a matching problem when reading, too, in that in theory writes made by another core can be never seen by the reading core, even if they have reached the domain covered by cache coherency, unless the necessary extra magic, etc.) So here with this code, in theory, the writes being made simply are never seen by another core, and so it doesn't work. As it is, in practise, writes typically make their way to other physical cores in a reasonably short time, whether or not the extra magic is performed; but this is not guaranteed. Also of course the ordering of the emergence of those writes is not guaranteed (although on some platforms, additional guarantees are provided - Intel is particular generous in this regard, and performance suffers because of it).

dragontamer 5y ago
> The basic problem is that for any physical core, there is no guarantee that any writes will ever be seen by any other core (unless the necessary extra magic is done to make this so). They're using atomic read/writes with sequential-consistency. This means that the compiler will automatically put memory-barriers in the appropriate locations to guarantee sequential-consistency, but probably at a significant performance cost. The implementation is likely correct, but its the slowest performance available (seq-cst is the simplest / most braindead atomic operation, but slowest because you probably don't need all those memory barriers). I'd expect that Acq-release style barriers is possible for this use case, which would be faster on x86, POWER, and ARM systems.
- MaxGanzII 5y ago
  > They're using atomic read/writes with sequential-consistency. In the C11 code? I'm not up to speed with that version of the spec, but unless there is behaviour invoked by the use of _Atomic, the code looks to me to be performing normal, non-atomic read/writes. Another reply says there are full barriers being automatically used, but that doesn't address the problem I've described.

api 5y ago

Be careful with spin locks. We used to have one in the ZeroTier core. We pulled it due to a crazy insane bug where it would hang on single core machines and another one where it would run away on CPU usage on massively multicore machines. These bugs had the same cause. Think about it. Don't use spin locks unless you have profiled and have a clear understanding of the contention factors involved. Also be sure to test on single core and massively multicore. Also look at whether you can use atomics. Atomics are better than lock guarded things in almost every way. The only time locks beat atomics is when you are updating a bunch of things in which case it may be faster to lock once than to update 10 atomic variables. Message passing can also win sometimes over concurrent access even if it involves more copying. Profile and think.

PaulDavisThe1st 5y ago
> The only time locks beat atomics is when you are updating a bunch of things in which case it may be faster to lock once than to update 10 atomic variables. Locks are mandatory when you're updating data that does not fit into a single atomic type. You cannot use N atomics to create atomic update of a data structure that must be semantically atomic across its N members.
- gpderetta 5y ago
  Technically any algorithm can be implemented in a lock free way and there are n-way CAS constructs that indeed allow updating N memory locations atomically. In practice they are very slow.
  - atq2119 5y ago
    You can use RCU to do this, but I'd argue that everything else ends up being more or less a lock by another name (maybe you could do read/write where the read is optimistic, but at least the write side will have some sort of lock). I'm curious what you had in mind?
    - deleted 5y ago
      [deleted]

BeeOnRope 5y ago

Nice writeup as usual by Chris, but I'm pretty sure there were public non-broken, efficient spin-only barrier implementations before this. Here's one I wrote: https://github.com/travisdowns/concurrency-hierarchy-bench/blob/30f30a7e37f2433c21528942ba7d27824be1d1b4/cyclic-barrier.hpp#L15 https://github.com/travisdowns/concurrency-hierarchy-bench/b... Now it is a lot larger and CAS based, rather than an unconditional increment, but that was to support the extra feature of having the "breaker" run a function and return the value, which I needed in this context, as well as reporting the number of spins, etc. The earlier iterations had an unconditional increment. The idea is substantially the same as Chris' and uses only 1 word of state (though my implementation stores the n, the break count, as a member, you could pass it in as Chris does): but it uses the sign bit rather than the (log(n) + 1)th bit to indicate the phase: the count goes negative when in the "draining" phase after the barrier is broken. It supports arbitrary break counts without division and the fast path is comparable to the one in the post, though "fast path" is kind of meaningless when you expect to spin most of the time (as long as you don't invoke the scheduler, at least). That said, Chris's bit manipulation approach is very compact and elegant!

bob1029 5y ago

I learned a lot about this stuff from this paper: https://lmax-exchange.github.io/disruptor/disruptor.html https://lmax-exchange.github.io/disruptor/disruptor.html I think the Disruptor is probably still the most ideal approach for serializing multiple producers on an x86 platform. The core idea is to decouple the producer and consumer so that they do not contend over the same CAS variable (position in a ring buffer). If you only have a single producer, the CAS goes entirely uncontended and you will get tens to hundreds of millions of items per second without issue. Even with multiple producers, the figures are fairly incredible. The trade off is that you basically have to sacrifice an entire core to busy-waiting if you want the world-class latency performance. Alternatives can yield or wait on conditions, but clearly would be slower.

gpderetta 5y ago
I don't see how you can use the Disruptor as a barrier, at least in a way that is remotely efficient.
- bob1029 5y ago
  > I don't see how you can use the Disruptor as a barrier I am not advocating for this. I am simply demonstrating how the Disruptor leverages these kinds of techniques (memory barriers, et. al.) to provide a high performance outcome for its intended use cases. I would be exhilarated if someone could demonstrate an even faster way to do what the Disruptor does (for x86 platforms).
  - gpderetta 5y ago
    Sorry, I misunderstood. If you need a total message order and many-to-all messaging it is indeed hard to do better than the Disruptor, but that's kind of a very specialized need. If you can relax the message ordering for example, multiple 1-to-all queues can be significantly more efficient.
    - bob1029 5y ago
      > that's kind of a very specialized need I somewhat disagree with this. I have been able to build a lot of business systems that have nothing to do with fintech on top of the exact same abstraction. Order matching engines are not the only thing that can benefit from being able to deal with millions of serialized events per second. Most video games, especially multiplayer ones, can benefit from this style of abstraction too.