14 ms·

I've been writing ring buffers wrong all these years

361 points by b3h3moth 10y ago

ansible 10y ago
Hmm..., interesting. I've always been doing it the "wrong" way, mostly on embedded systems. My classic application is a ring buffer for the received characters over a serial port. What's nice is that this sort of data structure doesn't need a mutex or such to protect access. Only the ISR changes the head, and only the main routine changes the tail.
ams6110 10y ago
Why do people use the version that's inferior and more complicated? Because it's easier to understand at first glance, has no performance penalty, and for most busy programmers that often wins.
- falcolas 10y ago
  And you don't have expend any mental energy on the integer overflow edge case. It should be handled by using a bitmask and a power-of-2 sized array, should.
- hzhou321 10y ago
  The first version always leaves a "clean" state, that is both indices points to actual array locations. A mentally "clean" state makes understanding easier. For the third version one has to keep in mind the wrap around behavior of computer specific integers throughout the comprehension process, so it is a bit more difficult (to understand).
  - kbenson 10y ago
    The third version also allows for the write index to be a counter of total store operations, at least until overflow, which could be useful.
- gwu78 10y ago
  "Why do people use the version that's inferior and more complicated?" This question needs little context to be relevant, so long as the topic is "computer programming". Certainly not limited to writing ring buffers. It could be an apropos comment in almost any discussion. Of course in many cases, the part about "no performance penalty" does not apply. Performance is a routine trade off for some other perceived gain.
- deleted 10y ago
  [deleted]
- alfalfasprout 10y ago
  The reasoning comes down to how you use it. I use ringbuffers for ultra low latency buffering of market data for instance. If my ringbuffer is so full that I'm worried about its length approaching its capacity then I'm doing something wrong and I should be willing to lose the data. 1 element isn't going to make the difference. The real reason to stick with the first approach is that your static analysis tools won't freak out that you have intentional unsigned int overflow. Heck, some compilers will now scream at you for doing this. Then what happens when someone goes to port your code to a language with stricter overflow behavior? It won't work. IMO even in realtime systems, I don't use this. Heck, the linux kernel even uses the original version.
jstanley 10y ago
I had to pause for a second to convince myself that the version relying on integer wrap-around is actually correct. I guess that's the reason most people don't do it: they'd rather waste O(1) space than waste mental effort on trying to save it.
- deleted 10y ago
  [deleted]
phaemon 10y ago
> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.
- Bognar 10y ago
  The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.
  - chrisseaton 10y ago
    I don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.
    - wccrawford 10y ago
      From the site: "The finished "Ian Knot" is identical to either the Standard Shoelace Knot or the Two Loop Shoelace Knot. Because it was tied much more quickly and symmetrically, the laces suffer less wear and tear and thus last longer."
      - chrisseaton 10y ago
        Do people's laces wear out? That's not a problem I've ever experienced.
        greenshackle2 10y ago
        Laces on my boots wear out.
zimpenfish 10y ago
If you use modulus instead of bitmasking, it doesn't have to be power-of-2 size, does it?
- DblPlusUngood 10y ago
  No, the size of the array doesn't need to be a power-of-2 if you use modulus to derive indices. But you need to deal with the overflow somehow. For instance: 0xffffffff % 7 = 3, but (0xffffffff + 1) % 7 = 0.
  - RBerenguel 10y ago
    Also as mentioned elsewhere in the comments, modulo is expensive, even more for non-powers of 2
    - pklausler 10y ago
      Modulus by a power of two is cheap. Modulus by a constant is a multiplication by reciprocal and a shift. And if your argument is in [0..2N], mod N is just a conditional subtraction that doesn't even require a branch.
      - CorvusCrypto 10y ago
        cheap is relative right? I mean a multiplication can be spread over shift and add/sub instructions whereas a mask is just one instruction I think right?
    - tbirdz 10y ago
      That's only true if your compiler actually outputs a modulus instruction when it sees you doing N % pow2. It really should optimize that into N & (pow2-1) for you, so whether you write the & or the % it will end up running the cheap & version.
