Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I've been writing ring buffers wrong all these years

snellman.net

Post reply on HN
Print view View original

21–30 of 175 posts

Re: I've been writing ring buffers wrong all these years

#21

Post by jstimpfle »

fla wrote: post #13
jgrahamc wrote: post #9

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 bef…

Depending on the machine, a modulo can cost _alot_ . Last time I checked, the operation cost was 26k cycles on my PIC. Using a 2^n + mask made my queue perform 10 times faster (if not more).

Don't use a modulo then. Use subtraction.

Re: I've been writing ring buffers wrong all these years

#22

Post by Bartweiss »

falcolas wrote: post #8

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 m…

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.

Re: I've been writing ring buffers wrong all these years

#23

Post by flnz »

phaemon wrote: post #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.

thank you for this link. I didn't know about this website and I find it amazing. I just upgraded my shoes to a Secure Knot.

Re: I've been writing ring buffers wrong all these years

#24

Post by RossBencina »

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/...

Re: I've been writing ring buffers wrong all these years

#25

Post by hzhou321 »

ams6110 wrote: post #2

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.

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).

Re: I've been writing ring buffers wrong all these years

#27

Post by ChuckMcM »

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.

Re: I've been writing ring buffers wrong all these years

#29

Post by chrisseaton »

Bognar wrote: post #19
phaemon wrote: post #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.

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 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.

I don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.

Re: I've been writing ring buffers wrong all these years

#30

Post by tmaly »

Bognar wrote: post #19
phaemon wrote: post #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.

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 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.

These look like variations on the square knot. How is he the inventor? I was looking at a field scout manual dated 1948 the other night where they have this same knot.
Post reply on HN