alt Hacker NewsI've been writing ring buffers wrong all these years (2016)
Comments
It's a silly offhand remark at the end of the article, but anybody who is genuinely interested in whether they've been tying their shoes wrong will enjoy Ian's shoelace site: https://www.fieggen.com/shoelace/
> 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?
I’m jealous of people, who have to write ring buffers for work.
It feels like 90% swe jobs these days are about writing CRUD wrappers.
This stuff dates way, way before 2004.
For non-power of two, just checked our own very old circular byte buffer library code and using the notation from this article, it is:
entriesAllocated() { return ((wrPtr-rdPtr+2*bufSize) % (2*bufSize)); }
remainingSpace() { return bufSize - entriesAllocated(); }
isEmpty() { return (entriesAllocated()==0); }
isFull() { return (entriesAllocated()==bufSize); }
incWr(int n) { wrPtr = (wrPtr+n) % (2*bufSize); }
incRd(int n) { rdPtr = (rdPtr+n) % (2*bufSize); }
Related. Others?
I've been writing ring buffers wrong all these years - https://news.ycombinator.com/item?id=13175832 - Dec 2016 (167 comments)
Most people implement them now in my field using mmap tricks so the CPU can do the wraparound for you in virtual memory.
Makes the code trivial
Technically each side needs an index plus a single bit. The bit is a counter, you increment it on every wrap. It overflows, but this is correct, we only need the last bit. Initially it is 0. By comparing the indexes and the bit you tell apart all cases and do not lose an entry.
(I think this was published in one of Llang's papers but in a rather obscure language.)
As far as I know, the last approach is the only way to implement efficient lock-free ring-buffer
Every implementation of "the lmax disrupter" I've come across uses this trick.
Why would you ever want a data structure that wraps around!? What a headache! Is it a memory constraint or optimization!? All I can think about is a physical knob where you want to know what position it is in.
That's how TCP sequence numbers work as well.
> All of those seem like non-issues. What kind of a monster would make a non-power of two ring anyway?
Huh? Anytime you want to restrict the buffer to a specific size, you will have to support non-power-of-two capacities. There are cases where the capacity of the ring buffer determines the latency of the system, e.g. an audio ringbuffer or a network jitter buffer.
It 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...