8 ms·

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

165 points by karelpeeters 9mo ago

z3t4 9mo ago
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.
- danhau 9mo ago
  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 https://github.com/ziglang/zig/issues/19231
- aldonius 9mo ago
  It's a somewhat different kind of ring buffer, because there's just one index, but I used it in my signal processing class for a finite-impulse-response filter. Choose N to be a power of two >= the length of your filter. Increment index i mod N, write the sample at buffer position x[i], output sum of x[i-k mod N] * a[k] where a[k] are your filter coefficients, repeat with next sample at next time step.
codeworse 9mo ago
As far as I know, the last approach is the only way to implement efficient lock-free ring-buffer
- mrcode007 9mo ago
  There is one more way that is truly lock free. Most lock free implementations relying on atomic compare and swap instructions are not lock free afaik; they have a lock on the cache line in the CPU (in a way you go away from global lock to many distributed locks). There is one more mechanism that allows implementing ring buffers without having to compare head and tail buffers at all (and doesn’t rely on counters or empty/full flags etc) that piggybacks on the cache consistency protocol
  - spockz 9mo ago
    Interesting! Do you know of an example implementation of this?
    - mrcode007 9mo ago
      Yes. [1] has background, [2] has the implementation (fig 2. pseudocode). Since you understood my comment I trust you can figure out the rest :) it’s a very neat trick. [1]https://www.microsoft.com/en-us/research/publication/concurrent-reading-writing/ https://www.microsoft.com/en-us/research/publication/concurr... [2]https://arxiv.org/pdf/1012.1824 https://arxiv.org/pdf/1012.1824
  - dooglius 9mo ago
    That's not how "lock free" is defined/used. If you are considering the MESI M state to be a "lock" then you also have to grant that any write instruction is a "lock".
    - mrcode007 9mo ago
      In fact this a crux of the problem in low latency code and there are ways to combat this. I know there is an academic wait-free and lock-free definition but folks use those often incorrectly as a slogan that something is magically better because it’s „lockfree”. Imagine how _you_ would implement a read-modify-write atomic in the CPU and why E stands for exclusive (sort of like exclusive in a mutex)
  - wat10000 9mo ago
- zephen 9mo ago
  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.
  - fullstop 9mo ago
    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.
    - zephen 9mo ago
      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.
dang 9mo ago
Related. Others? I've been writing ring buffers wrong all these years - https://news.ycombinator.com/item?id=13175832 https://news.ycombinator.com/item?id=13175832 - Dec 2016 (167 comments)
Someone 9mo ago
> 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?
- andrepd 9mo ago
  > C++ has std::bitset and std::vector Notably, this is not the case. C++ std::vector is specialised for bools to pack bits into words, causing an untold array (heh) of headaches. And "wasteful" is doing a lot of lifting here. In terms of memory usage? Yes. In terms of CPU? The other way around.
  - mbel 9mo ago
    > In terms of CPU? The other way around. That depends on your architecture and access pattern. In case of sequential access, packed bools may perform better due to arithmetic being usually way cheaper than memory operations.
- jsnell 9mo ago
  It was for a dynamically growing ring buffer that also did short-object optimization. The natural implementation was to have the capacity and the offsets stored in fixed locations and with a fixed width, and have the variable part be a union of pointer or inline byte buffer. Depending on the element width, you'd have space for different amounts of data in the inline buffer. Sometimes 1, sometimes a few more. Specializing for a one-element inline buffer would be quite complex with limited gains. In retrospect trying to use that as a running gag for the blog post did not work well without actually giving the full context, but the full context would have been a distraction.
- cpgxiii 9mo ago
  > 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. Rather infamously, C++ tried to be clever here and std::vector<bool> is not just a vector-of-bools but instead a totally different vector-ish type that lacks many of the important properties of every other instantiation of std::vector. Yes, a lot of the time you want the space efficiency of a dynamic bitset, rather than wasting an extra 7 bits per element. But also quite often you do want the behavior of a "real" std::vector for true/false values, and then you have to work around it manually (usually via std::vector<uint8_t> or similar) to get the expected behavior.
