I've been writing ring buffers wrong all these years

<i>This is of course not a new invention. The earliest instance I could find with a bit of searching was from 2004, with Andrew Morton mentioning in it a code review so casually that it seems to have been a well established trick. But the vast majority of implementations I looked at do not do this.</i><p>I was doing this in 1992 so it&#x27;s at least 12 years older than the 2004 implementation. I suspect it was being done long before that. Back then the read and write indexes were being updated by separate processors (even more fun, processors with different endianness) with no locking. The only assumption being made was that updates to the read&#x2F;write pointers were atomic (in this case &#x27;atomic&#x27; meant that the two bytes that made up a word, counters were 16 bits, were written in atomically). Comically, on one piece of hardware this was <i>not</i> the case and I spent many hours inside the old Apollo works outside Boston with an ICE and a bunch of logic analyzers figuring out what the hell was happening on some weird EISA bus add on to some HP workstation.<p>It&#x27;s unclear to me why the focus on a 2^n sized buffer just so you can use &amp; for the mask.<p>Edit: having had this discussion I&#x27;ve realized that Juho&#x27;s implementation is different from the 1992 implementation I was using because he doesn&#x27;t ever reset the read&#x2F;write indexes. Oops.

&gt; Join me next week for the exciting sequel to this post, &quot;I&#x27;ve been tying my shoelaces wrong all these years&quot;.<p>Probably. Use the Ian Knot: <a href="http:&#x2F;&#x2F;www.fieggen.com&#x2F;shoelace&#x2F;ianknot.htm" rel="nofollow">http:&#x2F;&#x2F;www.fieggen.com&#x2F;shoelace&#x2F;ianknot.htm</a><p>Seriously, spend 20 mins practising this, and you&#x27;ll never go back to the clumsy old way again.

