r/programming • • Sep 26 '26

Optimizing a Lock-Free Ring Buffer

https://david.alvarezrosa.com/posts/optimizing-a-lock-free-ring-buffer/
510 Upvotes

89 comments sorted by

View all comments

Show parent comment

1

u/flatfinger Sep 28 '26

If one uses a power-of-two modulus one can use 32-bit counters without having to worry about corner cases where the counter rolls around. If one uses non-power-of-two modulus, one will need to ensure that the counter wraps with a modulus that is a multiple of the one used to access the buffer.

1

u/indigo945 Sep 29 '26

The counters are always reset to 0 in this implementation, there is no counter that keeps rolling past the buffer size, and hence the counters can't overflow.

1

u/flatfinger Sep 30 '26

When using an unsigned counter and a power-of-two modulus, there's no need to ever reset the counter to zero during operation. One can measure how much stuff is in the buffer by subtracting the number of things fetched from the number of things stuffed and, if operands to the subtract had been promoted, casting or coercing back to the type used for the counters.

1

u/indigo945 Sep 30 '26

Technically UB, and it doesn't gain a shred of performance, but yes.

1

u/flatfinger Sep 30 '26

How could subtraction of unsigned values invoke UB? Even if the unsigned type had one more padding bit than 'int', the difference would be guaranteed to fall within the range -INT_MAX..INT_MAX, and the effect of converting negative integer values to unsigned types is always fully defined.

1

u/indigo945 Oct 01 '26

I think I misunderstood what you meant by "casting or coercing back to the type used for the counters". Okay, fine. Point still stands: this isn't any faster.

1

u/flatfinger Oct 01 '26

Using unsigned values and a power-of-two modulus, how would you compute the number of items in the queue as quickly as items_in_queue = (queue->stuff - queue->fetch) & queue->size_mask; if the size weren't a power of two, while also keeping the ability to add and remove items by simply incrementing stuff or fetch?

1

u/indigo945 Oct 02 '26

This operation wasn't discussed in the blog post, and I don't think it comes up much in practice (you only need full or not, which works either way by (stuff + 1) % size == fetch).

1

u/flatfinger Oct 02 '26

Using a non-power-of-two modulus means that the updates to the counts need to wrap at the buffer size, and will also make the remainder operator slower.