6 ms·
Optimizing a lock-free ring buffer
- lukesergei 7mo ago[flagged]
- dalvrosa 7mo ago:)
- hedal 7mo ago[flagged]
- dalvrosa 7mo agoThanks!
- dalvrosa 7mo agoFrom 12M ops/s to 305 M ops/s on a lock-free ring buffer. In this post, I walk you step by step through implementing a single-producer single-consumer queue from scratch. This pattern is widely used to share data between threads in the lowest-latency environments.
- loeg 7mo agoYour blog footer mentions that code samples are GPL unless otherwise noted. You don't seem to note otherwise in the article, so -- do you consider these snippets GPL licensed?
- dalvrosa 7mo agoActually I'm not sure. GPL was for source code of the website itself I guess the code samples inside post are under https://david.alvarezrosa.com/LICENSE https://david.alvarezrosa.com/LICENSE But feel free to ping me if you need different license, quite open about it
- random3 7mo agoRing buffers never get old. Here’s a useful mention of some of the most extensive technical work by LMAX team over 15 years ago https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html
- kristianp 7mo agoThis is in C++, other languages have different atomic primitives.
- dalvrosa 7mo agoYeah, this is quite specific to C++ (at a syntax level)
- jitl 7mo agoReally? Pretty much all atomics i’ve used have load, store of various integer sizes. I wrote a ring buffer in Go that’s very similar to the final design here using similar atomics. https://pkg.go.dev/sync/atomic#Int64 https://pkg.go.dev/sync/atomic#Int64
- dalvrosa 7mo agoNice one, thanks for sharing. Do you wanna share the ring buffer code itself?
- wat10000 7mo agoThey generally map directly to concepts in the CPU architecture. On many architectures, load/store instructions are already guaranteed to be atomic as long as the address is properly aligned, so atomic load/store is just a load/store. Non-relaxed ordering may emit a variant load/store instruction or a separate barrier instruction. Compare-exchange will usually emit a compare and swap, or load-linked/store-conditional sequence. Things like atomic add/subtract often map to single instructions, or might be implemented as a compare-exchange in a loop. The exact syntax and naming will of course differ, but any language that exposes low-level atomics at all is going to provide a pretty similar set of operations.
- sanufar 7mo agoSuper fun, def gonna try this on my own time later
- dalvrosa 7mo agoFeel free to share your findings
- JonChesterfield 7mo agoIt's obviously, trivially broken. Stores the index before storing the value, so the other thread reads nonsense whenever the race goes against it. Also doesn't have fences on the store, has extra branches that shouldn't be there, and is written in really stylistically weird c++. Maybe an llm that likes a different language more, copying a broken implementation off github? Mostly commenting because the initial replies are "best" and "lol", though I sympathise with one of those.
- dalvrosa 7mo agoSorry, but that's not actually true. There are no data races, the atomics prevent that (note that there are only one consumer and one producer) Regarding the style, it follows the "almost always auto" idea from Herb Sutter
- secondcoming 7mo agoIf you enforce that the buffer size is a power of 2 you just use a mask to do the if (next_head == buffer.size()) next_head = 0; part
- JonChesterfield 7mo agoIf it's a power of two, you don't need the branch at all. Let the unsigned index wrap.
- Blackthorn 7mo agoI had what I thought was a pretty good implementation, but I wasn't aware of the cache line bouncing. Looks like I've got some updates to make.
- dalvrosa 7mo agoGlad that it helps :)
- devnotes77 7mo ago[dead]
- kevincox 7mo agoRandom idea: If you have a known sentinel value for empty could you avoid the reader needing to read the writer's index? Just try to read, if it is empty the queue is empty, otherwise take the item and put an empty value there. Similarly for writing you can check the value, if it isn't empty the queue is full. It seems that in this case as you get contention the faster end will slow down (as it is consuming what the other end just read) and this will naturally create a small buffer and run at good speeds. The hard part is probably that sentinel and ensuring that it can be set/cleared atomically. On Rust you can do `Option<T>` to get a sentinel for any type (and it very often doesn't take any space) but I don't think there is an API to atomically set/clear that flag. (Technically I think this is always possible because the sentinel that Option picks will always be small even if the T is very large, but I don't think there is an API for this.)
- loeg 7mo agoYeah, or you could put a generation number in each slot adjacent to T and a read will only be valid if the slot's generation number == the last one observed + 1, for example. But ultimately the reader and writer still need to coordinate here, so we're just shifting the coordination cache line from the writer's index to the slot.
- kevincox 7mo agoI think the key difference is that they only need to coordinate when the reader and writer are close together. If that slows one end down they naturally spread apart. So you don't lose throughput, only a little latency in the contested case.
- loeg 7mo ago> I think the key difference is that they only need to coordinate when the reader and writer are close together. This was already the case with the cached index design at the end of the article, though. (Which doesn't require extra space or extra atomic stores.)
- erickpintor 7mo agoGreat post! Would you mind expanding on the correctness guarantees enforced by the atomic semantics used? Are they ensuring two threads can't push to the same slot nor pop the same value from the ring? These type of atomic coordination usually comes from CAS or atomic increment calls, which I'm not seeing, thus I'm interested in hearing your take on it.
- erickpintor 7mo agoI see you replied on comment below with: > note that there are only one consumer and one producer That clarify things as you don't need multi-thread coordination on reads or writes if assuming single producer and single consumer.
- dalvrosa 7mo agoExactly, that's right
- dalvrosa 7mo agoThanks! That's not ensured, optimizations are only valid due to the constraints - One single producer thread - One single consumer thread - Fixed buffer capacity So to answer > Are they ensuring two threads can't push to the same slot nor pop the same value from the ring? No need for this usecase :)
- loeg 7mo agoThis is a SPSC queue -- there aren't multiple writers to coordinate, nor readers. It simplifies the design.
- pixelpoet 7mo agoGreat article, thanks for sharing. And such a lovely website too :)
- dalvrosa 7mo agoThanks for the feedback <3
- ramon156 7mo agoSomething to add to this; if you're focussing on these low-level optimizations, make sure the device this code runs on is actually tuned. A lot of people focus on the code and then assume the device in question is only there to run it. There's so much you can tweak. I don't always measure it, but last time I saw at least a 20% improvement in Network throughput just by tweaking a few things on the machine.
- dalvrosa 7mo agoAgreed. For benchmarking I used this <https://github.com/david-alvarez-rosa/CppPlayground/blob/main/DataStructures/ring_buffer.cpp https://github.com/david-alvarez-rosa/CppPlayground/blob/mai...> which relies on GoogleBenchmark and pins producer/consumer threads to dedicated CPU cores What else could be improved? Would like to learn :) Maybe using huge pages?
- dijit 7mo agokernel tickrate is a pretty big one, most people don't bother and use what their OS ships with. Disabling c-states, pinning network interfaces to dedicated cores (and isolating your application from those cores) and `SCHED_FIFO` (chrt -f 99 <prog>) helps a lot. Transparent hugepages increase latency without you being aware of when it happens, I usually disable that. Idk, there's a bunch but they all depend on your use-case. For example I always disable hyperthreading because I care more about latency than processing power- and I don't want to steal cache from my workload randomly.. but some people have more I/O bound workloads and hyperthreading is just and strict improvement in those situations.
- brcmthrowaway 7mo agoRandom q: What was the first cpu to support atomic instructions?
- jeffbee 7mo agoI don't know but the IBM 360 and the DEC PDP-10 both had them. Those are the earliest systems I ever saw.
- brcmthrowaway 7mo agoIs there a C library that I can get these data structures for free?
- loeg 7mo agoConcurrencyKit ck_ring. The SPSC macros are the most similar to this article: https://github.com/concurrencykit/ck/blob/master/include/ck_ring.h#L977 https://github.com/concurrencykit/ck/blob/master/include/ck_...
- nitwit005 7mo agoIt would be nice to have an example use case where the technique would show a benefit. It seems relatively rare to have a single producer and consumer thread, and be worth polling a ring buffer.
- ohazi 7mo agoI use my own very similar version of this spsc lock-free ring buffer on almost every embedded project I work on that has to stream any sort of sampled data (e.g. audio). You can even have the consumer end be a DMA into something like a uart or USB peripheral so your microcontroller userspace doesn't have to touch the hardware.
- jeffbee 7mo agoIt's lock-free because it uses ordered loads and stores, which is also how you implement locks. I find the semantic distinction unconvincing. The post is really about how slow the default STL mutex implementation is.
- loeg 7mo agoThere are real practical implications of both the producer and consumer mutating the same cache line to take a lock that is fundamentally avoided by this "lock-free" design. It isn't meaningless.
- pjdesno 7mo agoThat's what "lock-free" means. You still need to use the hardware mechanisms provided for atomicity. The whole point of lock-free data structures and algorithms is that sometimes you can do better by using these atomic operations inside your own code, rather than using a one-size-fits-all mutex based on those same atomic operations. (Note that I say "sometimes". Too many people believe that lock-free structures are always faster; as always, your mileage may vary. In this case it's a huge win, to the point where I would bet it almost always moves the bottleneck to the code actually using the ring buffer.)
- jeffbee 7mo agoMy point is that the "huge win" is expressed in terms of a bogus and misleading baseline. The article moves immediately from the worst possible lock-based implementation to a pretty bad atomics-based implementation. The final punchline of the article is expressed as a ratio of the bad baseline. To make an honest conclusion, the article should also explore better ways of using the locks.
- mikhmha 7mo agoLock-free ring buffer is my favorite data structure. I remember implementing it in C++ and then using a legitimate implementation in the form of boost:SPSC for prod. The idea is so simple. And then I started thinking about designing some programming language or framework around the concept, only to then stumble upon the idea of "message passing" for concurrency. Which of course led me to learn about Erlang. And then I went down the Erlang rabbit hole. It might have been a mistake...I made more money doing C++.
- dalvrosa 7mo agoLol. Funny story :)
- kev946 7mo agoIs it okay for push and pop to have noexcept when copy assignment of T could throw?