Menu
Why must a ring buffer size be a power of 2?
844
Perhaps the most common version of the circular buffer uses 8-bit bytes as elements. Some implementations of the circular buffer use fixed-length elements that are bigger than 8-bit bytes—16-bit integers for audio buffers, 53-byte ATM cells for telecom buffers, etc.
Advantages and Disadvantages. A ring buffer is an efficient FIFO buffer. It uses a fixed-size array that can be pre-allocated upfront and allows an efficient memory access pattern. All the buffer operations are constant time O(1), including consuming an element, as it doesn't require a shifting of elements.
Solution Answer: Yes. In general, when you change the ring buffer size, the ring closes then allocates more size, and then reopens.
A ring buffer, or circular buffer, is a data structure used to emulate a wrap-around in memory. Ring buffers are contiguous blocks of memory that act as if they are circular, with no beginning or end, instead of 1D.
It must be a power of 2 to use the approach detailed below. It need not be otherwise.
A common approach looks like "if (index >= size) { index = size - index; }" (size of 10, index 10, resulting index is 0). This is slower and prone to error relative to the following approach.
Using a power of two allows us to take advantage of the following:
size = 32
bin(size) => '00100000'
mask = size - 1;
bin(mask) => '00011111'
Applying this mask with a bitwise and, we can isolate only the bits that comprise numbers in the range of 0 - 31 as the index grows:
index = 4
bin(4 & mask) => '00000100' (4)
# index 32 wraps. note here that we do no bounds checking,
# no manipulation of the index is necessary. we can simply
# and safely use the result.
index = 32
bin(index & mask) => '00000000' (0)
index = 33
bin(index & mask) => '00000001' (1)
index = 64
bin(index & mask) => '00000000' (0)
index = 65
bin(index & mask) => '00000001' (1)
This approach requires no comparisons, no branches, and is safe (resulting index always within bounds). It has the added benefit of not trashing information; while index 65 addresses element 1, I still retain the information that the index is logically 65 (which proves quite useful).
I'd also like to add that this is just as efficient when the index grows to 3456237 (address 13 in the buffer) as when it's 3.
I know I'm late to the party, I'm not even sure how I found this question :-) Hope this helps.
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
