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

41–50 of 69 posts

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

#41

Post by Mikhail_Edoshin »

grumbelbart2 wrote: post #40
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 2 capacity (instead of capacity or UINT _MAX).

Which does that and that's what Llang suggests as well, I remember 2 in some power in his formula. I myself find the separate one-bit counter easier to understand: each side counts pages, but they don't need the full number, only the difference between their counters and the difference can be at most one, so one bit is sufficient. If the counters are same, the actors are on the same page, if they are different, then the writer is one page ahead.

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

#42

Post by ale42 »

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…

> using 64-bit numbers, which is exactly the right solution

On a 64-bit platform, sure. When you're working on ring buffers with an 8-bit microcontroller, using 64-bit numbers would be such an overhead that nobody would even think of it.

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

#43

Post by reincarnate0x14 »

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.

I agree with that sentiment in general but even though I've seen systems in continuous operation for 15 years, I've never seen anything make it to 20. I wouldn't write something with the external expectation it never made it that far, but in practical terms, that's probably about as safe as it gets. Even like embedded medical devices expect to get restarted every now and again.

Just as an example the Voyager computers have been restarted and that's been almost 60 years.

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

#48

Post by danhau »

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.

They are efficient FIFOs (queues). You‘ll find them in many places. I know them from multimedia / audio, where you often have unsynchronized readers and writers.

In the audio domain, the reader and weiter are usually allowed to trample over each other. If you‘ve ever gamed on a PC, you might have heard this. When a game freezes, sometimes you hear a short loop of audio playing until the game unfreezes. That‘s a ringbuffer whose writer has stopped, but the async reader is still reading the entire buffer.

Zig‘s “There are too many ring buffer implementations in the standard library“ might also be interesting:

https://github.com/ziglang/zig/issues/19231

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

#49

Post by ErroneousBosh »

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.

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

#50

Post by cuno »

This stuff dates way, way before 2004.

For non-power of two, just checked our own very old circular byte buffer library code and using the notation from this article, it is:

  entriesAllocated() { return ((wrPtr-rdPtr+2*bufSize) % (2*bufSize)); }
  remainingSpace() { return bufSize - entriesAllocated(); }
  isEmpty() { return (entriesAllocated()==0); }
  isFull() { return (entriesAllocated()==bufSize); }
  incWr(int n) { wrPtr = (wrPtr+n) % (2*bufSize); }
  incRd(int n) { rdPtr = (rdPtr+n) % (2*bufSize); }
The 2*bufSize gives you an extra bit (beyond representing bufSize) that lets you disambiguate empty vs full. And if it is a constant power of two (e.g. via C++ template), then you can see how this just compiles into a bitmask instead, like the author's version. You read and write the buffer at (rdPtr%bufSize) and (wrPtr%bufSize) respectively.
Post reply on HN