ts330 10y ago
i love that he has 20 different shoelace knots! life was too simple before now.
falcolas 10y ago
Usually when I'm writing a ring buffer, it'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. Using the mask method is slick (I'd cache that mask with the array to reduce runtime calculations), but it's definitely going to add cognitive overhead and get messy if you want to make it lockless with CAS semantics.
- Bartweiss 10y ago
  In general, this makes sense; certainly data you're putting into a ring buffer is data you're willing to lose. Doesn't it break the order invariant of the buffer, though? I can't see a way to do this without the risk of getting reads of newer data prior to older data. That's probably fine in many cases, but something like non-timestamped-debugging strikes me as a case where I'd want to know that the data arrived in the order I'm seeing.
  - falcolas 10y ago
    > Doesn't it break the order invariant of the buffer, though No, if you increment the read pointer prior to the write pointer, the read pointer will still point at the oldest valid value in the buffer. So, in pseudo code: if (w+1 >= r) { r = w + 2 } w++ b[w-1] = value For a debugging ring buffer (i.e. looking at it in a core file), you have the last value of the write pointer, so you can simply read from write pointer + 1 back around to the write pointer and have your messages in order. This makes the assumption that there is no readers of the debug buffer, so you're only having to deal with the one pointer.
  - dllthomas 10y ago
    > certainly data you're putting into a ring buffer is data you're willing to lose. When that's the case, a ring buffer is a great choice. It's not required, though - the writer could block when it detects a full buffer.
- blub 10y ago
  This is exactly what I was thinking. When pushing D in their example they overwrite the value to be read and items are out of order now. But maybe I'm missing something, I lost interest at all the bit-twiddling.
jgrahamc 10y ago
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 was doing this in 1992 so it'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/write pointers were atomic (in this case 'atomic' 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 not 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. It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask. Edit: having had this discussion I've realized that Juho's implementation is different from the 1992 implementation I was using because he doesn't ever reset the read/write indexes. Oops.
- kitsuac 10y ago
  It's odd that you were using ring buffers in 1992 for low level code but don't understand the value of avoiding a modulus instruction. Masking is far more efficient and often a ring buffer will be used in code where performance is absolutely critical.
  - jgrahamc 10y ago
    You wouldn't use the modulus operation. You aren't adding some arbitrary number that's going to make you increase either index by more than the buffer length so you know that at worse you are going to need to subtract the length of the buffer. IIRC the way we made this really fast was the write the buffer backwards. That way you can detect wrapping around the buffer because DEC will underflow and set the sign flag. Then you can JS to whatever code needs to ADD back the buffer length to handle the wrap around. But 2^n has another problem (back in that era): buffer size. You are stuck with 1K, 2K, 4K, etc. buffers. When memory is tight you likely need something very specific, so you end up with the solution we had. But, hey, if memory is free use 2^n bytes for your buffer.
dom0 10y ago
A very related post by ryg: https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-queues/ https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-qu...
- gcatlin 10y ago
  Another one by ryg: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/ https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...
RossBencina 10y ago
From what I understand, this is the way you'd do it with hardware registers (maintain the read and write indices each with one extra MSB to detect the difference between full/empty). We've been using similar code in PortAudio since the late 90s[0]. I'm pretty sure Phil Burk got the idea from his hardware work. [0] https://app.assembla.com/spaces/portaudio/git/source/master/src/common/pa_ringbuffer.c https://app.assembla.com/spaces/portaudio/git/source/master/...
hzhou321 10y ago
He keeps stating the case of one-element ring buffer. Is that a real concern ever?
- alanbernstein 10y ago
  It seemed like a sarcastic comment to me. Why would that ever be used?
  - jsnell 10y ago
    It's indeed a ridiculous data structure, but I did actually need it. It's a dynamically sized ring buffer with an optimization analogous to that of C++ strings; if the required capacity is small enough, the buffer is stored inline in the object rather than in a separate heap-allocated object. So something in the spirit of (but not exactly like): struct rb { union { Value* array; // Set N such that this array uses the same amount of space as the pointer. Value inline_array[N]; }; uint16_t read; uint16_t write; uint16_t capacity; } You'd dynamically switch between the two internal representations, and choose whether to read from array or inline_array based on whether capacity is larger than N. In this setup it'd be pretty common for N to be 1. Having to add a special case to every single method would kind of suck, generic code that could handle any size seemed like a nice property to have.
  - lomnakkus 10y ago
    Weirdly, I think Haskell has an equivalent: MVar. It has its (low-level) uses, but its quite hard to get any sort of non-trivial (non-rendezvous) synchronization protocol right. It's incredibly easy to deadlock. (But that may be mostly to do with the MVar's paucity of non-blocking primitives.)
- qb45 10y ago
  Probably it was a joke though one can imagine the size being configurable which surely would lead to interesting results if somebody sets it to 1 for some reason (like troubleshooting).
ChuckMcM 10y ago
I have always considered these "double ring" buffers. Along the same lines as how you figure out which race car is in the race is in lead by their position and lap count. You run your indexes in the range 0 .. (2 * SIZE) and then empty is EMPTY -> (read == write) FULL -> (read == (write + SIZE) % (2 * SIZE)) Basically you're full if you'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 'lap' is just the bit 2 << SIZE.
- nickodell 10y ago
  No, I think the author is using the full range of a 32 bit int. So read could be any 32 bit integer, even if the size of the ring is 1. (The trick is that SIZE has to be a power of two, or else when you increment from 2^32-1 to 0, your pointers will jump to a different position in the array.)
pawadu 10y ago
> This is of course not a new invention 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: http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO1.pdf http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIF...
planckscnst 10y ago
This is another interesting ring buffer implementation that uses mmap. https://github.com/willemt/cbuffer https://github.com/willemt/cbuffer
- leni536 10y ago
  With the additional benefit that one can have arbitrary slices between head and tail as a contiguous memory region.
- AndyKelley 10y ago
  Here's another implementation that works on Windows too: https://github.com/andrewrk/libsoundio/blob/master/src/ring_buffer.c https://github.com/andrewrk/libsoundio/blob/master/src/ring_...
  - csl 10y ago
    This seems to use modulus. The whole point of the mmap trick is to get the kernel/MMU to do the work for you, IIRC. EDIT: Oops, I see they use mirrored memory here as well.
- ohazi 10y ago
  That's so cool. Unfortunately for me, the one time I could have used something like this, I was working on an embedded system with no mmap / virtual memory.
- lomnakkus 10y ago
  I was waiting for someone to mention this -- it seemed much more interesting to me. It's a real classic in the "what the hell, you can do that?" category. (Bonus points if you've done it in a language that requires "extra data" for strings, like storing the length somewhere.) I must admit that I never actually benchmarked my implementation properly -- it might be interesting to see if there are actual trade-offs between mmap vs. copying. (I'm guessing that nothing can beat MMU support, but I think the MMU also supports copy operations, so...?)
- jevinskie 10y ago
falcolas 10y ago
My C is rusty, but won't this act... oddly... on integer overflow? size() { return write - read; } 0 - UINT_MAX -1 = ? [EDIT] Changed constant to reflect use of unsigned integers, which I forgot to specify initially.
- crististm 10y ago
  Actually, this method counts on it. What I find interesting are the trade-offs: machine vs explicit integer wrap-around and buffers with maximum ~size(int)/2 vs ~size(int).
  - falcolas 10y ago
    Got it. Modular arithmetic was the term I was looking for to resolve this. (0 - (2^32 - 1)) % 2^32 = 1
- mfukar 10y ago
  In all examples, `read` and `write` are unsigned, and since they both are the same type, no integer conversions are performed, ergo no overflow. PS. No wrap-around either, for different reasons.
  - falcolas 10y ago
    > No wrap-around either, for different reasons. You'll have to explain that to me, since I can't assign `x = 2^32` without wraparound when x is an unsigned 32 bit integer.
kazinator 10y ago
> don't squash the indices into the correct range when they are incremented, but when they are used to index into the array. Great! Just don't use it if the indices are N bits wide and the array has 2N elements. :) Not unheard of. E.g. tiny embedded system. 8 bit variables, 256 element buffer.
tankfeeder 10y ago
PicoLisp: last function here as circular buffer task https://bitbucket.org/mihailp/tankfeeder/src/3258edaded514ef010a1526d5a298eeaebed215d/exercism-io/a-f.l?at=default&fileviewer=file-view-default https://bitbucket.org/mihailp/tankfeeder/src/3258edaded514ef... build in dynamic fifo function http://software-lab.de/doc/refF.html#fifo http://software-lab.de/doc/refF.html#fifo
doktrin 10y ago
> So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure. I didn't even know what a ring buffer was where do I dispose of my programmer membership card? edit : lol, what a hostile reaction...
- doktrin 10y ago
  I honestly can't tell whether the downvotes are from elitist neckbeards or offended plebs pls explain I'd love to hear
  - mikekchar 10y ago
    Probably just because it doesn't add to the discussion. Though, from a certain standpoint it shows one of the problems with our education system pretty clearly. This is truly a fundamental technique. I don't know how one gets out of school without knowing it. It doesn't say anything about you, but it says a lot about what we are teaching people. Embarrassingly, for a long time I thought I had invented this technique ;-)
    - doktrin 10y ago
      I didn't attend college or graduate school (yeah ik ik I'm a pos), so that may well go a ways towards explaining my dumbassery
      - mikekchar 10y ago
        Don't worry. Programming and computer science is one of those things that anyone can learn on their own. If you don't mind some advice, though, try not to be embarrassed by things that you don't know. I can imagine that it is difficult, especially if you don't feel confident about your previous education. Even if most other people already know it, it just means that you have the pleasure of discovering it (as a certain XKCD comic pointed out). One thing I've said to many people starting out (especially those without an academic background in the area) is that there is a lot to learn. Sometimes at the beginning, you improve so quickly that it is easy to think, "I must be getting close to knowing it all". After several decades in the industry, though, I'm still learning brand new (to me!) , important things every single day. In many ways, the best programmers are the ones who can see how much they don't know, not how much they do know.
