如何高效地封装固定大小的循环缓冲区的索引？

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 是缓冲区的最大大小。

- Kiril

---

@Fred，当你向循环缓冲区添加元素时...每次超过buffer_size时，索引都会回绕。 - Kiril

@Fred，循环缓冲区的要点是新数据会覆盖旧数据，并且你需要跟踪圆圈中的位置。它使用一个数组来模拟一个圆圈，因此end_index告诉我们最后一个元素的位置（或者是最后一个元素之后的位置）。缓冲区大小可能是100，但我们只有13个元素，因此end_index是14。如果我已经有了100个元素，end_index就是99，如果再添加一个元素，end_index将回到0。我的工作方式类似于队列，但我可以以O(1)的时间访问每个元素。 - Kiril

@Fred，缓冲区始终已经填满：一开始就填充，然后稍后可以添加更多项（我也这样做）。我在一开始就填充它，这样我就不需要为环形的起始和结束保留单独的索引。如果我不立即填充它，那么我将拥有一个部分填充的圆形，并且我将需要两个索引来迭代它。所有这些情况都在循环缓冲区的维基页面中显示。 - Kiril

@Fred end_index 是我词汇贫乏的结果。我不想称它为 start_end_index（感觉有些奇怪），也想不到一个好的描述方式，但它确实充当了起始和结束索引的作用。如果缓冲区始终是满的（我的实现保证了这一点），那么起始和结束索引始终相同，因此无需保留两个单独的变量。 - Kiril

@Fred：你是建议在圆形缓冲区中使用“标记”或“令牌”项目吗？这可能是个好主意，但我如何获取圆形缓冲区中的第 n 个项目（即我不需要一个指向起始位置的引用吗）？当我向缓冲区添加另一个项目时，我要移动起始位置吗？ - Kiril

Answer 1

我想到的最好的方法是：

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

假设你需要使用负数进行操作。

- mpen

---

这对我来说不太明显，因此在此稍作澄清： a 是需要包装的索引，而 n 是数组大小。 - GER

我在使用这样的代码时刚刚被一个bug咬了一口。问题是，如果索引接近int的大小，它可能会溢出并返回负数。例如：((872415600 % 1275068416) + 1275068416) % 1275068416) 等于 -872414864。 - user545424

Answer 2

请确保缓冲区的长度始终是2的幂，并屏蔽掉高位。

- Peter Taylor

---

一个过早优化的模运算。 - user395760

@delnan 我不知道所谓的“过早”。虽然我个人会使用模数，但为此将数组设置为二的幂次方实际上是非常普遍的做法。 - corsiKa

@Jonathan，他现在正在做的是过早优化取模。我只是在建议逻辑上的极端情况。 :P - Peter Taylor

我测试了取模版本和最高位掩码版本，它们都是相等的。看起来取模更加健壮，因为它不需要buffer_size是2的幂。 - Kiril

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

性能结果（tick）：

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

所以看起来模数是更好的选择，因为它不需要对缓冲区大小进行任何限制。

- Kiril

---

这很有帮助，我想知道与三元运算符( endIndex = 0 ? maxSize: endIndex ) - 1;相比，针对负数/递减的双模解决方案（https://dev59.com/ElPTa4cB1Zd3GeqPnu-h#10184756）的性能如何。 - WilliamKF

取模运算效率低下，因为它实际上是除法。大多数处理器（至少是微控制器和高端DSP）没有除法操作，因此必须使用一系列的加法、移位和比较来实现。即使处理器有除法指令，通常也是通过微码实现的，比掩码要慢几十倍。如果maxSize是2的幂，则编译器可以将取模优化为掩码，但不能依赖于此。 - PauliL

@WilliamKF：三目运算符只是if...else语句的一种晦涩写法。它并不更高效，但它更难阅读。通常情况下，你应该避免使用它。 - PauliL

Answer 4

这将有些取决于处理器，但尝试使用类似 return (end_index + index) % buffer_size; 的方法可能至少值得一试。

- Jerry Coffin

---

(1) 如果end_index不等于buffer_size（假设数组是从0开始索引的），是否成立？ (2) 考虑到这一点，让我们简化为return (a + n) % n; -- 然后如果a = -5，n = 4，那么(a+n)得到的结果是-1，仍然超出了边界（即，对于a < -n情况下失败）。 - mpen

@Mark：虽然原始代码暗示了负数的可能性，但通常根本不允许这种情况发生（尽管最好使用无符号类型来确保防止出现这种情况）。 - Jerry Coffin

哦...我想我的情况有所不同。我经常使用-1来表示最后一个元素。 - mpen

@Mark：在这种情况下，你需要稍微不同地限制一下值，例如：int clamp(int val, int max) { while (val < 0) val += max; while (val >= max) val -= max; return val; } - Jerry Coffin

我以前用while循环的方式做过（这个问题），但是直接进行两次模运算会更高效，不是吗？ - mpen

@Mark：如果你的值可能会严重超出范围，那么取余运算可能会更快。如果你只想处理类似于-max..max2（左右）的东西，那么while循环可能*更快（在大多数处理器上，取余运算并不特别快）。 - Jerry Coffin

Answer 5

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

请查看模运算以获取有关模运算符 (%)的更多信息。

- Judge Maygarden

---

太简单了！不错。 - tisaksen

Answer 6

顺便说一下，你总是可以使用并行数组：i = next[i];

但是，实际上，我总是这样做：i++; if (i >= n) i = 0; 或者 i = (i+1) % n;

无论如何，如果这真的是一个重要的性能问题，我会感到非常惊讶。

- Mike Dunlavey