I've been writing ring buffers wrong all these years (2016)
1–10 of 69 posts
Re: I've been writing ring buffers wrong all these years (2016)
#2As far as I know, the last approach is the only way to implement efficient lock-free ring-buffer
Re: I've been writing ring buffers wrong all these years (2016)
#3Related. Others?
I've been writing ring buffers wrong all these years - https://news.ycombinator.com/item?id=13175832 - Dec 2016 (167 comments)
Re: I've been writing ring buffers wrong all these years (2016)
#4> So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure.
It is, but, IMO, shouldn’t use the code for “a n-element ring buffer, with n set to 1”, similarly to how an array of booleans in many languages shouldn’t be implemented as “an arrayof Foos, with Foo set to bool”.
C++ has std::bitset and std::vector and Java similarly has BitSet and Array because using the generic code for arrays of bits is too wasteful.
Similarly, a one-element ring buffer is either full or it is empty. Why use two indexes to encode a single boolean?
Re: I've been writing ring buffers wrong all these years (2016)
#5As far as I know, the last approach is the only way to implement efficient lock-free ring-buffer
There is one more way that is truly lock free. Most lock free implementations relying on atomic compare and swap instructions are not lock free afaik; they have a lock on the cache line in the CPU (in a way you go away from global lock to many distributed locks).
There is one more mechanism that allows implementing ring buffers without having to compare head and tail buffers at all (and doesn’t rely on counters or empty/full flags etc) that piggybacks on the cache consistency protocol
Re: I've been writing ring buffers wrong all these years (2016)
#6Every implementation of "the lmax disrupter" I've come across uses this trick.
Re: I've been writing ring buffers wrong all these years (2016)
#7> So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure. It is, but, IMO, shouldn’t use the code for “a n-element ring buffer, with n set to 1”, similarly to how an array of booleans in many languages shouldn’t be implemented as “an arrayof Foos , with Foo set to bool”. C++ has std::bitset and std::vector and Java similarly has BitSet and Array…
> C++ has std::bitset and std::vector
Notably, this is not the case. C++ std::vector is specialised for bools to pack bits into words, causing an untold array (heh) of headaches.
And "wasteful" is doing a lot of lifting here. In terms of memory usage? Yes. In terms of CPU? The other way around.
Re: I've been writing ring buffers wrong all these years (2016)
#8As far as I know, the last approach is the only way to implement efficient lock-free ring-buffer
There is one more way that is truly lock free. Most lock free implementations relying on atomic compare and swap instructions are not lock free afaik; they have a lock on the cache line in the CPU (in a way you go away from global lock to many distributed locks). There is one more mechanism that allows implementing ring buffers without having to compare head and tail buffers at all (and doesn’t rely on counters or em…
Interesting! Do you know of an example implementation of this?
Re: I've been writing ring buffers wrong all these years (2016)
#9> So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure. It is, but, IMO, shouldn’t use the code for “a n-element ring buffer, with n set to 1”, similarly to how an array of booleans in many languages shouldn’t be implemented as “an arrayof Foos , with Foo set to bool”. C++ has std::bitset and std::vector and Java similarly has BitSet and Array…
It was for a dynamically growing ring buffer that also did short-object optimization. The natural implementation was to have the capacity and the offsets stored in fixed locations and with a fixed width, and have the variable part be a union of pointer or inline byte buffer.
Depending on the element width, you'd have space for different amounts of data in the inline buffer. Sometimes 1, sometimes a few more. Specializing for a one-element inline buffer would be quite complex with limited gains.
In retrospect trying to use that as a running gag for the blog post did not work well without actually giving the full context, but the full context would have been a distraction.
Re: I've been writing ring buffers wrong all these years (2016)
#10It is not just a way of writing ring buffers. It's a way of implementing concurrent non-blocking single-reader single-writer atomic ring buffers with only atomic load and store (and memory barriers).
The author says that non-power-of-two is not possible, but I'm pretty sure it is if you use a conditional instead of integer modulus.
I first learnt of this technique from Phil Burk, we've been using it in PortAudio forever. The technique is also widely known in FPGA/hardware circles, see:
"Simulation and Synthesis Techniques for Asynchronous FIFO Design", Clifford E. Cummings, Sunburst Design, Inc.
https://twins.ee.nctu.edu.tw/courses/ip_core_04/resource_pdf...