tveita 10y ago
The Linux kernel seems to leave one element free, which surprised me, but it does have this interesting note about it: https://www.kernel.org/doc/Documentation/circular-buffers.txt https://www.kernel.org/doc/Documentation/circular-buffers.tx... 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.
geophile 10y ago
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. I understand not wanting to waste one slot. A third variable (first, last, count) isn'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.
- simonbw 10y ago
  > Why not just use first and count variables? I think he addressed that in the post: The most common use for ring buffers is for it to be the intermediary between a concurrent reader and writer (be it two threads, to processes sharing memory, or a software process communicating with hardware). And for that, the index + size representation is kind of miserable. Both the reader and the writer will be writing to the length field, which is bad for caching. The read index and the length will also need to always be read and updated atomically, which would be awkward.
blauditore 10y ago
> I've must have written a dozen ring buffers over the years Why would someone do this instead of re-using previous (or third-party) implementations? Of course unless it's all in different languages, but I don't think that's the case here.
cannam 10y ago
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'm sure). I like this kind of article and enjoyed this particular one, but the long discussion above about the "right" way to do it goes some way to justifying why so many people are happy to do it the "wrong" way. I've implemented and used ring buffers the "wrong" 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's easier to write and understand than almost any other data structure. In most practical applications, it's memory barriers that you really have to worry about.
ared38 10y ago
Dumb question: why use power of two sized rings? If I know the reader won't be more than 100 behind the writer, isn't it better to waste one element of a 101 sized rings instead of 28 of a 128 sized ring?
phkahler 10y ago
I find the headline very interesting. It'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's applicable outside this one problem. It begs the question: if he's been doing it wrong on a fairly mundane thing, maybe I am too. I need to see what this is about.
- buzzybee 10y ago
  I believe it's very common to find little variations on algorithms or coding style like this that could produce a nice gain in efficiency or elegance. They aren't really the same problem as whole-system engineering, though, since most of your bottlenecks come from the algorithm that is completely unsuitable, not the one that is a little bit suboptimal.
