Try late 1960s. Generally known then, widely used.
For an interesting proof about tokens in ring buffers, check out https://www.cs.utexas.edu/users/EWD/ewd04xx/EWD426.PDF, which, for 1974, has an interesting bit of multiprocessing.
The cost of a mask can probably be entirely buried in the instruction pipeline, so that it's hardly any more expensive than whatever it costs just to move from one register to another.
Modulo requires division. Division requires a hardware algorithm that iterates, consuming multiple cycles (pipeline stall).
That's for "normal" ring buffers. I suspect that the design described in the article can be implemented for non power-of-two without division but I'll need to think about the details.
I don't know if it would end up being faster, though.
The general rule is to only use cmov if your test condition is mostly random.
Ad was pointed out in the thread, recent cpus have reduced the latency of cmov to a cycle. So your result could also depend on your architecture.
if (__builtin_expect(index >= cap,0)) { ...
In which case cmov would be relatively cheap since it isn't blocking execution of other instructions.
This used to be a problem on Pentium4 where cmov had high latency (4 cycles or more), but today, IIRC, a register-to-register cmov is only one cycle, so it is safe to use whenever a branch could have a non-trivial misprediction rate.
If you decrement your array index you don't even need the cmp instruction. The compiler could probably gen so good code.
More recent CPUs, IIRC, do away with the dedicated loop predictor as they have a much more sophisticated general predictor, which, although won't guarantee perfect prediction on this case, it might still get close enough.
movl $-252645135, %edx
movl %edi, %eax
mull %edx
movl %edx, %eax
shrl $4, %eax
movl %eax, %edx
sall $4, %edx
addl %edx, %eax
subl %eax, %ediBTW: read and write pointers, power of two, did that in BeOS (1998) and many sound drivers did it earlier than that. To me, that seemed like the obvious way to do it when I needed it.
- subtracting buffer size from both pointers once the read pointer has wrapped.
- choosing a longer int for the math operation where possible
That seems a small price for the freedom to be able to choose an appropriate buffer size.
You are only encoding 1 bit of data (first or second) so adding more data than that by allowing unsigned integer overflow is just an optimization, not fundamentally necessary.
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.
> 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.
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.
> 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).
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.
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.
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.
Write index of 8 = 1000
Masking those together to create a write position 1000 & 0100 = 0
Doesn't work out correctly, got 0, would expect to get 2. In fact, you could never get a write position of 1, 2, or 3 with an array size of 5.
You are assuming still using &, which is very obviously incorrect with a very obvious fix (%5) which is still wrong because of behavior at overflow.
[EDIT] Resolved internal concerns about size calculations.
Last time I checked, the operation cost was 26k cycles on my PIC.
Using a 2^n + mask made my queue perform 10 times faster (if not more).
IIRC the way we made this really fast was the write the buffer backwards. That way you can detect wrapping around the buffer because DEC will underflow and set the sign flag. Then you can JS to whatever code needs to ADD back the buffer length to handle the wrap around.
But 2^n has another problem (back in that era): buffer size. You are stuck with 1K, 2K, 4K, etc. buffers. When memory is tight you likely need something very specific, so you end up with the solution we had.
But, hey, if memory is free use 2^n bytes for your buffer.
This isn't true for Intel chips since Netburst Pentium 4. The hardware prefetchers can handle predicting iterating through an array forwards, backwards, and even strided accesses [0]. The arrays takes up the same number of cache lines in both cases, so going forwards or backwards are still going to have the same number of cache misses.
0: https://software.intel.com/en-us/articles/optimizing-applica...
; precondition: 0 <= x <= N
; (N is constant)
mov y, 0 ; set up mask
cmp x, N-1 ; set carry flag if x >= N
sbb y, 0 ; subtract 1 from y if carry flag set
and x, y ; set x to zero if x == NCosts were very different in the pipelines (or lack thereof) of eighties/early nineties hardware.
I was doing this in 1992 so it's at least 12 years older than the 2004 implementation. I suspect it was being done long before that. Back then the read and write indexes were being updated by separate processors (even more fun, processors with different endianness) with no locking. The only assumption being made was that updates to the read/write pointers were atomic (in this case 'atomic' meant that the two bytes that made up a word, counters were 16 bits, were written in atomically). Comically, on one piece of hardware this was not the case and I spent many hours inside the old Apollo works outside Boston with an ICE and a bunch of logic analyzers figuring out what the hell was happening on some weird EISA bus add on to some HP workstation.
It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask.
Edit: having had this discussion I've realized that Juho's implementation is different from the 1992 implementation I was using because he doesn't ever reset the read/write indexes. Oops.