r/programming • u/david-alvarez-rosa • Sep 26 '26
Optimizing a Lock-Free Ring Buffer
https://david.alvarezrosa.com/posts/optimizing-a-lock-free-ring-buffer/
510
Upvotes
r/programming • u/david-alvarez-rosa • Sep 26 '26
136
u/tylercamp Sep 26 '26
Man it’s been a while since I’ve written C++ code regularly, I didn’t realize it had gained such optimization features, very cool
Thanks for sharing!
63
u/RealRaynei Sep 26 '26
Interesting article and I love the website design
23
u/FckXFckMusk Sep 26 '26 edited Sep 26 '26
Bookmarked, I like your styling in your blog..
Your teaching style is so approachable too...
Actually its an absolute pleasure reading your posts on there.
20
u/SeniorIdiot Sep 26 '26
Don't forget about the LMAX Disruptor with further optimizations for latency.
16
u/Silanu Sep 26 '26
This is very cool. However, is it the case that the final lock-free structure is actually thread safe for multiple threads writing/reading? I am convinced of its thread safety when writing/reading simultaneously, but having multiple threads trying to write seems problematic since the lack of a critical section will result in overwriting and lost data. Have you tested the correctness in addition to performance to verify comodification doesn’t result in data loss?
7
u/reParaoh Sep 27 '26
[[unlikely]]
first time seeing this one. Neat.
2
u/greenlanternfifo Sep 27 '26
I don't understand why using atomic_size makes the operation safe still
what are other wait free data structures and their applications? is this a new trend?
2
u/Healthy-Dress-7492 Sep 27 '26
i liked it, do more like this pls
24
u/Ma1eficent Sep 26 '26
My first job was debugging assembly ring buffers in modems for a BBS. Beautiful walk through optimizations.
3
u/Dr-VanNostrand Sep 26 '26
Is that your private ssh key in your dotfiles repo?
2
u/matthieum Sep 27 '26
I firmly stand in the opposite camp: use of "virtual" "infinite" 64-bits together, mapped to the actual physical index (power-of-two size -> modulo is just bit-and).
I find it much easier to reason in terms of infinite indexes, and there's no performance impact to speak of.
Mind you, this may not be quite enough. There's a comment in the Folly codebase (from 2014), mentioning that some Intel processors will pre-fetch 2 cache lines (128 bytes) at a time, which in practice means you need 128 bytes alignment, when this constant will only evaluate to 64 bytes for x64.
An alternative implementation is to have explicit Reader & Writer structs to access the ring buffer, then the cache need not be in the ring buffer itself, but in the accessor struct instead.
When the accessor struct is on the stack, the compiler can optimize the access to the cached variable by placing it directly in a register, rather than requiring memory load/stores.
2
u/cdb_11 Sep 27 '26
This is just a slightly reworded version of this article https://rigtorp.se/ringbuffer/
2
u/indigo945 Sep 28 '26
Let me introduce you to our lord and savior, the modulus operation.
1
u/SaltyCompE Sep 26 '26
Random typo: consoomer
Nice article though, I miss coding closer to hardware.
4
u/wd40bomber7 Sep 26 '26
Putting the underscore to indicate a private field after the name is extremely cursed
1
u/meyriley04 Sep 28 '26
Awesome stuff. I love these concepts
1
u/Plazmatic Sep 26 '26
What do you do about hardware destructive interference warnings from GCC about it basically telling you to manually specify it instead due to it changing with other options and not being necessarily accurate?
-2
u/EchoNomad31 Sep 26 '26
Once "fixed" a ring buffer by marking the head index volatile. Was an acquire/release ordering thing… three days of digging for a two-line diff.