noiv 10y ago
Just in case, StackOverflow has some variations for JavaScript, although not that much optimized ;) http://stackoverflow.com/questions/1583123/circular-buffer-in-javascript http://stackoverflow.com/questions/1583123/circular-buffer-i...

361 points by b3h3moth 10y ago

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

ams6110 10y ago

Why do people use the version that's inferior and more complicated? Because it's easier to understand at first glance, has no performance penalty, and for most busy programmers that often wins.

falcolas 10y ago
And you don't have expend any mental energy on the integer overflow edge case. It should be handled by using a bitmask and a power-of-2 sized array, should.
hzhou321 10y ago
The first version always leaves a "clean" state, that is both indices points to actual array locations. A mentally "clean" state makes understanding easier. For the third version one has to keep in mind the wrap around behavior of computer specific integers throughout the comprehension process, so it is a bit more difficult (to understand).
- kbenson 10y ago
  The third version also allows for the write index to be a counter of total store operations, at least until overflow, which could be useful.
gwu78 10y ago
"Why do people use the version that's inferior and more complicated?" This question needs little context to be relevant, so long as the topic is "computer programming". Certainly not limited to writing ring buffers. It could be an apropos comment in almost any discussion. Of course in many cases, the part about "no performance penalty" does not apply. Performance is a routine trade off for some other perceived gain.
deleted 10y ago
[deleted]
alfalfasprout 10y ago
The reasoning comes down to how you use it. I use ringbuffers for ultra low latency buffering of market data for instance. If my ringbuffer is so full that I'm worried about its length approaching its capacity then I'm doing something wrong and I should be willing to lose the data. 1 element isn't going to make the difference. The real reason to stick with the first approach is that your static analysis tools won't freak out that you have intentional unsigned int overflow. Heck, some compilers will now scream at you for doing this. Then what happens when someone goes to port your code to a language with stricter overflow behavior? It won't work. IMO even in realtime systems, I don't use this. Heck, the linux kernel even uses the original version.

