3 ms·

> I chose to allow any queue size as opposed to allowing only sizes that are a power-of-two. This means that at least one queue item is unused in order to disam

> I chose to allow any queue size as opposed to allowing only sizes that are a power-of-two. This means that at least one queue item is unused in order to disambiguate between the empty queue and full queue state. Don't you still need an unused queue item even with a power of two size? Isn't the point of having a power of two size that you can calculate the next item index in the buffer using binary rollover to go back to 0 as opposed to requiring a comparison and a branch.

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 ago
  While 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 ago
    Well, 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 ago
    As 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.
JonChesterfield 3y ago
You can distinguish full and empty using x-y=0 vs x-y=N if the length N is a power of two and smaller than the integer type holding indices x, y. No unused element needed then.
- adwn 3y ago
  > You can distinguish full and empty using x-y=0 vs x-y=N if the length N is a power of two Why wouldn't this work for, e.g., N=13?
  - simias 3y ago
    The trick with powers of two is that you can just look at the MSB of `x XOR y` where x and y have one more bit than necessary to store the size. So for instance if you have a buffer with 8 entries you have a read pointer and a write pointer, both wrapping at 16 (4bits). When you address the buffer you ignore the MSB, when you want to test for empty you do `read == write`, when you want to test for full you do `read XOR write == 0b1000`. So you only have extremely cheap comparisons, bitwise XOR and counter increments to implement all operations.
crest 3y ago
If it's a power of two you can use a longer than required index. An empty buffer will have all index bits equal. A full buffer will have the higher bits different but the lower bits equal. This requires extracting only the lower bits from the index before using it, but depending on the instruction set and bit position this is either very cheap or completely free.

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 ago
While 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 ago
  Well, 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 ago
  As 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.

JonChesterfield 3y ago

You can distinguish full and empty using x-y=0 vs x-y=N if the length N is a power of two and smaller than the integer type holding indices x, y. No unused element needed then.

adwn 3y ago
> You can distinguish full and empty using x-y=0 vs x-y=N if the length N is a power of two Why wouldn't this work for, e.g., N=13?
- simias 3y ago
  The trick with powers of two is that you can just look at the MSB of `x XOR y` where x and y have one more bit than necessary to store the size. So for instance if you have a buffer with 8 entries you have a read pointer and a write pointer, both wrapping at 16 (4bits). When you address the buffer you ignore the MSB, when you want to test for empty you do `read == write`, when you want to test for full you do `read XOR write == 0b1000`. So you only have extremely cheap comparisons, bitwise XOR and counter increments to implement all operations.

crest 3y ago

If it's a power of two you can use a longer than required index. An empty buffer will have all index bits equal. A full buffer will have the higher bits different but the lower bits equal. This requires extracting only the lower bits from the index before using it, but depending on the instruction set and bit position this is either very cheap or completely free.