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

101–110 of 175 posts

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

#101

Post by to3m »

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.

Have you tested this recently? I haven't for some years now but performance was identical regardless of direction. Maybe I need to try it again. I'd expect going backwards to be no worse than "not as good" - like say perhaps the prefetching mechanism doesn't cater for this case - but maybe my standards aren't high enough and this is enough to tip things over into the horrific.

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

#103

Post by tbirdz »

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.

>iterating backward through memory is horrific for cache performance

This isn't true for Intel chips since Netburst Pentium 4. The hardware prefetchers can handle predicting iterating through an array forwards, backwards, and even strided accesses [0]. The arrays takes up the same number of cache lines in both cases, so going forwards or backwards are still going to have the same number of cache misses.

0: https://software.intel.com/en-us/articles/optimizing-applica...

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

#104

Post by tbirdz »

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

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.

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

#105

Post by ohazi »

planckscnst wrote: post #38

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

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.

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

#106

Post by pklausler »

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…

For what it's worth, Seymour Cray's Control Data 6600 implemented ring buffers for I/O channels correctly in hardware using gumdrop-sized single transistors in 1963. This is not exactly a new technology.

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

#107

Post by astrodust »

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.

It depends on the type of eyelets you have, your shoelaces, and how tightly you lace your shoes.

Some eyelets are basically razor blades, they have very sharp edges, and tight tugging can cause wear in a very narrow spot.

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

#108

Post by csl »

AndyKelley wrote: post #102
planckscnst wrote: post #38

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

Here's another implementation that works on Windows too: https://github.com/andrewrk/libsoundio/blob/master/src/ring_...

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.

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

#109

Post by dllthomas »

pklausler wrote: post #74
dllthomas wrote: post #37

Earlier quoted context omitted.

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.

Good point!

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

#110

Post by dllthomas »

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…

> (I'd cache that mask with the array to reduce runtime calculations)

So, store size-1 instead of size, and add one when asked for the size? I can see that, though I'm not confident it's worth the conceptual overhead.

If you mean storing it in addition to the size, I think that's a bad trade - cache is far more precious than many decrements.

Of course, if the size is fixed at compile time, the mask will probably be stored baked into the instructions (andl , ...).

Post reply on HN