jstanley 10y ago

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

deleted 10y ago
[deleted]

phaemon 10y ago

> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.

Bognar 10y ago
The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.
- chrisseaton 10y ago
  I don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.
  - wccrawford 10y ago
    From the site: "The finished "Ian Knot" is identical to either the Standard Shoelace Knot or the Two Loop Shoelace Knot. Because it was tied much more quickly and symmetrically, the laces suffer less wear and tear and thus last longer."
    - chrisseaton 10y ago
      Do people's laces wear out? That's not a problem I've ever experienced.
      - greenshackle2 10y ago
        Laces on my boots wear out.

zimpenfish 10y ago

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

DblPlusUngood 10y ago
No, the size of the array doesn't need to be a power-of-2 if you use modulus to derive indices. But you need to deal with the overflow somehow. For instance: 0xffffffff % 7 = 3, but (0xffffffff + 1) % 7 = 0.
- RBerenguel 10y ago
  Also as mentioned elsewhere in the comments, modulo is expensive, even more for non-powers of 2
  - pklausler 10y ago
    Modulus by a power of two is cheap. Modulus by a constant is a multiplication by reciprocal and a shift. And if your argument is in [0..2N], mod N is just a conditional subtraction that doesn't even require a branch.
    - CorvusCrypto 10y ago
      cheap is relative right? I mean a multiplication can be spread over shift and add/sub instructions whereas a mask is just one instruction I think right?
  - tbirdz 10y ago
    That's only true if your compiler actually outputs a modulus instruction when it sees you doing N % pow2. It really should optimize that into N & (pow2-1) for you, so whether you write the & or the % it will end up running the cheap & version.

ts330 10y ago

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

falcolas 10y ago

