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 (2016)

snellman.net

Post reply on HN
Print view View original

61–69 of 69 posts

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

#61

Post by myrmidon »

ErroneousBosh wrote: post #59
myrmidon wrote: post #56

Earlier quoted context omitted.

Replacing just the mask operation is not enough. The problem is incrementing past the index integer type limit. Consider a simple example with ring buffer size 9, and 16bit indices: When you increment the write index from 0xffff to 0, your "masked index" jumps from 6 (0xffff % 9) to 0 (instead of 7). There is no elegant fix that I'm aware of (using a very wide index type, like possibly a uint64, is extremely non-eleg…

Yes, that's what I'm saying. You can't just use a quick and easy mask, you have to use a modulo operator which is computationally expensive enough that it's probably killing the time savings you made elsewhere. There's probably no good reason to make your buffer sizes NOT a power of two, though. If memory's that tight, maybe look elsewhere first.

What I mean is: This ringbuffer implementation (and its simplicity) relies on the index range being a multiple of the buffer size (which is only true for powers of two, when the index is e.g. a 32bit unsigned integer).

If you swap bitmasking for modulo operations then that does work at first glance, but breaks down when the index wraps around. This forces you to abandon the simple "increment" operation for something more complex, too.

The requirement for a power-of-two size is more intrinsic to the approach than just the bitmasking operation itself.

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

#62

Post by msm_ »

atq2119 wrote: post #47

It's a silly offhand remark at the end of the article, but anybody who is genuinely interested in whether they've been tying their shoes wrong will enjoy Ian's shoelace site: https://www.fieggen.com/shoelace/

I thought you're joking, but then I opened https://www.fieggen.com/shoelace/grannyknot.htm

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

#63

Post by hinkley »

rcoveson wrote: post #21
hinkley wrote: post #19

Earlier quoted context omitted.

I think unfortunately we sometimes ascribe to powers of two supernatural powers that are really about caches being built in powers of two. Intel is still 64 byte cache lines as they have been for quite a long time but they also do some shenanigans on the bus where they try to fetch two lines when you ask for one. So there’s ostensibly some benefit of aligning data particularly on linear scans to 128 byte alignment fo…

But there's a reason that caches are always sized in powers of two as well, and that same reason is applicable to high-performance ring buffers: Division by powers of two is easy and easy is fast. It's reliably a single cycle, compared to division by arbitrary 32bit integers which can be 8-30 cycles depending on CPU. Also, there's another benefit downstream of that one: Powers of two work as a schelling point for all…

CPU Caches are powers of two because retrieval involves a logarithmic number of gates have to fire in a clock cycle. There is a saddle point where more cache starts to make the instructions per second start to go back down again, and that number will be a power of two.

That has next to nothing to do with how much of your 128 GB of RAM should be dedicated to any one data structure, because working memory for a task is the sum of a bunch of different data structures that have to fit into both the caches and main memory, which used to be powers of two but now main memory is often 2^n x 3.

And as someone else pointed out, the optimal growth factor for resizable data structures is not 2, but the golden ratio, 1.61. But most implementations use 1.5 aka 3/2.

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

#64

Post by waffletower »

RossBencina wrote: post #10

It is not just a way of writing ring buffers. It's a way of implementing concurrent non-blocking single-reader single-writer atomic ring buffers with only atomic load and store (and memory barriers). The author says that non-power-of-two is not possible, but I'm pretty sure it is if you use a conditional instead of integer modulus. I first learnt of this technique from Phil Burk, we've been using it in PortAudio fore…

Regardless of correctness, as a DSP dork I really identified with the question: "What kind of a monster would make a non-power of two ring anyway?" I remember thinking similarly when requesting a power of two buffer from a 3rd party audio hardware device and having it correct to a nearby non-power of two. Latency adding ringbuffer to the rescue.

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

#65

Post by mrcode007 »

spockz wrote: post #8
mrcode007 wrote: post #5

Earlier quoted context omitted.

