How to efficiently wrap the index of a fixed-size circular buffer

15.6k views Asked by At

I have a fixed size circular buffer (implemented as an array): upon initialization, the buffer gets filled with the specified maximum number of elements which allows the use of a single position index in order to keep track of our current position in the circle.

What is an efficient way to access an element in the circular buffer? Here is my current solution:

int GetElement(int index)
{
    if (index >= buffer_size || index < 0)
    {
        // some code to handle the case
    }
    else
    {
        // wrap the index
        index = end_index + index >= buffer_size ? (index + end_index) - buffer_size : end_index + index;
    }

    return buffer[index];
}

Some definitions:
end_index is the index of the element immediately after the last element in the circle (it would also be considered the same as the start_index, or the first element of the circle).
buffer_size is the maximum size of the buffer.

6

There are 6 answers

2
mpen On BEST ANSWER

Best I've come up with is:

public static int Wrap(int index, int n)
{
    return ((index % n) + n) % n;
}

(Assuming you need to work with negative numbers)

3
Kiril On

I tested all 3 versions:

// plain wrap
public static int WrapIndex(int index, int endIndex, int maxSize)
{
    return (endIndex + index) > maxSize ? (endIndex + index) - maxSize : endIndex + index;
}

// wrap using mod
public static int WrapIndexMod(int index, int endIndex, int maxSize)
{
    return (endIndex + index) % maxSize;
}

// wrap by masking out the top bits
public static int WrapIndexMask(int index, int endIndex, int maxSize)
{
    return (endIndex + index) & (maxSize - 1);
}

The performance results (ticks):

Plain: 25 Mod: 16 Mask: 16 (maxSize = 512)
Plain: 25 Mod: 17 Mask: 17 (maxSize = 1024)
Plain: 25 Mod: 17 Mask: 17 (maxSize = 4096)

So it seems that the modulus is the better choice, because it does not require any restriction on the size of the buffer.

0
Mike Dunlavey On

FWIW, you could always do a parallel array: i = next[i];

But, really, I've always just done this: i++; if (i >= n) i = 0; OR i = (i+1) % n;

Regardless, I'd be really surprised if this is ever a significant performance issue.

1
Judge Maygarden On
int GetElement(int index)
{
    return buffer[(end_index + index) % buffer_size];
}

See modulo operation for the more information on the modulus operator (%).

4
Peter Taylor On

Ensure that the buffer is always a power of two long and mask out the top bits.

6
Jerry Coffin On

It'll depend somewhat on the processor, but it's probably at least worth trying something like return (end_index + index) % buffer_size;