如何有效地包装固定大小的循环缓冲区的索引

Question

我有一个固定大小的循环缓冲区(实现为数组):初始化时,缓冲区将填充指定的最大元素数,允许使用单个位置索引,以便跟踪我们在圆圈中的当前位置.

访问循环缓冲区中元素的有效方法是什么？这是我目前的解决方案:

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];
}

一些定义:
end_index是紧跟在圆圈中最后一个元素之后的元素的索引(它也被认为与start_index或圆的第一个元素相同).
buffer_size是缓冲区的最大大小.

Answer 1

我想出的最好的是:

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

(假设你需要使用负数)

Answer 2

确保缓冲区始终为2的幂,并掩盖顶部位.

Answer 3

它在某种程度上取决于处理器,但它可能至少值得尝试类似的东西 return (end_index + index) % buffer_size;

Answer 4

我测试了所有3个版本：

// 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);
}

性能结果（滴答声）：

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

因此，似乎模数是更好的选择，因为它不需要对缓冲区的大小进行任何限制。