There is one more way that is truly lock free. Most lock free implementations relying on atomic compare and swap instructions are not lock free afaik; they have a lock on the cache line in the CPU (in a way you go away from global lock to many distributed locks). There is one more mechanism that allows implementing ring buffers without having to compare head and tail buffers at all (and doesn’t rely on counters or em…

Interesting! Do you know of an example implementation of this?

Yes. [1] has background, [2] has the implementation (fig 2. pseudocode). Since you understood my comment I trust you can figure out the rest :) it’s a very neat trick.

[1]https://www.microsoft.com/en-us/research/publication/concurr... [2]https://arxiv.org/pdf/1012.1824

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

#66

Post by mrcode007 »

dooglius wrote: post #11
mrcode007 wrote: post #5

Earlier quoted context omitted.

There is one more way that is truly lock free. Most lock free implementations relying on atomic compare and swap instructions are not lock free afaik; they have a lock on the cache line in the CPU (in a way you go away from global lock to many distributed locks). There is one more mechanism that allows implementing ring buffers without having to compare head and tail buffers at all (and doesn’t rely on counters or em…

That's not how "lock free" is defined/used. If you are considering the MESI M state to be a "lock" then you also have to grant that any write instruction is a "lock".

In fact this a crux of the problem in low latency code and there are ways to combat this.

I know there is an academic wait-free and lock-free definition but folks use those often incorrectly as a slogan that something is magically better because it’s „lockfree”.

Imagine how _you_ would implement a read-modify-write atomic in the CPU and why E stands for exclusive (sort of like exclusive in a mutex)

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

#67

Post by ErroneousBosh »

myrmidon wrote: post #61
ErroneousBosh wrote: post #59

Earlier quoted context omitted.

Yes, that's what I'm saying. You can't just use a quick and easy mask, you have to use a modulo operator which is computationally expensive enough that it's probably killing the time savings you made elsewhere. There's probably no good reason to make your buffer sizes NOT a power of two, though. If memory's that tight, maybe look elsewhere first.

What I mean is: This ringbuffer implementation (and its simplicity) relies on the index range being a multiple of the buffer size (which is only true for powers of two, when the index is e.g. a 32bit unsigned integer). If you swap bitmasking for modulo operations then that does work at first glance, but breaks down when the index wraps around. This forces you to abandon the simple "increment" operation for something…

Yes, I get you now. If you let it roll over and you apply a modulo operation, now you have two modulo operations :-)

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

#68

Post by zephen »

The article author claims that his new version is simpler than the old version.

But the new version is really only simpler TEXTUALLY, because of the post-increment operators:

push(val) { assert(!full()); array[mask(write++)] = val; }

shift() { assert(!empty()); return array[mask(read++)]; }

(If you look at assembly output, it's probably the same or more code.)

But, at least in some languages, those increments might happen before the array access, which could mean that using them causes a race condition.

In fact, in C or C++, those increments are GUARANTEED to happen before the access to array, because they are guaranteed to happen before the calls to mask.

tl;dr -- dude claims to insure he can utilize one more character of his buffer, while writing code that ensures that if he is truly operating at the margins, he will be doing things in the wrong order.

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

#69

Post by aidenn0 »

myrmidon wrote: post #56
ErroneousBosh wrote: post #49

Earlier quoted context omitted.

> The author says that non-power-of-two is not possible, but I'm pretty sure it is if you use a conditional instead of integer modulus. I don't see why it wouldn't be, it's just computationally expensive to take the modulo value of the pointer rather than just masking off the appropriate number of bits.

Replacing just the mask operation is not enough. The problem is incrementing past the index integer type limit. Consider a simple example with ring buffer size 9, and 16bit indices: When you increment the write index from 0xffff to 0, your "masked index" jumps from 6 (0xffff % 9) to 0 (instead of 7). There is no elegant fix that I'm aware of (using a very wide index type, like possibly a uint64, is extremely non-eleg…

Everything still works if you unconditionally modulo by any multiple of 9 between 18 and 0xffff, but that's very expensive.
Post reply on HN