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

Question

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.

Solution 1

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)

Solution 2

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

Solution 3

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.

Solution 4

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

Solution 5

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

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

View more solutions

Comments

[Admin]

@Johnatan: A prematurely optimized modulo operation, yes.

[corsiKa]

@delnan I don't know about prematurely. While personally I'd use modulo, it's actually very common practice to have arrays be powers of two for this reason.

[Peter Taylor]

@Jonathan, what he's doing at the moment is already prematurely optimised modulo. I'm just suggesting the logical extreme. :P

[Kiril]

I tested the modulus version vs the top-bit-mask and they're both equal. It seems that the modulus is more robust since it doesn't require the buffer_size to be a power of 2.

[mpen]

(1) Is end_index not equal to buffer_size (assuming a 0-indexed array)? (2) With that in mind, let's simplify this to return (a + n) % n; -- then if a = -5, and n = 4, then (a+n) yields -1, which is still out of bounds. (i.e., it fails for a < -n).

[Jerry Coffin]

@Mark: although the original code implies the possibility of negative numbers, that's normally just not allowed at all (though it's probably better to use an unsigned type to ensure against it).

[mpen]

Oh... I guess my situation is different. I often use -1 to mean the last element.

[Jerry Coffin]

@Mark: in that case, you'd just about have to clamp the value a bit differently, something like: ` int clamp(int val, int max) { while (val < 0) val += max; while (val >= max) val -= max; return val; }`

[mpen]

I've done it that way in the past (with a while loop), but it'd be more efficient to just mod it twice, no?

[Jerry Coffin]

@Mark: if your value might be drastically out of bounds, then a remainder is likely to be faster. If you just want to handle something like -max..max*2 (or so), then the while loops are probably faster (taking a remainder isn't particularly fast on most processors).

[GER]

It wasn't obvious to me so here is a slight clarification: a is the index that needs wrapped and n is the array size.

[user545424]

I just got bitten by a bug when using code like this. The problem is that if index is close to the size of the int, this can overflow and return a negative number. For example: ((872415600 % 1275068416) + 1275068416) % 1275068416) is equal to -872414864.

[tisaksen]

So simple! Good one.

[WilliamKF]

This was helpful, I'm wondering how the double mod solution that works with negative numbers / decrementing (stackoverflow.com/a/10184756/115751) performs versus a ternary like ( endIndex = 0 ? maxSize: endIndex ) - 1;

[PauliL]

Modulo operation is inefficient because it is actually division. Most processors (at least microcontrollers and high-end DSPs) do not have division operation, so it has to be implemented with series of additions, shifts and comparisons. Even if the processor has division instruction, it is usually implemented with microcode and takes dozens of times longer than masking. Compiler may optimize modulo into masking if maxSize is power of two, but you can not rely on that.

[PauliL]

@WilliamKF: Ternary operation is just a cryptic way to write if...else clause. It is not more efficient but it is more difficult to read. Generally, you should avoid using it.