7 ms·

One neat thing is, you don't actually need a spinlock if you're using a ringbuffer. You can use atomic increment on a counter to claim a slot, then write to tha

One neat thing is, you don't actually need a spinlock if you're using a ringbuffer. You can use atomic increment on a counter to claim a slot, then write to that slot. It can be between two to three orders of magnitude higher throughput. Equally important, lower latency. (Throughput tends to be a consequence of low latency, but not always.) I'm not saying this should be the norm, though. You probably don't need this design. But when you do, e.g. processing millions of stock market messages, there's no substitute. EDIT: I love hearing about the designs and questions, but it was probably a mistake for me not to be explicit. Sorry! The thing I'm referring to is LMAX Disruptor pattern: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ I learned about it in 2011-ish, and it deeply changed my perspective on high speed designs.

ampdepolymerase 5y ago
Long live the LMAX?
- sillysaurusx 5y ago
  All hail! It was truly a cool design, for its time. I feel strongly like it's one of those designs you should study just to even be aware that such a thing exists. Otherwise I probably would've been like "Oh, a spinlock! Yes, always." (It's the disruptor pattern: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/)
emerged 5y ago
I spent several years developing lockfree algorithms and very often CAS loops are the empirically fastest solution. But as often, you can perform as good or better with atomic increments. The devil is in the details of what sort of tasks you’re managing and on which specific hardware.
- namibj 5y ago
  The problem is that CAS loops in locking scenarios aren't an option if you're subject to preemption. Yes, true lock-free datastructures are allowed, but for many there are situations where you could practically encounter live locks (i.e., they aren't just a theoretical possibility for the access algorithm). Atomic increment is still fairly cheap/efficient and resolves many cases where you'd risk live lock by being wait-free in some aspects.
  - emerged 5y ago
    There are many scenarios where you’re subject to preemption and CAS is empirically faster and completely viable. This including hardware with over 200 hardware threads of concurrency. In that same realm of hardware, atomic increments can be as fast or faster. Certain devilish details I’m sure are exceptions to those scenarios, just sharing the ones I’ve come across.
    - namibj 5y ago
      Yeah, we've been bitten by horrible degradation as soon as anything else is running on the system next to the main application, like a cron job or unknowingly running CI on a VM where the VM's vCPUs are subject to preemption. As long as you aren't oversubscribing hardware threads, you'll be fine, but at the cost of pathological behavior once you add just a single additional thread. Also don't use `sched_yield(2)` for spin locks, unless you're running priority-based RT Linux. A scheduler that is good for that scenario tends to be quite bad at most real-world scenarios that don't try to do their own spinlocks in userspace due to NIH syndrome.
reitzensteinm 5y ago
Do you have an example of this in action? I'd be interested to know what steps are taken to avoid false sharing of cache lines in the ring buffer itself.
- sillysaurusx 5y ago
  You pad each counter so that it's on a separate cache line. https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ goes into detail on the false sharing problem. (A+ and full marks on recognizing that that's a central problem.)
  - rigtorp 5y ago
    I think reitzensteinm was referring to the actual data inside the ring. There is a false sharing problem there particularly for the MPMC type ring buffer like disruptor. The solution is to pad each data slot in addition to the read and write indices. I do this in my MPMC ring buffer queue: https://github.com/rigtorp/MPMCQueue/blob/master/include/rigtorp/MPMCQueue.h#L106 https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...
- rigtorp 5y ago
  You can align and pad each ring buffer slot to the cache line size. Example https://github.com/rigtorp/MPMCQueue/blob/master/include/rigtorp/MPMCQueue.h#L106 https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...
Kranar 5y ago
I have not found this to be the case in my situation but there are so many variations of this that I could be missing something. So from my experiments with this, in order to avoid a lock you need to have a ringbuffer of atomic pointers (or atomic values if you're literally just buffering ints or similar). You claim a slot which is a pointer, and then swap out the pointer to the stale value with the pointer to the updated value. But this now requires a multithreaded lock free memory pool. Single threaded this is no problem, but multithreaded this is incredibly difficult without high latency. From my own efforts, while it's possible to implement a lock free ring buffer + suitable memory allocator, you end up with high latency. This high latency can only be justified if the size of the data you're buffering is greater than a certain bound because you get increased bandwidth. For data less than a certain bound, my experience is you get much lower latency and lower bandwidth (but still pretty good bandwidth) by tagging each element with a lock-bit. I suspect we work in the same area (finance), so if you have insight into good lock free memory allocators or resources I'd be very happy to better inform myself.
- sillysaurusx 5y ago
  It's easy to fall into traps! I edited my original comment with a link to https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ which has all the details on avoiding the pitfalls you mention. As to your specific concern, I think you should be able to preallocate a large buffer of objects that you want to share. In other words, the allocations only need to happen infrequently. The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals. It's true that you do need to be allocating memory, but the memory can be allocated by a thread (lock free), and then the slot is claimed and pointer written (still lock free). But there's nothing special about this process -- just allocate some memory, and stick it into the slot. The ringbuffer is the thing that handles the coordination, enabling you to allocate memory on whatever thread you want. Is there a reason more complexity is justified? (More complexity might entirely be justified, and I just haven't had that experience.)
  - Kranar 5y ago
    >the memory can be allocated by a thread (lock free) If there is one thread A allocating memory to push a value onto the ring buffer, and another thread B popping a value off of the ring buffer, how does B free that memory back to the memory allocator without introducing a data race? Certainly there must be some kind of synchronization so that A can allocate memory and B can free that memory. >The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals. Yes, because in many cases when I see lock free data structures and get excited about it, what is really presented is a data structure that is putting all of the locking pressure on the memory allocator so that the system as a whole has no net gain. And this comes down to the crux of the issue, you can write a lock free ring buffer if you stuff all your locking into your memory allocator and I suppose you could claim that the ring buffer is lock free... but the system of ring buffer + memory allocator is then no longer lock free. That said I'm not saying that this is bad, being lock free doesn't mean good, fast whereas using a lock means slow, bad... it's just that there are a lot of subtle details that make a proper analysis of this much more difficult than it first appears and to the best of my knowledge there is no lock free ring buffer that gives a clear performance benefit. But as I said, this is such a tricky subject with so many different possible configurations that I would love to see different approaches.
secondcoming 5y ago
Last time I looked at Disruptor it still required a WaitStrategy, one of which was a Spinlock
- sillysaurusx 5y ago
  Not for the single producer multi consumer case, which is approximately the most useful case. (For me, anyway.) If you have multiple producers and consumers though, then yes. But it's very cool to me that you can do without the spinlock in any useful case.
  - secondcoming 5y ago
    Are you sure? It's been a while since I ported it to C++ and so maybe the code has changed, but doesn't the producer have to wait for all consumers to consume, and don't consumers have to wait for the producer to produce? The BlockingWaitStrategy was mutex based IIRC.
    - sillysaurusx 5y ago
      The original whitepaper goes into detail about where the lock isn't necessary: https://lmax-exchange.github.io/disruptor/files/Disruptor-1.0.pdf https://lmax-exchange.github.io/disruptor/files/Disruptor-1.... I did this in 2011 or so, so it's been a decade. But my feelings are, "I'm quite certain that if I were to re-read the paper from start to finish, I'd end up feeling convinced of the position I just tried to convince you of." If that's not true, then I'm simply a fool, and will happily concede. :) But! For now, I have to go look at a house that we're thinking of renting.
      - deleted 5y ago
        [deleted]
