8 ms·
This is of course not a new invention. The earliest instance I could find with a bit of searching was from 2004, with Andrew Morton mentioning in it a code revi
by jgrahamc 10y ago
This is of course not a new invention. The earliest instance I could find with a bit of searching was from 2004, with Andrew Morton mentioning in it a code review so casually that it seems to have been a well established trick. But the vast majority of implementations I looked at do not do this.
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.
- kitsuac 10y agoIt's odd that you were using ring buffers in 1992 for low level code but don't understand the value of avoiding a modulus instruction. Masking is far more efficient and often a ring buffer will be used in code where performance is absolutely critical.
- jgrahamc 10y agoYou wouldn't use the modulus operation. You aren't adding some arbitrary number that's going to make you increase either index by more than the buffer length so you know that at worse you are going to need to subtract the length of the buffer. 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.
- deleted 10y ago[deleted]
- kitsuac 10y agoYou are still introducing a conditional by detecting the need to subtract, and iterating backward through memory is horrific for cache performance. If you need a specific, non power-of-2 sized buffer, then of course you make that design decision and pay the performance penalty. But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer.
- jgrahamc 10y agoThe 286/386 didn't have a cache so that wasn't a worry at that time.
- coldtea 10y ago>But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer. Costs were very different in the pipelines (or lack thereof) of eighties/early nineties hardware.
- to3m 10y agoHave you tested this recently? I haven't for some years now but performance was identical regardless of direction. Maybe I need to try it again. I'd expect going backwards to be no worse than "not as good" - like say perhaps the prefetching mechanism doesn't cater for this case - but maybe my standards aren't high enough and this is enough to tip things over into the horrific.
- tbirdz 10y ago>iterating backward through memory is horrific for cache performance 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-application-performance-on-intel-coret-microarchitecture-using-hardware-implemented-prefetchers/ https://software.intel.com/en-us/articles/optimizing-applica...
- fla 10y agoDepending on the machine, a modulo can cost _alot_ . 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).
- jstimpfle 10y agoDon't use a modulo then. Use subtraction.
- dllthomas 10y agoSubtraction requires a branch, which could be worse (or not) depending on architecture.
- pklausler 10y agoOh, come on, you don't need a branch to do a conditional subtraction. Reify the condition to 0/1 and use multiplication, or use AND with a two's complement of the condition.
- dllthomas 10y agoGood point!
- avocad 10y agoThanks! This AND trick is great. Actually makes me want to go back to assembly-level programming.
- cksk 10y agoOK, my bit twiddling knowledge is weak, my google skills are weaker still, and now I'm curious: what does "AND with a two's complement of the condition" mean, exactly?
- pklausler 10y agox -= N & -(x >= N);
- jsnell 10y agoIt's not just an optimization, it's necessary for correct operation. With a non-power of two buffer the integer wraparound causes a discontinuity.
- jgrahamc 10y agoNo, it's an optimization.
- brianon99 10y agoThis is not only an optimisation. Power of 2 is necessary to avoid discontinuity. See the comments below the article for explanation.
- dllthomas 10y agoNo, 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 10y agoI never claimed you should use a modulus operation.
- dllthomas 10y agoYou 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.
- 10y ago
- kazinator 10y ago> It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask. 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).
- ambrop7 10y agoYou do not need modulo or division to implement non-power-of-2 ring buffers. Because you will only increment by one. So instead of "x = x % BufferSize" you can do "if (x >= BufferSize) x -= BufferSize;" or similar. 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.
- deleted 10y ago[deleted]
- tbirdz 10y agoYou could also do a predicated conditional move instead. Just do the subtraction every time, and use something like cmov to only do the write if you need to. I don't know if it would end up being faster, though.
- jnordwick 10y agoMost likely (very very likely) the branch would be faster. It will almost always be predicted correctly (exceptions on the rollover) and cmov can be moderately expensive. The general rule is to only use cmov if your test condition is mostly random.
- smallnamespace 10y agoCan't the CPU just continue execute out-of-order while waiting on the cmov data dependency to finish though? In which case cmov would be relatively cheap since it isn't blocking execution of other instructions.
- wglb 10y agoI was doing this in 1992 so it's at least 12 years older than the 2004 implementation 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 https://www.cs.utexas.edu/users/EWD/ewd04xx/EWD426.PDF, which, for 1974, has an interesting bit of multiprocessing.
- pklausler 10y agoFor what it's worth, Seymour Cray's Control Data 6600 implemented ring buffers for I/O channels correctly in hardware using gumdrop-sized single transistors in 1963. This is not exactly a new technology.
- NotThe1Pct 10y agoMe too, back in 2005 we were already doing all this. Also there is an easy hack that solves the overflow part.