I've been writing ring buffers wrong all these years
1–10 of 175 posts
Re: I've been writing ring buffers wrong all these years
#2Why 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.
Re: I've been writing ring buffers wrong all these years
#3I 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.
Re: I've been writing ring buffers wrong all these years
#4> 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
Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.
Re: I've been writing ring buffers wrong all these years
#5If you use modulus instead of bitmasking, it doesn't have to be power-of-2 size, does it?
Re: I've been writing ring buffers wrong all these years
#6i love that he has 20 different shoelace knots! life was too simple before now.
Re: I've been writing ring buffers wrong all these years
#7If you use modulus instead of bitmasking, it doesn't have to be power-of-2 size, does it?
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.
Re: I've been writing ring buffers wrong all these years
#8Usually 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.
Re: I've been writing ring buffers wrong all these years
#9This 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.
Re: I've been writing ring buffers wrong all these years
#10Why 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.
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.