3 ms·
The ExpandingRingBuffer.h is rather bad for a representation of a ring buffer - it uses modulo for the index calculation, which is pretty damn bad and should re
by dzaima 2y ago
The ExpandingRingBuffer.h is rather bad for a representation of a ring buffer - it uses modulo for the index calculation, which is pretty damn bad and should really at the very least be masking by a power-of-two.
(it might very-slightly-but-not-really be excusable if the reason was memory utilization.. ..but the resize does "size_t new_capacity = capacity * 2;" so it does doubling anyway. Also, see reply noting that you don't even need power-of-two sizes for fast wrapping, which I managed to completely forget about)
- kragen 2y agoMost ring buffers that aren't powers of 2 in size can still get by with i == max ? 0 : i+1 and i ? i-1 : max. On most hardware these will be almost as fast as just i+1 and i-1, while division will be much slower, even on recent hardware.
- dzaima 2y ago..yep, true, completely slipped my mind. So modulo is just trivially always the bad choice. Even for arbitrary indexing "tmp=head+index; buffer[(tmp >= capacity) ? tmp - capacity : tmp]" or so is gonna be better. (assuming the compiler compiles it to something branchless. Or, probably even if it doesn't - division might end up slower than the worst-case of 50% misprediction! And for sequential indexing it's even gonna be predictable.)