I've been writing ring buffers wrong all these years (2016)
3 days ago
- #data-structures
- #optimization
- #ring-buffer
- Implementing a one-element ring buffer is challenging due to wasted space in traditional implementations.
- Two common ring buffer implementations: array with two indices (read/write) and array with one index plus length.
- Traditional two-index implementation wastes one array element to distinguish between empty and full states.
- Alternative one-index-plus-length implementation uses full array capacity but complicates concurrent access.
- Proposed solution: use two unmasked indices that grow unbounded, only masking when indexing the array.
- Benefits of unmasked indices: simpler code, no wasted space, but requires power-of-two capacities and unsigned integer wraparound.
- Early mentions of this technique date back to 2004, yet it remains underused.
- Possible reasons for underuse: tradition, aversion to integer overflow, or non-power-of-two buffer needs.
- Non-power-of-two capacities can be supported with modulo operations, at a performance cost.