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

21–30 of 69 posts

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

#21

Post by rcoveson »

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…

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 allocations. Picking powers of two for resizable vectors maximizes "good luck" when you malloc/realloc in most allocators, in part because e.g. a buddy allocator is probably also implemented using power-of-two allocations for the above reason, but also for the plain reason that other users of the same allocator are more likely to have requested power of two allocations. Spontaneous coordination is a benefit all its own. Almost supernatural! :)

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

#22

Post by avadodin »

ekropotin wrote: post #15

I’m jealous of people, who have to write ring buffers for work. It feels like 90% swe jobs these days are about writing CRUD wrappers.

Sorry.

Mostly Type 1 and overflow is a diagnostic log at most. Losing all stale unprocessed data and leaving a ready empty buffer behind is often the desired outcome.

Type 3 is probably banned on most codebases because of the integer overflow.

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

#23

Post by kevin_thibedeau »

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…

powers-of-two are problematic with growable arrays on small heaps. You risk ending up with fragmented space you can't allocate unless you keep growth less than 1.61x, which would necessitate data structures that can deal with arbitrary sizes.

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

#24

Post by tom_ »

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…

A couple of the comments to the article suggest using 64-bit numbers, which is exactly the right solution. 2^64 nanoseconds=584.55 years - overflow is implausible for any realistic use case. Even pathological cases will struggle to induce wraparound at a human timescale.

(People will probably moan at the idea of restarting the process periodically rather than fixing the issue properly, but when the period would be something like 50 years I don't think it's actually a problem.)

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

#25

Post by zephen »

codeworse wrote: post #2

As far as I know, the last approach is the only way to implement efficient lock-free ring-buffer

The middle approach is the only one that is not lock-free.

The first approach is lock-free, but as the author says, it wastes an element.

But here's the thing. If your element is a character, and your buffer size is, say, 256 bytes, and you are using 8-bit unsigned characters for indices, the one wasted byte is less than one percent of your buffer space, and also is compensated for by the simplicity and reduced code size.

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

#26

Post by zephen »

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…

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

That may or may not be part of the actual definition of a ring buffer, but every ring buffer I have written had those goals in mind.

And the first method mentioned in the article fully satisfies this, except for the one missing element mentioned by the author. Which in practice, often is not only not a problem, but simplifies the logic so much that you make up for it in code space.

Or, for example, say you have a 256 character buffer. You really, really want to make sure you don't waste that one character. So you increase the size of your indices. Now they are 16 bits each instead of 8 bits, so you've gained the ability to store 256 bytes by having 260 bytes of data, rather than 255 bytes by having 258 bytes of data.

Obviously, if you have a 64 byte buffer, there is no such tradeoff, and the third example wins (but, whether your are doing the first or third example, you still have to mask the index data off at some point, whether it's on an increment or a read).

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

There's "not possible" and then "not practical."

Sure, you could have a 50 byte buffer, but now, if your indices are ever >= 50, you're subtracting 50 before accessing the array, so this will increase the code space (and execution time).

> The [index size > array size] technique is also widely known in FPGA/hardware circles

Right, but in those hardware circles, power-of-two _definitely_ matters. You allocate exactly one extra bit for your pointers, and you never bother manually masking them or taking a modulo or anything like that -- they simply roll over.

If you really, really need to construct something like a 6 entry FIFO in hardware, then you have techniques available to you that mere mortal programmers could not use efficiently at all. For example, you could construct a drop-through FIFO, where every element traverses every storage slot (with a concomitant increase in minimum latency to 6 clock cycles), or you could construct 4 bit indices that counted 0-1-2-3-4-5-8-9-10-11-12-13-0-1-2 etc.

Most ring buffers, hardware or software, are constructed as powers of two, and most ring buffers either (a) have so much storage that one more element wouldn't make any difference, or (b) have the ability to apply back pressure, so one more element wouldn't make any difference.

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

#27

Post by Neywiny »

ekropotin wrote: post #15

I’m jealous of people, who have to write ring buffers for work. It feels like 90% swe jobs these days are about writing CRUD wrappers.

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.

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

#28

Post by Krssst »

avadodin wrote: post #22
ekropotin wrote: post #15

I’m jealous of people, who have to write ring buffers for work. It feels like 90% swe jobs these days are about writing CRUD wrappers.

Sorry. Mostly Type 1 and overflow is a diagnostic log at most. Losing all stale unprocessed data and leaving a ready empty buffer behind is often the desired outcome. Type 3 is probably banned on most codebases because of the integer overflow.

Unsigned integer arithmetic operations don't overflow but are done modulo 2^n (https://en.cppreference.com/w/c/language/operator_arithmetic...). The author does use unsigned integers so I don't think there is a problem there.

Signed integer overflow is definitely a problem however. Something as simple as incrementing a user-provided int can lead to UB (if the user provides INT_MAX).

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

#29

Post by ekropotin »

Neywiny wrote: post #27
ekropotin wrote: post #15

I’m jealous of people, who have to write ring buffers for work. It feels like 90% swe jobs these days are about writing CRUD wrappers.

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.

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

#30

Post by Neywiny »

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.

I mean idk, I'm living comfortably and as the adage says, not working a day in my life. But if you're at a spot where you need the pay more than you want to write ring buffers, I understand.
Post reply on HN