CODEWITHSUNDEEP
c#javac++optimizationcircular-buffer
Kiril
Kiril

Reputation: 40395

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

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.

Upvotes: 8

Views: 16909

Answers (6)

mpen
mpen

Reputation: 283243

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)

Upvotes: 20

Kiril
Kiril

Reputation: 40395

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.

Upvotes: 8

Mike Dunlavey
Mike Dunlavey

Reputation: 40689

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.

Upvotes: 0

Judge Maygarden
Judge Maygarden

Reputation: 27603

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

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

Upvotes: 5

Jerry Coffin
Jerry Coffin

Reputation: 490583

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

Upvotes: 6

Peter Taylor
Peter Taylor

Reputation: 5076

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

Upvotes: 11

Related Questions