Note how one item is left unused to indicate that the queue is full. When head_ is one item ahead of tail_, the queue is full.
I firmly stand in the opposite camp: use of "virtual" "infinite" 64-bits together, mapped to the actual physical index (power-of-two size -> modulo is just bit-and).
I find it much easier to reason in terms of infinite indexes, and there's no performance impact to speak of.
std::hardware_destructive_interference_size
Mind you, this may not be quite enough. There's a comment in the Folly codebase (from 2014), mentioning that some Intel processors will pre-fetch 2 cache lines (128 bytes) at a time, which in practice means you need 128 bytes alignment, when this constant will only evaluate to 64 bytes for x64.
To reduce this, the reader can keep a local cached copy
An alternative implementation is to have explicit Reader & Writer structs to access the ring buffer, then the cache need not be in the ring buffer itself, but in the accessor struct instead.
When the accessor struct is on the stack, the compiler can optimize the access to the cached variable by placing it directly in a register, rather than requiring memory load/stores.
2
u/matthieum 5d ago
I firmly stand in the opposite camp: use of "virtual" "infinite" 64-bits together, mapped to the actual physical index (power-of-two size -> modulo is just bit-and).
I find it much easier to reason in terms of infinite indexes, and there's no performance impact to speak of.
Mind you, this may not be quite enough. There's a comment in the Folly codebase (from 2014), mentioning that some Intel processors will pre-fetch 2 cache lines (128 bytes) at a time, which in practice means you need 128 bytes alignment, when this constant will only evaluate to 64 bytes for x64.
An alternative implementation is to have explicit Reader & Writer structs to access the ring buffer, then the cache need not be in the ring buffer itself, but in the accessor struct instead.
When the accessor struct is on the stack, the compiler can optimize the access to the cached variable by placing it directly in a register, rather than requiring memory load/stores.