2 ms·
Normally I use monotonically increasing indices to avoid the 1 element issue as there is no wraparound, then use masking to map them to actual buffer positions.
by gpderetta 3y ago
Normally I use monotonically increasing indices to avoid the 1 element issue as there is no wraparound, then use masking to map them to actual buffer positions. With non-power of two sizes it becomes a more expensive operation, so you have to wrap on increment instead.
- adrian_b 3y agoWhile this should be better, it now needs a check for overflow in the indices, unless they are 64-bit numbers, when you may hope for a computer reboot long before overflow. Overflow in 32-bit indices can be surprisingly frequent in fast computers.
- gpderetta 3y agoWell, yes, you use 64 bit indices. As you are padding your indices to cacheline size anyway, you have bits to spare. You can also still use 32bit indices and let them wrap around naturally and make it work as long as your queue size is less than 2*31. Comparison just becomes a little bit trickier. That's how TCP works for example.
- Joker_vD 3y agoAs a matter of fact, integer overflow does not matter in this case. The head and tail indices of a full buffer would still be equal, and those of an empty buffer would still differ by exactly its size: so all you need to do is use a wide enough integer for the buffer's size to fit inside it.