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

31–40 of 69 posts

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

#31

Post by loeg »

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…

Fwiw in this application you would never need to divide by an arbitrary integer each time; you'd pick it once and then plumb it into libdivide and get something significantly cheaper than 8-30 cycles.

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

#32

Post by RealityVoid »

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.

Banned is a bit strong, maybe discouraged. MISRA might yell but it's valid technique, IMO, unsigned integer overflow will be fine.

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

#33

Post by fullstop »

zephen wrote: post #25
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…

I've used the "Waste an element" one for ages on microcontrollers where I don't want to deal with the overhead in an ISR.

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

#34

Post by nathan_douglas »

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.

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.

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

#35

Post by thaumasiotes »

tom_ wrote: post #24
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 so…

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

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

#36

Post by tom_ »

thaumasiotes wrote: post #35
tom_ wrote: post #24

Earlier quoted context omitted.

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 so…

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

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

#37

Post by zephen »

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.

> Losing all stale unprocessed data and leaving a ready empty buffer behind is often the desired outcome.

Yeah, the Type 3 example could conceivably make it so that you intermix old and new data if you overflow, rather than just dumping a whole buffer.

Especially when your full() function checks for exact equality, like the one in the article does.

And if you remove the asserts, and then somehow underflow? God help you. You'll be pulling 4 billion entries you never actually stored out of the buffer, just repeating previously stored garbage over and over.

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

Not only this, but the purported code reduction benefits associated with type 3 are only superficial, and won't actually appear in any assembly listing.

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

#38

Post by zephen »

fullstop wrote: post #33
zephen wrote: post #25

Earlier quoted context omitted.

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…

I've used the "Waste an element" one for ages on microcontrollers where I don't want to deal with the overhead in an ISR.

Agreed.

The article author claims that the "don't waste an element" code is also more efficient, but that claim seems to be based on a hard-on about the post-increment operator, rather than any kind of dive into the cyclometric complexity, or even, y'know, just looking at the assembler output from the compiler.

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

#39

Post by Mikhail_Edoshin »

Technically each side needs an index plus a single bit. The bit is a counter, you increment it on every wrap. It overflows, but this is correct, we only need the last bit. Initially it is 0. By comparing the indexes and the bit you tell apart all cases and do not lose an entry.

(I think this was published in one of Llang's papers but in a rather obscure language.)

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

#40

Post by grumbelbart2 »

Mikhail_Edoshin wrote: post #39

Technically each side needs an index plus a single bit. The bit is a counter, you increment it on every wrap. It overflows, but this is correct, we only need the last bit. Initially it is 0. By comparing the indexes and the bit you tell apart all cases and do not lose an entry. (I think this was published in one of Llang's papers but in a rather obscure language.)

One of the comments in the article proposes that: Just wrap both counters at 2capacity (instead of capacity or UINT_MAX).
Post reply on HN