计算循环缓冲区中剩余空间的简化算法？

Question

我想知道是否有比这更简单（单一）的方法来计算循环缓冲区中的剩余空间？

int remaining = (end > start)
                ? end-start
                : bufferSize - start + end;

Answer 1

如果您担心预测不佳的条件会减慢 CPU 管道的速度，您可以使用以下方法：

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize);

但这可能是过早的优化（除非您确实将其识别为热点）。 坚持使用当前的技术，这样更具可读性。

Answer 2

嗯...

int remaining = (end - start + bufferSize) % bufferSize;

13 个代币，我赢了吗？

Answer 3

如果循环缓冲区大小是 2 的幂，则可以通过使用 start 和 end 表示虚拟流中的位置而不是循环缓冲区存储中的索引来做得更好。 假设 start 和 end 是无符号的，上面的内容就变成：

int remaining= bufferSize - (end - start);

实际上从缓冲区中获取元素要复杂一些，但开销通常足够小，其幂次方为2 大小的循环缓冲区（仅使用 bufferSize - 1 进行屏蔽），使循环缓冲区的所有其他逻辑更加简单和清晰。 另外，您可以使用所有元素，因为您不再担心 end==start！

Answer 4

根据 C++ 标准，第 5.6 节第 4 段：

二元 / 运算符产生商，二元 % 运算符产生第一个表达式除以第二个表达式的余数。 如果 / 或 % 的第二个操作数为零，则行为未定义； 否则 (a/b)*b + a%b 等于 a。 如果两个操作数都非负，则余数也非负； 如果不是，则余数的符号是​​实现定义的。

脚注表明最好将商四舍五入为零，这将使余数为负。

因此，(end - start) % bufferSize 方法不能可靠地工作。 C++ 没有模算术（除了无符号整数类型提供的意义上）。

j_random_hacker 推荐的方法是不同的，看起来不错，但我不知道它在简单性或速度方面有任何实际的改进。 将布尔值转换为 int 是巧妙的，但需要心理解析，并且根据编译器和机器的不同，这种调整可能比使用 ?: 更昂贵。

我认为你已经有了最简单、最好的版本，我不会改变它。

Answer 5

失去条件：

int remaining = (end + bufferSize - start - 1) % bufferSize + 1

编辑：-1和+1适用于end == start的情况。 在这种情况下，此方法将假设缓冲区为空。 根据缓冲区的具体实现，您可能需要调整这些以避免出现相差 1 的情况。

Answer 6

我知道较旧的线程，但认为这可能会有所帮助。

不确定这在 C++ 中实现的速度有多快，但在 rtl 中，如果大小为 n^2

remaining = (end[n] ^ start[n])
            ? start[n-1:0] - end[n-1:0]
            : end[n-1:0] - start[n-1:0];

或

remaining = if (end[n] ^ start[n]) {
              start[n-1:0] - end[n-1:0]
            } else { 
              end[n-1:0] - start[n-1:0] 
            };