c++ - 用于计算循环缓冲区中剩余空间的简化算法？

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 推荐的方法不同，看起来不错，但我不知道它在简单性或速度方面有什么实际改进。boolean 到 int 的转换很巧妙，但需要心理解析，而且这种摆弄可能比使用 ?: 更昂贵，具体取决于编译器和机器。

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

Answer 5

失去条件：

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

编辑：-1and+1适用于 when 的情况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] 
            };