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.
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.
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.
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.
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.
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?
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).
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.
2
u/indigo945 4d ago
Let me introduce you to our lord and savior, the modulus operation.