[dllthomas]

No, it's not. A non-power-of-two will lead to incorrect behavior, implementing the data structure the way the author describes, for precisely the reason given by your parent comment. There are other implementations that don't suffer from this (described in the comments there), but it's not simply a matter of replacing bitwise-and with a more generic computation of the modulus.

Imagine we had four bit integers and a three cell array. Stepping from 7 (= 1 mod 3) to 8 (= 2 mod 3) winds up stepping instead to 0 (= 0 mod 3) because overflow, which would reuse cells inappropriately.

[jgrahamc]

I never claimed you should use a modulus operation.

[dllthomas]

You said,

> It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask.

In fact it is required for correctness to use the approach he specified with any choice of masking operation.

[jgrahamc]

Any choice?

He only ever calls mask() after an increment. There are other ways of detecting the overflow and wrap to 0 that don't involve modulus.

[dllthomas]

Yes, any choice. Yes, that's not the case if you change the implementation in other ways in tandem - but then you are describing a different implementation. To mask where he does, any choice of mask will exhibit this problem (or other problems), mathematically. I can produce a proof if you need it.

> He only ever calls mask() after an increment.

I think you misunderstand what he's talking about. He calls mask at insert and lookup and he does not store the masked value - which leaves the implementation vulnerable to overflow (which is not a problem iff the array is 2^n big).

[simcop2387]

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.

[dllthomas]

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.

[emn13]

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.

[jgrahamc]

A ha! That is the point I was missing. Thanks.