uint_MAX 环绕：我可以相信它用于环形缓冲区头部和尾部吗？

Question

我有一个环形缓冲区，它将头索引和尾索引存储为无符号整数值。根据 this 源，仅在索引检索时换行就足够了，并且让 uint 行为负责 uint_MAX 处的换行。对于所有实现都是如此吗？还是我依赖于这里未定义的行为？

演示

#include <iostream>
#include <cstddef>
#include <limits>

int main()
{
    size_t max = std::numeric_limits<size_t>::max();
    size_t head = max - 5;
    size_t tail = max + 5;
    size_t len = tail - head;
    std::cout << len << std::endl;
    head = max - 5;
    tail = head + 10;
    len = tail - head;
    std::cout << len << std::endl;
    head += 20;
    tail += 20;
    len = tail - head;
    std::cout << len << std::endl;
}

输出：

10
10
10

Answer 1

无符号算术

无符号整数类型的算术运算由 从最大可表示值“环绕”的语言标准 值返回到 0。 引用 基础.基础p2：

无符号类型的算术运算以 2^N 为模。

（其中 N 是表示中的位数）。

因此，示例代码中显示的行为，其中

size_t

数量增加超过最大值，并在以下情况下减去： 一个接近最大值，另一个接近零，都是明确定义的， 显示的输出是便携式的。

使用无界无符号数量作为数组索引

问题询问是否“足以仅在检索时换行” 指数”。据我了解，这个想法是做类似的事情：

typedef int /*or whatever type*/ DataValue;
DataValue ringBuffer[BUFFER_SIZE];
size_t head;
size_t tail;

// Add an element to the ring buffer.
void addElement(DataValue value)
{
  // Increment head without explicit bound, allowing it to wrap when it
  // reaches the maximum value.
  ++head;

  // Limit the index to the array size using `%` only at the point it is
  // used as an index.
  ringBuffer[head % BUFFER_SIZE] = value;
}

这是否安全取决于

BUFFER_SIZE

。

如果

BUFFER_SIZE

始终是 2 的幂，那么这是安全的。

但是如果

BUFFER_SIZE

不是 2 的幂，那么这就不安全， 因为当

head

最终以最大值换行时，有效数组 索引将无法正确换行。 例如，如果

BUFFER_SIZE

是 10，并且

size_t

是一个32位量，最大值为4294967295，然后接近 它的极限，我们将有：

head         head % BUFFER_SIZE
----------   ------------------
4294967293   3
4294967294   4
4294967295   5
0            0      <--- oops, should have been 6!
1            1

如果

BUFFER_SIZE

是 2 的幂，这是个好主意吗？

不！ 即使算术上安全，让索引脱离 范围然后用

%

拉回来不是一个好软件 工程选择。 相反，你应该做一些简单的事情 喜欢：

if (++head == BUFFER_SIZE) {
  head = 0;
}

以下是选择简单的增量和检查方法的一些原因 无限增量：

• 不存在无限增量代码的现实场景 运行速度明显更快。 是的，它避免了一个分支，但你需要 无论如何，检查

  tail

  ，它可能很容易变慢，具体取决于

  %

  到底会变成什么样子，而且这种程度的优化 极不可能相关。

• 它仅适用于特定的缓冲区大小，这充其量是未来 维护危险。

• 由于

  head

  不存在，这使得调试变得不必要的困难 直接与数组大小进行比较。

• 当

  head

  事实上达到其极限时，总会存在潜伏的极端情况 最大值。 即使使用 32 位计数器，您也必须努力工作 测试达到极限以验证其是否有效 正确，并且使用 64 位计数器，在测试期间溢出 （如果从 0 开始递增 1）是不可行的（需要 在最快的现有硬件上进行数月的计算）。 你从来没有 想要拥有未经测试的代码路径，这些路径可能会在生产中遇到，如果 代码运行了足够长的时间。