I love the way this discussion has divided neatly into thirds: history of ringbuffers; digression on shoelaces; fragmentary, widely ignored, replies about everything else (this one included, I&#x27;m sure).<p>I like this kind of article and enjoyed this particular one, but the long discussion above about the &quot;right&quot; way to do it goes some way to justifying why so many people are happy to do it the &quot;wrong&quot; way.<p>I&#x27;ve implemented and used ring buffers the &quot;wrong&quot; way many times (with the modulus operator as well!) and the limitations of this method have never been a problem or bottleneck for me, while its simplicity means that it&#x27;s easier to write and understand than almost any other data structure.<p>In most practical applications, it&#x27;s memory barriers that you really have to worry about.

This is another interesting ring buffer implementation that uses mmap. <a href="https:&#x2F;&#x2F;github.com&#x2F;willemt&#x2F;cbuffer" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;willemt&#x2F;cbuffer</a>

The Linux kernel seems to leave one element free, which surprised me, but it does have this interesting note about it:<p><a href="https:&#x2F;&#x2F;www.kernel.org&#x2F;doc&#x2F;Documentation&#x2F;circular-buffers.txt" rel="nofollow">https:&#x2F;&#x2F;www.kernel.org&#x2F;doc&#x2F;Documentation&#x2F;circular-buffers.tx...</a><p><pre><code> Note that wake_up() does not guarantee any sort of barrier unless something is actually awakened. We therefore cannot rely on it for ordering. However, there is always one element of the array left empty. Therefore, the producer must produce two elements before it could possibly corrupt the element currently being read by the consumer. Therefore, the unlock-lock pair between consecutive invocations of the consumer provides the necessary ordering between the read of the index indicating that the consumer has vacated a given element and the write by the producer to that same element.</code></pre>

I have always considered these &quot;double ring&quot; buffers. Along the same lines as how you figure out which race car is in the race is in lead by their position <i>and</i> lap count. You run your indexes in the range 0 .. (2 * SIZE) and then empty is<p><pre><code> EMPTY -&gt; (read == write) FULL -&gt; (read == (write + SIZE) % (2 * SIZE)) </code></pre> Basically you&#x27;re full if you&#x27;re at the same relative index and your on different laps, you are empty if you at the same relative index on the same lap. If you do this with power of 2 size then the &#x27;lap&#x27; is just the bit 2 &lt;&lt; SIZE.

<i>Why do people use the version that&#x27;s inferior and more complicated?</i><p>Because it&#x27;s easier to understand at first glance, has no performance penalty, and for most busy programmers that often wins.

A very related post by ryg: <a href="https:&#x2F;&#x2F;fgiesen.wordpress.com&#x2F;2010&#x2F;12&#x2F;14&#x2F;ring-buffers-and-queues&#x2F;" rel="nofollow">https:&#x2F;&#x2F;fgiesen.wordpress.com&#x2F;2010&#x2F;12&#x2F;14&#x2F;ring-buffers-and-qu...</a>

Usually when I&#x27;m writing a ring buffer, it&#x27;s for tasks where the loss of an item is acceptable (even desirable - a destructive ring buffer for debugging messages is a fantastic tool). As such, I simply push the read indicator when I get to the r=1, w=1 case.<p>Using the mask method is slick (I&#x27;d cache that mask with the array to reduce runtime calculations), but it&#x27;s definitely going to add cognitive overhead and get messy if you want to make it lockless with CAS semantics.

From what I understand, this is the way you&#x27;d do it with hardware registers (maintain the read and write indices each with one extra MSB to detect the difference between full&#x2F;empty).<p>We&#x27;ve been using similar code in PortAudio since the late 90s[0]. I&#x27;m pretty sure Phil Burk got the idea from his hardware work.<p>[0] <a href="https:&#x2F;&#x2F;app.assembla.com&#x2F;spaces&#x2F;portaudio&#x2F;git&#x2F;source&#x2F;master&#x2F;src&#x2F;common&#x2F;pa_ringbuffer.c" rel="nofollow">https:&#x2F;&#x2F;app.assembla.com&#x2F;spaces&#x2F;portaudio&#x2F;git&#x2F;source&#x2F;master&#x2F;...</a>

&gt; This is of course not a new invention<p>No, this is a well known construct in digital design. Basically, for a 2^N deep queue you only need two N+1 bit variables:<p><a href="http:&#x2F;&#x2F;www.sunburst-design.com&#x2F;papers&#x2F;CummingsSNUG2002SJ_FIFO1.pdf" rel="nofollow">http:&#x2F;&#x2F;www.sunburst-design.com&#x2F;papers&#x2F;CummingsSNUG2002SJ_FIF...</a>

PicoLisp: last function here as circular buffer task <a href="https:&#x2F;&#x2F;bitbucket.org&#x2F;mihailp&#x2F;tankfeeder&#x2F;src&#x2F;3258edaded514ef010a1526d5a298eeaebed215d&#x2F;exercism-io&#x2F;a-f.l?at=default&amp;fileviewer=file-view-default" rel="nofollow">https:&#x2F;&#x2F;bitbucket.org&#x2F;mihailp&#x2F;tankfeeder&#x2F;src&#x2F;3258edaded514ef...</a><p>build in dynamic fifo function <a href="http:&#x2F;&#x2F;software-lab.de&#x2F;doc&#x2F;refF.html#fifo" rel="nofollow">http:&#x2F;&#x2F;software-lab.de&#x2F;doc&#x2F;refF.html#fifo</a>

&gt; <i>don&#x27;t squash the indices into the correct range when they are incremented, but when they are used to index into the array.</i><p>Great! Just don&#x27;t use it if the indices are N bits wide and the array has 2<i></i>N elements. :)<p>Not unheard of. E.g. tiny embedded system. 8 bit variables, 256 element buffer.

I had to pause for a second to convince myself that the version relying on integer wrap-around is actually correct.<p>I guess that&#x27;s the reason most people don&#x27;t do it: they&#x27;d rather waste O(1) space than waste mental effort on trying to save it.

He keeps stating the case of one-element ring buffer. Is that a real concern ever?

I find the headline very interesting. It&#x27;s very inviting because of the way it expresses a sort of epiphany about doing it wrong on a mundane programming task. One is tempted to read it in order to see if there is some great insight to this problem. just maybe it&#x27;s applicable outside this one problem. It begs the question: if he&#x27;s been doing it wrong on a fairly mundane thing, maybe I am too. I need to see what this is about.

Hmm..., interesting.<p>I&#x27;ve always been doing it the &quot;wrong&quot; way, mostly on embedded systems. My classic application is a ring buffer for the received characters over a serial port. What&#x27;s nice is that this sort of data structure doesn&#x27;t need a mutex or such to protect access. Only the ISR changes the head, and only the main routine changes the tail.

Just in case, StackOverflow has some variations for JavaScript, although not that much optimized ;)<p><a href="http:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;1583123&#x2F;circular-buffer-in-javascript" rel="nofollow">http:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;1583123&#x2F;circular-buffer-i...</a>

My C is rusty, but won&#x27;t this act... oddly... on integer overflow?<p><pre><code> size() { return write - read; } </code></pre> 0 - UINT_MAX -1 = ?<p>[EDIT] Changed constant to reflect use of unsigned integers, which I forgot to specify initially.

Dumb question: why use power of two sized rings? If I know the reader won&#x27;t be more than 100 behind the writer, isn&#x27;t it better to waste one element of a 101 sized rings instead of 28 of a 128 sized ring?

i love that he has 20 different shoelace knots! life was too simple before now.

His favored solution introduces subtlety and complexity. Remember that 20-year old binary search bug in the JDK a few years ago? That is the sort of bug that could be lurking in this solution.<p>I understand not wanting to waste one slot. A third variable (first, last, count) isn&#x27;t too bad. But if you really hate that third variable, why not just use first and count variables? You can then compute last from first and count, and the two boundary cases show up as count = 0 and count = capacity.

If you use modulus instead of bitmasking, it doesn&#x27;t have to be power-of-2 size, does it?

&gt; I&#x27;ve must have written a dozen ring buffers over the years<p>Why would someone do this instead of re-using previous (or third-party) implementations? Of course unless it&#x27;s all in different languages, but I don&#x27;t think that&#x27;s the case here.

&gt; So there I was, implementing a one element ring buffer. Which, I&#x27;m sure you&#x27;ll agree, is a perfectly reasonable data structure.<p>I didn&#x27;t even know what a ring buffer was<p>where do I dispose of my programmer membership card?<p>edit : lol, what a hostile reaction...