I've been writing ring buffers wrong all these years

Re:I've been writing ring buffers wrong all these years by simcop2387 on Wednesday December 14, 2016 @01:37PM (#13178441)

That said, one of the comments on the blog actually had a great suggestion for dealing with this. Wrap the value yourself at 2*capacity, you'll still get the same benefits from the algorithm and it's trivial to prevent the overflow then. You can then avoid the modulo operation (subtract the capacity if it's a larger index) and get better performing non-power of 2 capacities.

That said I'd mostly be using this kind of thing in a situation where i'd want to have a power of two sized buffer anyway.

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by dllthomas on Wednesday December 14, 2016 @02:56PM (#13179133)

Yeah, that's a great option!

Conceptually it's roughly what's going on anyway - something must wrap at some point if we're going to store our offsets in limited space - just that we get the wrapping for free from overflow if it's 2^n.

The confusion above stemmed, I think, from the fact that in the "original" implementation the mask is used for that wrapping and then we have a noop projection from offset to index. In this implementation, overflow is used for that wrapping and the mask is to project from offset to index. In the implementation you discuss, we pick still other functions for both.

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by emn13 on Thursday December 15, 2016 @04:35AM (#13183459)

fastest would likely be to wrap at the greatest multiple of N that fits in your integer representation, since that (probably dramatically) reduces branch mispredicts.

However, you're still doing lots of modulos to then find the "real" array index from the "virtual" one, so this is still likely not a great option compared to the power-of-two buffers.

It might actually be faster (at least for mildly large buffers) to use 2 ifs and a range that's twice the capacity. One ifs checks whether your virtual index needs to subtract the capacity to become real, and another checks whether it's time to substract 2 times the capacity.

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by dllthomas on Thursday December 15, 2016 @06:35PM (#13189746)

With the conditional subtraction recommended elsewhere, you can do 2*N with no branch mispredictions and no modulo. Whether that's actually faster should be tested, if you're in an environment where you care about such things.

[ Parent | on HN ]