kybernetikos 9mo ago
Every implementation of "the lmax disrupter" I've come across uses this trick.
RossBencina 9mo ago
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/cummings1_final.pdf https://twins.ee.nctu.edu.tw/courses/ip_core_04/resource_pdf...
- azemetre 9mo ago
  Your link has an invalid cert FYI, but do appreciate the knowledge drop. Rung buffers are some of the cooler data structures out there.
  - RossBencina 9mo ago
    Unfortunately the original source is now behind a sign-in-wall.
- aidenn0 9mo ago
  Non-power-of-two is only really feasible of the total number of inserts will fit in your post/ack counters. Otherwise you have to implement overflow manually which may or may not be possible to do with the available atomic primitives on your architecture. I first encountered this structure at a summer internship at a company making data switches.
- hinkley 9mo ago
  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 for cold cache access.
ekropotin 9mo ago
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.
- RealityVoid 9mo ago
  Jokes on me, when I need them, I don't feel like writing them so I just pick up an old one and tweak it. Or just tell Claude to build me one and it one shots it.
- avadodin 9mo ago
  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.
  - Krssst 9mo ago
    Unsigned integer arithmetic operations don't overflow but are done modulo 2^n (https://en.cppreference.com/w/c/language/operator_arithmetic.html 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).
  - RealityVoid 9mo ago
    Banned is a bit strong, maybe discouraged. MISRA might yell but it's valid technique, IMO, unsigned integer overflow will be fine.
  - zephen 9mo ago
    > 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.
Mikhail_Edoshin 9mo ago
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.)
- grumbelbart2 9mo ago
  One of the comments in the article proposes that: Just wrap both counters at 2capacity (instead of capacity or UINT_MAX).
  - Mikhail_Edoshin 9mo ago
    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.
gpderetta 9mo ago
That's how TCP sequence numbers work as well.
nly 9mo ago
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
- thrtythreeforty 9mo ago
  Not only that, but you can also always form a normal (ptr, size) slice reference to any piece of the ring buffer, even when it wraps. This is really helpful for Eigen arrays that you need to rotate.
atq2119 9mo ago
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/ https://www.fieggen.com/shoelace/
- msm_ 9mo ago
  I thought you're joking, but then I opened https://www.fieggen.com/shoelace/grannyknot.htm https://www.fieggen.com/shoelace/grannyknot.htm
cuno 9mo ago
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.
spacechild1 9mo ago
> 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.
zephen 9mo ago
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.

165 points by karelpeeters 9mo ago

z3t4 9mo ago

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.

danhau 9mo ago
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 https://github.com/ziglang/zig/issues/19231
aldonius 9mo ago
It's a somewhat different kind of ring buffer, because there's just one index, but I used it in my signal processing class for a finite-impulse-response filter. Choose N to be a power of two >= the length of your filter. Increment index i mod N, write the sample at buffer position x[i], output sum of x[i-k mod N] * a[k] where a[k] are your filter coefficients, repeat with next sample at next time step.

codeworse 9mo ago

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

mrcode007 9mo ago
There is one more way that is truly lock free. Most lock free implementations relying on atomic compare and swap instructions are not lock free afaik; they have a lock on the cache line in the CPU (in a way you go away from global lock to many distributed locks). There is one more mechanism that allows implementing ring buffers without having to compare head and tail buffers at all (and doesn’t rely on counters or empty/full flags etc) that piggybacks on the cache consistency protocol
- spockz 9mo ago
  Interesting! Do you know of an example implementation of this?
  - mrcode007 9mo ago
    Yes. [1] has background, [2] has the implementation (fig 2. pseudocode). Since you understood my comment I trust you can figure out the rest :) it’s a very neat trick. [1]https://www.microsoft.com/en-us/research/publication/concurrent-reading-writing/ https://www.microsoft.com/en-us/research/publication/concurr... [2]https://arxiv.org/pdf/1012.1824 https://arxiv.org/pdf/1012.1824
- dooglius 9mo ago
  That's not how "lock free" is defined/used. If you are considering the MESI M state to be a "lock" then you also have to grant that any write instruction is a "lock".
  - mrcode007 9mo ago
    In fact this a crux of the problem in low latency code and there are ways to combat this. I know there is an academic wait-free and lock-free definition but folks use those often incorrectly as a slogan that something is magically better because it’s „lockfree”. Imagine how _you_ would implement a read-modify-write atomic in the CPU and why E stands for exclusive (sort of like exclusive in a mutex)
