HN Reader

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

105

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 forever. The technique is also widely known in FPGA/hardware circles, see:

"Simulation and Synthesis Techniques for Asynchronous FIFO Design", Clifford E. Cummings, Sunburst Design, Inc.

https://twins.ee.nctu.edu.tw/courses/ip_core_04/resource_pdf...

12 hours agoby RossBencina

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

2 hours agoby Mikhail_Edoshin

> So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure.

It is, but, IMO, shouldn’t use the code for “a n-element ring buffer, with n set to 1”, similarly to how an array of booleans in many languages shouldn’t be implemented as “an arrayof Foos, with Foo set to bool”.

C++ has std::bitset and std::vector and Java similarly has BitSet and Array because using the generic code for arrays of bits is too wasteful.

Similarly, a one-element ring buffer is either full or it is empty. Why use two indexes to encode a single boolean?

12 hours agoby Someone

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.

11 hours agoby ekropotin

Related. Others?

I've been writing ring buffers wrong all these years - https://news.ycombinator.com/item?id=13175832 - Dec 2016 (167 comments)

13 hours agoby dang

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

2 days agoby codeworse

Every implementation of "the lmax disrupter" I've come across uses this trick.

12 hours agoby kybernetikos