C++ 中哪个更快：mod (%) 还是另一个计数器？

Question

冒着重复的风险，也许我现在找不到类似的帖子：

我正在用 C++（具体来说是 C++20）编写。我有一个带有计数器的循环，每转一次都会进行计数。我们就这样称呼它吧counter。如果counter达到页面限制（我们称之为page_limit），程序应该继续下一页。所以它看起来像这样：

const size_t page_limit = 4942;
size_t counter = 0;
while (counter < foo) {
    if (counter % page_limit == 0) {
        // start new page
    }
    
    // some other code
    counter += 1;
}

现在我想知道，因为计数器变得相当高：如果我不让程序counter % page_limit每次都计算模数，而是创建另一个计数器，程序运行得会更快吗？它可能看起来像这样：

const size_t page_limit = 4942;
size_t counter = 0;
size_t page_counter = 4942;
while (counter < foo) {
    if (page_counter == page_limit) {
        // start new page
        page_counter = 0;
    }

    // some other code
    counter += 1;
    page_counter += 1;
}

Answer 1

（我假设你的意思是写if(x%y==0)not if(x%y)，相当于计数器。）

我不认为编译器会为你做这种优化，所以它可能是值得的。即使您无法测量速度差异，代码大小也会更小。这x % y == 0条路仍然有分支（因此在分支预测正确的罕见情况下仍然会受到分支错误预测的影响）。它唯一的优点是它不需要单独的计数器变量，只需要循环中某一点的一些临时寄存器。但每次迭代都需要除数。

总的来说，这对于代码大小来说应该更好，并且如果您习惯了这种习惯用法，那么可读性也不会降低。（特别是如果您使用if(--page_count == 0) { page_count=page_limit; ...so 所有逻辑片段都位于相邻的两行中。）

如果您page_limit不是编译时常量，这更有可能有帮助。 每多次递减只需要一次，这比 //便宜dec/jz很多，包括前端吞吐量。（在 Intel CPU 上微编码为大约 10 uops，因此即使它是一条指令，它仍然占用前端多个周期，从而占用了将周围代码放入无序后端的吞吐量资源） 。divtest edx,edxjzdiv

（对于常量除数，它仍然是乘法，右移，sub 来得到商，然后乘法和减法得到余数。所以仍然有几个单微指令指令。尽管有一些通过小常量进行整除性测试的技巧，请参见@Cassio Neri 关于快速整除测试（按 2,3,4,5,.., 16）的回答？其中引用了他的期刊文章；最近的 GCC 可能已经开始使用这些文章。）

但是，如果您的循环体不会成为前端指令/uop 吞吐量（在 x86 上）或除法器执行单元的瓶颈，那么乱序 exec 可能会隐藏指令的大部分div成本。它不在关键路径上，因此如果它的延迟与其他计算并行发生，并且有空闲的吞吐量资源，那么它可能大部分是空闲的。（分支预测+推测执行允许执行继续，而无需等待分支条件已知，并且由于这项工作独立于其他工作，因此它可以“提前运行”，因为编译器可以看到未来的迭代。）

尽管如此，让这项工作变得更便宜可以帮助 CPU 更快地发现并处理分支错误预测。但具有快速恢复功能的现代 CPU 可以在恢复时继续处理分支之前的旧指令。（当 skylake CPU 错误预测分支时到底会发生什么？ /通过提前计算条件来避免停止管道）

当然，一些循环确实可以完全保持 CPU 的吞吐量资源繁忙，而不是因缓存未命中或延迟链而成为瓶颈。每次迭代执行的 uop 越少，对其他超线程（或一般的 SMT）就越友好。

或者，如果您关心在有序 CPU 上运行的代码（常见于 ARM 和其他针对低功耗实现的非 x86 ISA），则真正的工作必须等待分支条件逻辑。（只有硬件预取或缓存未命中加载以及类似的事情可以在运行额外代码来测试分支条件时做有用的工作。）

划分工作确实占用了 ROB（重新排序缓冲区）中更多的空间，因此减少了 CPU 可以看到的乱序执行的距离，以在其之前/之后的代码之间找到独立的工作。

使用递减计数器

您实际上希望手持编译器使用可以编译为dec reg / jz .new_page或类似的递减计数器，而不是向上计数；所有普通的 ISA 都可以相当便宜地做到这一点，因为它与你在普通循环底部找到的东西是一样的。（dec/jnz在非零时保持循环）

    if(--page_counter == 0) {
        /*new page*/;
        page_counter = page_limit;
    }

递减计数器在 asm 中效率更高，并且在 C 中同样具有可读性（与递增计数器相比），因此如果您要进行微优化，则应该这样编写。相关：在手写 asm FizzBu​​zz 中使用该技术。也许还对3 和 5 的倍数的 asm sum进行代码审查，但它对于不匹配没有任何作用，因此优化它是不同的。

请注意，它page_limit只能在 if body 内部访问，因此如果编译器的寄存器不足，它很容易溢出，并且只根据需要读取它，而不是与它或乘法器常量绑定寄存器。

或者，如果它是已知常量，则只是立即移动指令。（大多数 ISA 也具有比较立即数，但不是全部。例如，MIPS 和 RISC-V 仅具有比较和分支指令，这些指令使用指令字中的空间作为目标地址，而不是立即数。）许多 RISC ISA 具有特别支持有效地将寄存器设置为比大多数采用立即数的指令（例如movw具有 16 位立即数的 ARM）更宽的常量，因此4092可以在一条指令中完成，mov但不能cmp：它不适合由立即数循环的 12 位偶数）。

与除法（或乘法逆元）相比，大多数 RISC ISA 没有立即数乘法，并且乘法逆元通常比一个立即数可以容纳的范围更宽。（x86 确实具有乘法立即数，但不适用于为您提供上半部分的形式。）除法立即数甚至更罕见，甚至 x86 根本没有这种功能，但没有编译器会使用它，除非针对空间而不是速度进行优化如果它确实存在的话。

像 x86 这样的 CISC ISA 通常可以使用内存源操作数进行乘法或除法，因此如果寄存器不足，编译器可以将除数保留在内存中（特别是如果它是运行时变量）。每次迭代加载一次（命中缓存）并不昂贵。page_count但是，如果循环足够短并且没有足够的寄存器，则溢出和重新加载在循环内更改的实际变量（例如）可能会引入存储/重新加载延迟瓶颈。（尽管这可能不太合理：如果您的循环体足够大，需要所有寄存器，那么它可能有足够的延迟来隐藏存储/重新加载。）