- wat10000 9mo ago
zephen 9mo ago
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.
- fullstop 9mo ago
  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.
  - zephen 9mo ago
    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.

dang 9mo ago

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

Someone 9mo ago

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

andrepd 9mo ago
> C++ has std::bitset and std::vector Notably, this is not the case. C++ std::vector is specialised for bools to pack bits into words, causing an untold array (heh) of headaches. And "wasteful" is doing a lot of lifting here. In terms of memory usage? Yes. In terms of CPU? The other way around.
- mbel 9mo ago
  > In terms of CPU? The other way around. That depends on your architecture and access pattern. In case of sequential access, packed bools may perform better due to arithmetic being usually way cheaper than memory operations.
jsnell 9mo ago
It was for a dynamically growing ring buffer that also did short-object optimization. The natural implementation was to have the capacity and the offsets stored in fixed locations and with a fixed width, and have the variable part be a union of pointer or inline byte buffer. Depending on the element width, you'd have space for different amounts of data in the inline buffer. Sometimes 1, sometimes a few more. Specializing for a one-element inline buffer would be quite complex with limited gains. In retrospect trying to use that as a running gag for the blog post did not work well without actually giving the full context, but the full context would have been a distraction.
cpgxiii 9mo ago
> 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. Rather infamously, C++ tried to be clever here and std::vector<bool> is not just a vector-of-bools but instead a totally different vector-ish type that lacks many of the important properties of every other instantiation of std::vector. Yes, a lot of the time you want the space efficiency of a dynamic bitset, rather than wasting an extra 7 bits per element. But also quite often you do want the behavior of a "real" std::vector for true/false values, and then you have to work around it manually (usually via std::vector<uint8_t> or similar) to get the expected behavior.

kybernetikos 9mo ago

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

RossBencina 9mo ago

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/cummings1_final.pdf https://twins.ee.nctu.edu.tw/courses/ip_core_04/resource_pdf...

azemetre 9mo ago
Your link has an invalid cert FYI, but do appreciate the knowledge drop. Rung buffers are some of the cooler data structures out there.
- RossBencina 9mo ago
  Unfortunately the original source is now behind a sign-in-wall.
aidenn0 9mo ago
Non-power-of-two is only really feasible of the total number of inserts will fit in your post/ack counters. Otherwise you have to implement overflow manually which may or may not be possible to do with the available atomic primitives on your architecture. I first encountered this structure at a summer internship at a company making data switches.
hinkley 9mo ago
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 for cold cache access.

ekropotin 9mo ago

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.

RealityVoid 9mo ago
Jokes on me, when I need them, I don't feel like writing them so I just pick up an old one and tweak it. Or just tell Claude to build me one and it one shots it.
avadodin 9mo ago
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.
- Krssst 9mo ago
  Unsigned integer arithmetic operations don't overflow but are done modulo 2^n (https://en.cppreference.com/w/c/language/operator_arithmetic.html 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).
- RealityVoid 9mo ago
  Banned is a bit strong, maybe discouraged. MISRA might yell but it's valid technique, IMO, unsigned integer overflow will be fine.
- zephen 9mo ago
  > 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.

Mikhail_Edoshin 9mo ago

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

grumbelbart2 9mo ago
One of the comments in the article proposes that: Just wrap both counters at 2capacity (instead of capacity or UINT_MAX).
- Mikhail_Edoshin 9mo ago
  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.

gpderetta 9mo ago

That's how TCP sequence numbers work as well.

nly 9mo ago

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

thrtythreeforty 9mo ago
Not only that, but you can also always form a normal (ptr, size) slice reference to any piece of the ring buffer, even when it wraps. This is really helpful for Eigen arrays that you need to rotate.

atq2119 9mo ago

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/ https://www.fieggen.com/shoelace/

msm_ 9mo ago
I thought you're joking, but then I opened https://www.fieggen.com/shoelace/grannyknot.htm https://www.fieggen.com/shoelace/grannyknot.htm

cuno 9mo ago

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.

spacechild1 9mo ago

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

zephen 9mo ago

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.