Usually when I'm writing a ring buffer, it'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. Using the mask method is slick (I'd cache that mask with the array to reduce runtime calculations), but it's definitely going to add cognitive overhead and get messy if you want to make it lockless with CAS semantics.

Bartweiss 10y ago
In general, this makes sense; certainly data you're putting into a ring buffer is data you're willing to lose. Doesn't it break the order invariant of the buffer, though? I can't see a way to do this without the risk of getting reads of newer data prior to older data. That's probably fine in many cases, but something like non-timestamped-debugging strikes me as a case where I'd want to know that the data arrived in the order I'm seeing.
- falcolas 10y ago
  > Doesn't it break the order invariant of the buffer, though No, if you increment the read pointer prior to the write pointer, the read pointer will still point at the oldest valid value in the buffer. So, in pseudo code: if (w+1 >= r) { r = w + 2 } w++ b[w-1] = value For a debugging ring buffer (i.e. looking at it in a core file), you have the last value of the write pointer, so you can simply read from write pointer + 1 back around to the write pointer and have your messages in order. This makes the assumption that there is no readers of the debug buffer, so you're only having to deal with the one pointer.
- dllthomas 10y ago
  > certainly data you're putting into a ring buffer is data you're willing to lose. When that's the case, a ring buffer is a great choice. It's not required, though - the writer could block when it detects a full buffer.
blub 10y ago
This is exactly what I was thinking. When pushing D in their example they overwrite the value to be read and items are out of order now. But maybe I'm missing something, I lost interest at all the bit-twiddling.

jgrahamc 10y ago

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 was doing this in 1992 so it'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/write pointers were atomic (in this case 'atomic' 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 not 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. It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask. Edit: having had this discussion I've realized that Juho's implementation is different from the 1992 implementation I was using because he doesn't ever reset the read/write indexes. Oops.

kitsuac 10y ago
It's odd that you were using ring buffers in 1992 for low level code but don't understand the value of avoiding a modulus instruction. Masking is far more efficient and often a ring buffer will be used in code where performance is absolutely critical.
- jgrahamc 10y ago
  You wouldn't use the modulus operation. You aren't adding some arbitrary number that's going to make you increase either index by more than the buffer length so you know that at worse you are going to need to subtract the length of the buffer. IIRC the way we made this really fast was the write the buffer backwards. That way you can detect wrapping around the buffer because DEC will underflow and set the sign flag. Then you can JS to whatever code needs to ADD back the buffer length to handle the wrap around. But 2^n has another problem (back in that era): buffer size. You are stuck with 1K, 2K, 4K, etc. buffers. When memory is tight you likely need something very specific, so you end up with the solution we had. But, hey, if memory is free use 2^n bytes for your buffer.

dom0 10y ago

A very related post by ryg: https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-queues/ https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-qu...

gcatlin 10y ago
Another one by ryg: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/ https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...

RossBencina 10y ago

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

hzhou321 10y ago

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

alanbernstein 10y ago
It seemed like a sarcastic comment to me. Why would that ever be used?
- jsnell 10y ago
  It's indeed a ridiculous data structure, but I did actually need it. It's a dynamically sized ring buffer with an optimization analogous to that of C++ strings; if the required capacity is small enough, the buffer is stored inline in the object rather than in a separate heap-allocated object. So something in the spirit of (but not exactly like): struct rb { union { Value* array; // Set N such that this array uses the same amount of space as the pointer. Value inline_array[N]; }; uint16_t read; uint16_t write; uint16_t capacity; } You'd dynamically switch between the two internal representations, and choose whether to read from array or inline_array based on whether capacity is larger than N. In this setup it'd be pretty common for N to be 1. Having to add a special case to every single method would kind of suck, generic code that could handle any size seemed like a nice property to have.
- lomnakkus 10y ago
  Weirdly, I think Haskell has an equivalent: MVar. It has its (low-level) uses, but its quite hard to get any sort of non-trivial (non-rendezvous) synchronization protocol right. It's incredibly easy to deadlock. (But that may be mostly to do with the MVar's paucity of non-blocking primitives.)
qb45 10y ago
Probably it was a joke though one can imagine the size being configurable which surely would lead to interesting results if somebody sets it to 1 for some reason (like troubleshooting).

ChuckMcM 10y ago

I have always considered these "double ring" buffers. Along the same lines as how you figure out which race car is in the race is in lead by their position and lap count. You run your indexes in the range 0 .. (2 * SIZE) and then empty is EMPTY -> (read == write) FULL -> (read == (write + SIZE) % (2 * SIZE)) Basically you're full if you'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 'lap' is just the bit 2 << SIZE.

nickodell 10y ago
No, I think the author is using the full range of a 32 bit int. So read could be any 32 bit integer, even if the size of the ring is 1. (The trick is that SIZE has to be a power of two, or else when you increment from 2^32-1 to 0, your pointers will jump to a different position in the array.)

pawadu 10y ago

> This is of course not a new invention 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: http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO1.pdf http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIF...

planckscnst 10y ago

This is another interesting ring buffer implementation that uses mmap. https://github.com/willemt/cbuffer https://github.com/willemt/cbuffer

leni536 10y ago
With the additional benefit that one can have arbitrary slices between head and tail as a contiguous memory region.
AndyKelley 10y ago
Here's another implementation that works on Windows too: https://github.com/andrewrk/libsoundio/blob/master/src/ring_buffer.c https://github.com/andrewrk/libsoundio/blob/master/src/ring_...
- csl 10y ago
  This seems to use modulus. The whole point of the mmap trick is to get the kernel/MMU to do the work for you, IIRC. EDIT: Oops, I see they use mirrored memory here as well.
ohazi 10y ago
That's so cool. Unfortunately for me, the one time I could have used something like this, I was working on an embedded system with no mmap / virtual memory.
lomnakkus 10y ago
I was waiting for someone to mention this -- it seemed much more interesting to me. It's a real classic in the "what the hell, you can do that?" category. (Bonus points if you've done it in a language that requires "extra data" for strings, like storing the length somewhere.) I must admit that I never actually benchmarked my implementation properly -- it might be interesting to see if there are actual trade-offs between mmap vs. copying. (I'm guessing that nothing can beat MMU support, but I think the MMU also supports copy operations, so...?)
jevinskie 10y ago

falcolas 10y ago

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

crististm 10y ago
Actually, this method counts on it. What I find interesting are the trade-offs: machine vs explicit integer wrap-around and buffers with maximum ~size(int)/2 vs ~size(int).
- falcolas 10y ago
  Got it. Modular arithmetic was the term I was looking for to resolve this. (0 - (2^32 - 1)) % 2^32 = 1
mfukar 10y ago
In all examples, `read` and `write` are unsigned, and since they both are the same type, no integer conversions are performed, ergo no overflow. PS. No wrap-around either, for different reasons.
- falcolas 10y ago
  > No wrap-around either, for different reasons. You'll have to explain that to me, since I can't assign `x = 2^32` without wraparound when x is an unsigned 32 bit integer.

kazinator 10y ago

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

tankfeeder 10y ago

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

doktrin 10y ago

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

doktrin 10y ago
I honestly can't tell whether the downvotes are from elitist neckbeards or offended plebs pls explain I'd love to hear
- mikekchar 10y ago
  Probably just because it doesn't add to the discussion. Though, from a certain standpoint it shows one of the problems with our education system pretty clearly. This is truly a fundamental technique. I don't know how one gets out of school without knowing it. It doesn't say anything about you, but it says a lot about what we are teaching people. Embarrassingly, for a long time I thought I had invented this technique ;-)
  - doktrin 10y ago
    I didn't attend college or graduate school (yeah ik ik I'm a pos), so that may well go a ways towards explaining my dumbassery
    - mikekchar 10y ago
      Don't worry. Programming and computer science is one of those things that anyone can learn on their own. If you don't mind some advice, though, try not to be embarrassed by things that you don't know. I can imagine that it is difficult, especially if you don't feel confident about your previous education. Even if most other people already know it, it just means that you have the pleasure of discovering it (as a certain XKCD comic pointed out). One thing I've said to many people starting out (especially those without an academic background in the area) is that there is a lot to learn. Sometimes at the beginning, you improve so quickly that it is easy to think, "I must be getting close to knowing it all". After several decades in the industry, though, I'm still learning brand new (to me!) , important things every single day. In many ways, the best programmers are the ones who can see how much they don't know, not how much they do know.

tveita 10y ago

The Linux kernel seems to leave one element free, which surprised me, but it does have this interesting note about it: https://www.kernel.org/doc/Documentation/circular-buffers.txt https://www.kernel.org/doc/Documentation/circular-buffers.tx... 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.

geophile 10y ago

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. I understand not wanting to waste one slot. A third variable (first, last, count) isn'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.

simonbw 10y ago
> Why not just use first and count variables? I think he addressed that in the post: The most common use for ring buffers is for it to be the intermediary between a concurrent reader and writer (be it two threads, to processes sharing memory, or a software process communicating with hardware). And for that, the index + size representation is kind of miserable. Both the reader and the writer will be writing to the length field, which is bad for caching. The read index and the length will also need to always be read and updated atomically, which would be awkward.

blauditore 10y ago

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

cannam 10y ago

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'm sure). I like this kind of article and enjoyed this particular one, but the long discussion above about the "right" way to do it goes some way to justifying why so many people are happy to do it the "wrong" way. I've implemented and used ring buffers the "wrong" 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's easier to write and understand than almost any other data structure. In most practical applications, it's memory barriers that you really have to worry about.

ared38 10y ago

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

phkahler 10y ago

I find the headline very interesting. It'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's applicable outside this one problem. It begs the question: if he's been doing it wrong on a fairly mundane thing, maybe I am too. I need to see what this is about.

buzzybee 10y ago
I believe it's very common to find little variations on algorithms or coding style like this that could produce a nice gain in efficiency or elegance. They aren't really the same problem as whole-system engineering, though, since most of your bottlenecks come from the algorithm that is completely unsuitable, not the one that is a little bit suboptimal.

noiv 10y ago

Just in case, StackOverflow has some variations for JavaScript, although not that much optimized ;) http://stackoverflow.com/questions/1583123/circular-buffer-in-javascript http://stackoverflow.com/questions/1583123/circular-buffer-i...