rigtorp 5y ago
Ringbuffers and thread-per-core architecture is great for low latency transaction processing systems, like exchanges and trading systems. Sometimes you don't have time to do things perfectly and might use a spinlock when initializing some cache on first use... Only light contention, not great not, not terrible :).

ampdepolymerase 5y ago

Long live the LMAX?

sillysaurusx 5y ago
All hail! It was truly a cool design, for its time. I feel strongly like it's one of those designs you should study just to even be aware that such a thing exists. Otherwise I probably would've been like "Oh, a spinlock! Yes, always." (It's the disruptor pattern: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/)

emerged 5y ago

I spent several years developing lockfree algorithms and very often CAS loops are the empirically fastest solution. But as often, you can perform as good or better with atomic increments. The devil is in the details of what sort of tasks you’re managing and on which specific hardware.

namibj 5y ago
The problem is that CAS loops in locking scenarios aren't an option if you're subject to preemption. Yes, true lock-free datastructures are allowed, but for many there are situations where you could practically encounter live locks (i.e., they aren't just a theoretical possibility for the access algorithm). Atomic increment is still fairly cheap/efficient and resolves many cases where you'd risk live lock by being wait-free in some aspects.
- emerged 5y ago
  There are many scenarios where you’re subject to preemption and CAS is empirically faster and completely viable. This including hardware with over 200 hardware threads of concurrency. In that same realm of hardware, atomic increments can be as fast or faster. Certain devilish details I’m sure are exceptions to those scenarios, just sharing the ones I’ve come across.
  - namibj 5y ago
    Yeah, we've been bitten by horrible degradation as soon as anything else is running on the system next to the main application, like a cron job or unknowingly running CI on a VM where the VM's vCPUs are subject to preemption. As long as you aren't oversubscribing hardware threads, you'll be fine, but at the cost of pathological behavior once you add just a single additional thread. Also don't use `sched_yield(2)` for spin locks, unless you're running priority-based RT Linux. A scheduler that is good for that scenario tends to be quite bad at most real-world scenarios that don't try to do their own spinlocks in userspace due to NIH syndrome.

reitzensteinm 5y ago

Do you have an example of this in action? I'd be interested to know what steps are taken to avoid false sharing of cache lines in the ring buffer itself.

sillysaurusx 5y ago
You pad each counter so that it's on a separate cache line. https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ goes into detail on the false sharing problem. (A+ and full marks on recognizing that that's a central problem.)
- rigtorp 5y ago
  I think reitzensteinm was referring to the actual data inside the ring. There is a false sharing problem there particularly for the MPMC type ring buffer like disruptor. The solution is to pad each data slot in addition to the read and write indices. I do this in my MPMC ring buffer queue: https://github.com/rigtorp/MPMCQueue/blob/master/include/rigtorp/MPMCQueue.h#L106 https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...
rigtorp 5y ago
You can align and pad each ring buffer slot to the cache line size. Example https://github.com/rigtorp/MPMCQueue/blob/master/include/rigtorp/MPMCQueue.h#L106 https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...

Kranar 5y ago

I have not found this to be the case in my situation but there are so many variations of this that I could be missing something. So from my experiments with this, in order to avoid a lock you need to have a ringbuffer of atomic pointers (or atomic values if you're literally just buffering ints or similar). You claim a slot which is a pointer, and then swap out the pointer to the stale value with the pointer to the updated value. But this now requires a multithreaded lock free memory pool. Single threaded this is no problem, but multithreaded this is incredibly difficult without high latency. From my own efforts, while it's possible to implement a lock free ring buffer + suitable memory allocator, you end up with high latency. This high latency can only be justified if the size of the data you're buffering is greater than a certain bound because you get increased bandwidth. For data less than a certain bound, my experience is you get much lower latency and lower bandwidth (but still pretty good bandwidth) by tagging each element with a lock-bit. I suspect we work in the same area (finance), so if you have insight into good lock free memory allocators or resources I'd be very happy to better inform myself.

sillysaurusx 5y ago
It's easy to fall into traps! I edited my original comment with a link to https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/ which has all the details on avoiding the pitfalls you mention. As to your specific concern, I think you should be able to preallocate a large buffer of objects that you want to share. In other words, the allocations only need to happen infrequently. The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals. It's true that you do need to be allocating memory, but the memory can be allocated by a thread (lock free), and then the slot is claimed and pointer written (still lock free). But there's nothing special about this process -- just allocate some memory, and stick it into the slot. The ringbuffer is the thing that handles the coordination, enabling you to allocate memory on whatever thread you want. Is there a reason more complexity is justified? (More complexity might entirely be justified, and I just haven't had that experience.)
- Kranar 5y ago
  >the memory can be allocated by a thread (lock free) If there is one thread A allocating memory to push a value onto the ring buffer, and another thread B popping a value off of the ring buffer, how does B free that memory back to the memory allocator without introducing a data race? Certainly there must be some kind of synchronization so that A can allocate memory and B can free that memory. >The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals. Yes, because in many cases when I see lock free data structures and get excited about it, what is really presented is a data structure that is putting all of the locking pressure on the memory allocator so that the system as a whole has no net gain. And this comes down to the crux of the issue, you can write a lock free ring buffer if you stuff all your locking into your memory allocator and I suppose you could claim that the ring buffer is lock free... but the system of ring buffer + memory allocator is then no longer lock free. That said I'm not saying that this is bad, being lock free doesn't mean good, fast whereas using a lock means slow, bad... it's just that there are a lot of subtle details that make a proper analysis of this much more difficult than it first appears and to the best of my knowledge there is no lock free ring buffer that gives a clear performance benefit. But as I said, this is such a tricky subject with so many different possible configurations that I would love to see different approaches.

secondcoming 5y ago

Last time I looked at Disruptor it still required a WaitStrategy, one of which was a Spinlock

sillysaurusx 5y ago
Not for the single producer multi consumer case, which is approximately the most useful case. (For me, anyway.) If you have multiple producers and consumers though, then yes. But it's very cool to me that you can do without the spinlock in any useful case.
- secondcoming 5y ago
  Are you sure? It's been a while since I ported it to C++ and so maybe the code has changed, but doesn't the producer have to wait for all consumers to consume, and don't consumers have to wait for the producer to produce? The BlockingWaitStrategy was mutex based IIRC.
  - sillysaurusx 5y ago
    The original whitepaper goes into detail about where the lock isn't necessary: https://lmax-exchange.github.io/disruptor/files/Disruptor-1.0.pdf https://lmax-exchange.github.io/disruptor/files/Disruptor-1.... I did this in 2011 or so, so it's been a decade. But my feelings are, "I'm quite certain that if I were to re-read the paper from start to finish, I'd end up feeling convinced of the position I just tried to convince you of." If that's not true, then I'm simply a fool, and will happily concede. :) But! For now, I have to go look at a house that we're thinking of renting.
    - deleted 5y ago
      [deleted]

rigtorp 5y ago

Ringbuffers and thread-per-core architecture is great for low latency transaction processing systems, like exchanges and trading systems. Sometimes you don't have time to do things perfectly and might use a spinlock when initializing some cache on first use... Only light contention, not great not, not terrible :).