HN Reader

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

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

It's a silly offhand remark at the end of the article, but anybody who is genuinely interested in whether they've been tying their shoes wrong will enjoy Ian's shoelace site: https://www.fieggen.com/shoelace/

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.

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.

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

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

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

Related. Others?

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

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

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

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.

The article author claims that his new version is simpler than the old version.

But the new version is really only simpler TEXTUALLY, because of the post-increment operators:

push(val) { assert(!full()); array[mask(write++)] = val; }

shift() { assert(!empty()); return array[mask(read++)]; }

(If you look at assembly output, it's probably the same or more code.)

But, at least in some languages, those increments might happen before the array access, which could mean that using them causes a race condition.

In fact, in C or C++, those increments are GUARANTEED to happen before the access to array, because they are guaranteed to happen before the calls to mask.

tl;dr -- dude claims to insure he can utilize one more character of his buffer, while writing code that ensures that if he is truly operating at the margins, he will be doing things in the wrong order.

That's how TCP sequence numbers work as well.