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

51–60 of 69 posts

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

#51

Post by RossBencina »

azemetre wrote: post #13
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…

Your link has an invalid cert FYI, but do appreciate the knowledge drop. Rung buffers are some of the cooler data structures out there.

Unfortunately the original source is now behind a sign-in-wall.

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

#52

Post by spacechild1 »

> All of those seem like non-issues. What kind of a monster would make a non-power of two ring anyway?

Huh? Anytime you want to restrict the buffer to a specific size, you will have to support non-power-of-two capacities. There are cases where the capacity of the ring buffer determines the latency of the system, e.g. an audio ringbuffer or a network jitter buffer.

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

#53

Post by KeplerBoy »

hinkley wrote: post #19
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…

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…

It's not just Intel is it, AMD is also using 64 byte cache lines afaik.

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

#54

Post by gpderetta »

tom_ wrote: post #36
thaumasiotes wrote: post #35

Earlier quoted context omitted.

> but when the period would be something like 50 years I don't think it's actually a problem I think you have that backwards. If something needs to be done every week, it will get done every week. That's not a problem. If something needs to be done every fifty years, you'll be lucky if it happens once.

My parting shot was slightly tongue in cheek, apologies. Fifty years is a long time. The process, whatever it is, will have been replaced or otherwise become irrelevant long before the period is up. 64 bits will be sufficient.

At some point a random bitflip becomes more likely than the counter overflowing.

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

#55

Post by IsTom »

ekropotin wrote: post #29
Neywiny wrote: post #27

Earlier quoted context omitted.

And yet here I sit, writing ring buffers, and never thinking about this idea. Probably because of the power of two issue. Which isn't actually a problem because as he points out, who would do that? But it makes me think that it's a restriction that it just isn't. But in all honesty, look for more embedded jobs, then. We can certainly use the help.

For some unexplainable reason, CRUD job’s pay is better than embedded, on average.

Probably there are less people excited to make another CRUD app than to write embedded code.

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

#56

Post by myrmidon »

ErroneousBosh wrote: post #49
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…

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

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

#57

Post by aldonius »

z3t4 wrote: post #44

Why would you ever want a data structure that wraps around!? What a headache! Is it a memory constraint or optimization!? All I can think about is a physical knob where you want to know what position it is in.

It's a somewhat different kind of ring buffer, because there's just one index, but I used it in my signal processing class for a finite-impulse-response filter.

Choose N to be a power of two >= the length of your filter.

Increment index i mod N, write the sample at buffer position x[i], output sum of x[i-k mod N] * a[k] where a[k] are your filter coefficients, repeat with next sample at next time step.

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

#58

Post by Neywiny »

nathan_douglas wrote: post #34
Neywiny wrote: post #27

Earlier quoted context omitted.

And yet here I sit, writing ring buffers, and never thinking about this idea. Probably because of the power of two issue. Which isn't actually a problem because as he points out, who would do that? But it makes me think that it's a restriction that it just isn't. But in all honesty, look for more embedded jobs, then. We can certainly use the help.

What do you work with (if you don't mind answering)? I'm looking for a change and like low-level stuff about as much as I like any other level. I've done some cycle-accurate NES emulation and VM implementation stuff - I'm not much of a DSA guy but performance and efficiency appeal to me.

I work with pretty much everything (except GPUs I guess). Embedded is extremely relative. To some, embedded means a rack mount server that's idk embedded in a vehicle instead of a datacenter. That's not me. To others, embedded means a 4-bit low power, mask-rom fed micro inside a sensor IC. That's also not me.

So I work with microcontrollers of various vendors, I do FPGA with hard and soft processors, recently did just past the smoke test through embedded Linux on a SoC, and I've done plenty of desktop code on Linux and Windows for interfacing. I get to work with a wide range of devices and a wide range of tasks for them. Might not pay as much but my goodness is it fun

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

#59

Post by ErroneousBosh »

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…

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.

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

#60

Post by thrtythreeforty »

nly wrote: post #46

Most people implement them now in my field using mmap tricks so the CPU can do the wraparound for you in virtual memory. Makes the code trivial

Not only that, but you can also always form a normal (ptr, size) slice reference to any piece of the ring buffer, even when it wraps. This is really helpful for Eigen arrays that you need to rotate.
Post reply on HN