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

71–80 of 175 posts

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

#71

Post by dllthomas »

falcolas wrote: post #61
dllthomas wrote: post #44

Earlier quoted context omitted.

This is not the problem. You are assuming still using &, which is very obviously incorrect with a very obvious fix (%5) which is still wrong because of behavior at overflow.

I'm answering the specific problem posed by the OP, given his other comments in this thread. [EDIT] Resolved internal concerns about size calculations.

You might have misread the OP. He's not asking why using & for the mask requires a 2^n sized buffer. He's asking why bother using & when it imposes these additional constraints on us. A part of the answer is that the constraints are already there with this approach, even if you pick a different function for masking than f(i,n) = i & (n - 1) -- which point OP only recently understood due to a misreading of the article.

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

#73

Post by __david__ »

to3m wrote: post #68
chrisseaton wrote: post #65

Earlier quoted context omitted.

Do people's laces wear out? That's not a problem I've ever experienced.

I've had a shoelaces break maybe 3-4 times on shoes I wore regularly for more than 2-3 years. It's annoying out of all proportion to the expense involved. (The plastic bits at the end can also get frayed and fall off, which happens more quickly, but I'm not sure knot style has much to do with that.)

I think it's so annoying because of the timing. I've never had one break when untying the knot or when just walking around. It's always while tying it which means I was just about to leave and now life has thrown a monkey wrench into my plans. Depending on how close I am cutting things, this may be an event that makes me late. Grrrrrr. Stupid shoelace!

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

#74

Post by pklausler »

dllthomas wrote: post #37
jstimpfle wrote: post #21

Earlier quoted context omitted.

Don't use a modulo then. Use subtraction.

Subtraction requires a branch, which could be worse (or not) depending on architecture.

Oh, come on, you don't need a branch to do a conditional subtraction. Reify the condition to 0/1 and use multiplication, or use AND with a two's complement of the condition.

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

#75

Post by dllthomas »

chrisseaton wrote: post #65
wccrawford wrote: post #34

Earlier quoted context omitted.

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

Do people's laces wear out? That's not a problem I've ever experienced.

Add me to the pile of people who have experienced this problem more than once.

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

#76

Post by kitsuac »

jgrahamc wrote: post #15
kitsuac wrote: post #12

Earlier quoted context omitted.

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.

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

You are still introducing a conditional by detecting the need to subtract, and iterating backward through memory is horrific for cache performance. If you need a specific, non power-of-2 sized buffer, then of course you make that design decision and pay the performance penalty. But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer.

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

#77

Post by nickodell »

ChuckMcM wrote: post #27

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…

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

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

#78

Post by pklausler »

RBerenguel wrote: post #51
DblPlusUngood wrote: post #7

Earlier quoted context omitted.

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.

Also as mentioned elsewhere in the comments, modulo is expensive, even more for non-powers of 2

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.

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

#79

Post by wglb »

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…

I was doing this in 1992 so it's at least 12 years older than the 2004 implementation

Try late 1960s. Generally known then, widely used.

For an interesting proof about tokens in ring buffers, check out https://www.cs.utexas.edu/users/EWD/ewd04xx/EWD426.PDF, which, for 1974, has an interesting bit of multiprocessing.

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

#80

Post by jgrahamc »

kitsuac wrote: post #76
jgrahamc wrote: post #15

Earlier quoted context omitted.

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

You are still introducing a conditional by detecting the need to subtract, and iterating backward through memory is horrific for cache performance. If you need a specific, non power-of-2 sized buffer, then of course you make that design decision and pay the performance penalty. But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer.

The 286/386 didn't have a cache so that wasn't a worry at that time.
Post reply on HN