为什么for循环体中的一个基本算术运算执行速度慢于两个算术运算？

Question

当我尝试测量算术运算的执行时间时，我遇到了非常奇怪的行为。包含< code>for循环且循环体中有一个算术运算的代码块的执行速度总是慢于在< code>for循环体中有两个算术运算的相同代码块。下面是我最后测试的代码:

#include <iostream>
#include <chrono>

#define NUM_ITERATIONS 100000000

int main()
{
    // Block 1: one operation in loop body
    {
        int64_t x = 0, y = 0;
        auto start = std::chrono::high_resolution_clock::now();

        for (long i = 0; i < NUM_ITERATIONS; i++) {x+=31;}

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = end-start;
        std::cout << diff.count() << " seconds. x,y = " << x << "," << y << std::endl;
    }

    // Block 2: two operations in loop body
    {
        int64_t x = 0, y = 0;
        auto start = std::chrono::high_resolution_clock::now();

        for (long i = 0; i < NUM_ITERATIONS; i++) {x+=17; y-=37;}

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = end-start;
        std::cout << diff.count() << " seconds. x,y = " << x << "," << y << std::endl;
    }

    return 0;
}

我测试了不同级别的代码优化（-O0，-O1，-O2和-O3），使用不同的在线编译器（例如onlinegdb.com），在我的工作机器上，在我的hame PC和笔记本电脑上，在RaspberryPi和同事的电脑上。我重新排列了这两个代码块，重复了它们，更改了常量，更改了操作（，-，）

1.05681 秒。x，y = 3100000000，0
0.90414 秒。

我检查了上的程序集输出https://godbolt.org/但一切看起来都和我预期的一样：第二个块在程序集输出中只进行了一次操作。

三个操作总是按预期运行：它们比一个慢，比四个快。那么为什么两个操作会产生这样的异常呢？

编辑：

让我重复一次：我在所有的Windows和Unix机器上都有这样的行为，代码没有优化。我查看了我执行的程序集（VisualStudio，Windows），并看到了我想在那里测试的指令。不管怎样，如果循环被优化了，在剩下的代码中就没有什么我要问的了。我在问题中添加了优化注意事项，以避免“不测量未优化代码”的答案，因为优化不是我要问的问题。问题是为什么我的计算机执行两个操作比一个更快，首先是在代码中，这些操作没有被优化。在我的测试中，执行时间的差异为5-25%（非常明显）。




Answer 1

我将代码拆分为C和程序集。我只是想测试循环，所以我没有返回总和。我在视窗上运行，调用约定是遥控车，rdx，r8，r9，循环计数在遥控车。该代码正在向堆栈上的 64 位整数添加即时值。

我得到了两个循环的相似时间，小于1%的变化，相同或其中一个比另一个快1%。

这里有一个明显的依赖因素：每次添加到内存都必须等待之前添加到同一位置的内存完成，因此两次添加到内存基本上可以并行执行。

将test2改为3添加到内存，结果慢了6%，4添加到内存慢了7.5%。

我的系统是Intel 3770K 3.5 GHz CPU，Intel DP67BG主板，DDR3 1600 9-9-9-27内存，Win 7 Pro 64 bit，Visual Studio 2015。

        .code
        public  test1
        align   16
test1   proc
        sub     rsp,16
        mov     qword ptr[rsp+0],0
        mov     qword ptr[rsp+8],0
tst10:  add     qword ptr[rsp+8],17
        dec     rcx
        jnz     tst10
        add     rsp,16
        ret     
test1   endp

        public  test2
        align 16
test2   proc
        sub     rsp,16
        mov     qword ptr[rsp+0],0
        mov     qword ptr[rsp+8],0
tst20:  add     qword ptr[rsp+0],17
        add     qword ptr[rsp+8],-37
        dec     rcx
        jnz     tst20
        add     rsp,16
        ret     
test2   endp

        end

我还测试了添加立即寄存器，1%以内的1或2个寄存器（任何一个都可以更快，但我们预计它们都将在常春藤桥上以1次迭代/时钟执行，因为它有3个整数ALU端口;在预测现代超标量处理器操作的延迟时需要考虑哪些因素，以及如何手动计算它们？

3个寄存器的长度是1.5倍，比理想的3个后端ALU端口的4个UOP(包括循环计数器宏融合dec/jnz)1.333个周期/迭代稍差。

4个寄存器，2.0倍长，前端瓶颈：执行uop计数不是处理器宽度倍数的循环时性能会降低吗？. Haswell和后来的微架构会更好地处理这个问题。

        .code
        public  test1
        align   16
test1   proc
        xor     rdx,rdx
        xor     r8,r8
        xor     r9,r9
        xor     r10,r10
        xor     r11,r11
tst10:  add     rdx,17
        dec     rcx
        jnz     tst10
        ret     
test1   endp

        public  test2
        align 16
test2   proc
        xor     rdx,rdx
        xor     r8,r8
        xor     r9,r9
        xor     r10,r10
        xor     r11,r11
tst20:  add     rdx,17
        add     r8,-37
        dec     rcx
        jnz     tst20
        ret     
test2   endp

        public  test3
        align 16
test3   proc
        xor     rdx,rdx
        xor     r8,r8
        xor     r9,r9
        xor     r10,r10
        xor     r11,r11
tst30:  add     rdx,17
        add     r8,-37
        add     r9,47
        dec     rcx
        jnz     tst30
        ret     
test3   endp

        public  test4
        align 16
test4   proc
        xor     rdx,rdx
        xor     r8,r8
        xor     r9,r9
        xor     r10,r10
        xor     r11,r11
tst40:  add     rdx,17
        add     r8,-37
        add     r9,47
        add     r10,-17
        dec     rcx
        jnz     tst40
        ret     
test4   endp

        end

Answer 2

埃塔:这是一个猜测，彼得·科德斯提出了一个很好的论点来解释为什么它是不正确的。投票支持彼得的答案。

我把我的答案留在这里，因为有些人发现这些信息很有用。虽然这不能正确解释OP中的行为，但它突出了一些问题，这些问题使得在现代处理器上测量特定指令的速度变得不可行(并且没有意义)。

有根据的猜测：

这是流水线操作、部分内核断电和动态频率调整的综合效果。

现代处理器采用流水线技术，因此可以同时执行多条指令。这是可能的，因为处理器实际上工作在微操作上，而不是我们通常认为的机器语言的汇编级指令上。处理器通过将微操作分派到芯片的不同部分来“调度”微操作，同时跟踪指令之间的依赖关系。

假设运行代码的内核有两个算术/逻辑单元（ALU）。一条重复的算术指令只需要一个ALU。使用两个ALU没有帮助，因为下一个操作取决于当前操作的完成，所以第二个ALU只是在等待。

但在双表达式测试中，表达式是独立的。要计算 y 的下一个值，您不必等待 x 上的当前操作完成。现在，由于省电功能，第二个ALU可能一开始就断电了。内核可能会运行几次迭代，然后才意识到它可以利用第二个ALU。此时，它可以启动第二个 ALU，并且大多数双表达式循环的运行速度将与单表达式循环一样快。因此，您可能希望这两个示例花费大约相同的时间。

最后，许多现代处理器使用动态频率调整。当处理器检测到它运行并不困难时，它实际上会稍微减慢它的时钟以节省功率。但当它被大量使用时(并且芯片的当前温度允许)，它可能会将实际时钟速度提高到其额定速度。

我假设这是通过启发式算法完成的。在第二个ALU保持关机的情况下，启发式算法可能会决定不值得提升时钟。在两个ALU通电并以最高速度运行的情况下，它可能会决定提升时钟。因此，两个表达式的情况应该和一个表达式的情况差不多快，实际上以更高的平均时钟频率运行，使其能够在略短的时间内完成两倍的工作。

根据你的数据，差距大约是14%。我的Windows机器空闲时大约为3.75 GHz，如果我通过在Visual Studio中构建一个解决方案来推动它，时钟会攀升到大约4.25GHz(目测任务管理器中的Performance选项卡)。时钟速度相差13%,所以我们在正确的范围内。

Answer 3

匿名用户

这种影响只发生在< code>-O0(或< code>volatile)，是编译器将变量保存在内存(而不是寄存器)中的结果。您可能会认为这只是通过< code>i 、< code>x和< code>y将固定量的额外延迟引入到循环承载的依赖链中，但现代CPU并不那么简单。

在Intel Sandybridge系列CPU上，当加载uop在它正在重新加载的数据的存储之后运行一段时间而不是立即运行时，存储转发延迟会更低。所以内存中有循环计数器的空循环是最坏的情况。我不明白哪些CPU设计选择会导致这种微架构怪癖，但这是真实的。

这基本上是在没有优化的情况下编译代码时添加冗余赋值来加速代码的重复，至少对于英特尔Sandybridge系列CPU是如此。

这是您不应该在< code>-O0进行基准测试的主要原因之一:瓶颈不同于实际优化的代码。看看clang为什么用-O0产生低效的asm(针对这个简单的浮点求和)？了解为什么编译器故意制造如此糟糕的asm。

微观基准测试很难；只有让编译器为您要测量的东西发出经过实际优化的asm循环，您才能正确测量某些东西。（即便如此，您也只是测量吞吐量或延迟，而不是两者兼而有之；对于无序流水线CPU上的单个操作，这是分开的事情：在预测现代超标量处理器上的操作延迟时需要考虑哪些因素，以及如何手动计算它们？）

有关将变量保存在寄存器中的循环会发生什么的测量解释，请参阅@rcgldr的答案。

使用叮当声，基准：:D oNotOptimize（x1 = 31）也会取消优化以将x保留在内存中，但是对于GCC，它确实只是停留在寄存器中。不幸的是，@SashaKnorre的答案在快速平台而不是gcc上使用叮当声来获得类似于-O0 asm的结果。它确实显示了大量短 NOP 被内存瓶颈隐藏的成本，并且当这些 NOP 延迟下一次迭代的时间刚好足以使存储转发达到较低延迟的良好情况时，会略微加速。（我认为QuickBench运行在英特尔至强服务器CPU上，每个CPU内核内部的微架构与同一代台式机版本相同。

据推测，您测试的所有x86机器都有过去10年的Intel CPU，否则对AMD也有类似的影响。如果您的测量在那里真的有意义，那么您的RPi使用的任何ARM CPU都可能产生类似的影响。否则，可能会出现另一种情况，即看到您的预期（确认偏差），尤其是如果您在那里启用了优化的情况下进行测试。

我测试了不同级别的代码优化（-O0，-O1，-O2和-O3）[…]，但我总是得到类似的结果

我在问题中添加了优化通知，以避免“不要测量未优化的代码”的答案，因为优化不是我要问的问题。

（后面的评论）关于优化：是的，我用不同的优化级别复制了它，但随着循环被优化，执行时间太快，无法确定。

所以实际上你没有为-O1或更高的值重现这种效应，你只是看到了你想看到的东西（确认偏差），并且主要弥补了效果是相同的声明。如果您准确报告了您的数据（-O0处的可测量效应，-O1及更高级别的空定时区域），我可以立即回答。

请参阅性能评估的惯用方法？-如果您的时间没有随着重复次数的增加而线性增加，那么您就没有测量您认为正在测量的东西。此外，启动效果（如冷缓存、软页面错误、延迟动态链接和动态CPU频率）很容易导致第一个空定时区域比第二个慢。

我假设您仅在-O0测试时交换循环，否则您将排除在-O1，或更高的测试代码中存在任何影响。

正如您在Godbolt上看到的，gcc完全移除了启用优化的循环。有时GCC会留下空循环，比如它可能认为延迟是故意的，但这里它甚至根本不循环。时间不与任何东西成比例，两个定时片段看起来都一样，如下所示:

orig_main:
   ...
        call    std::chrono::_V2::system_clock::now()       # demangled C++ symbol name
        mov     rbp, rax                                    # save the return value = start
        call    std::chrono::_V2::system_clock::now()
        # end in RAX

因此，定时区域中的唯一指令是将start保存到调用保留寄存器。你对你的源代码没有任何测量。

使用Google基准测试，我们可以得到不优化工作的asm，但它不会存储/重新加载以引入新的瓶颈：

#include <benchmark/benchmark.h>

static void TargetFunc(benchmark::State& state) {
   uint64_t x2 = 0, y2 = 0;
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    benchmark::DoNotOptimize(x2 += 31);
    benchmark::DoNotOptimize(y2 += 31);
  }
}
// Register the function as a benchmark
BENCHMARK(TargetFunc);

# just the main loop, from gcc10.1 -O3 
.L7:                         # do{
        add     rax, 31        # x2 += 31
        add     rdx, 31        # y2 += 31
        sub     rbx, 1
        jne     .L7          # }while(--count != 0)

我假设＜code＞benchmark：：DoNotOptimize＜code＞类似于＜code＞asm volatile（“：”rm“（x））（GNU C内联asm），以使编译器在寄存器或内存中具体化＜code＞x

对于GNU C兼容的编译器，我们可以手动使用asm易失性，只有“ r”寄存器约束来获得叮当声来制作良好的标量asm（Godbolt），就像GCC一样。我们得到一个本质上相同的内部循环，有3个添加指令，最后一个是可以宏融合的添加rbx，-1 / jnz。

static void TargetFunc(benchmark::State& state) {
   uint64_t x2 = 0, y2 = 0;
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
      x2 += 16;
      y2 += 17;
    asm volatile("" : "+r"(x2), "+r"(y2));
  }
}

所有这些都应该在现代Intel和AMD CPU上以每次迭代1个时钟周期运行，再次参见@rcgldr的答案。

当然，这也会禁用SIMD的自动矢量化，编译器在许多实际用例中都会这样做。或者，如果在循环之外使用结果，则可能会将重复增量优化为一次乘法。

你无法衡量C语言中< code> 操作符的开销——根据上下文/周围代码的不同，它的编译会有很大的不同。即使不考虑提升工作的循环不变的东西。例如<代码> x (y

问题实际上是为什么我的计算机执行两个操作比一个快，首先是在代码中，这些操作没有被优化掉

TL：DR：这不是操作，而是通过内存的循环携带的依赖链，它阻止CPU以每次迭代1个时钟周期运行循环，在单独的执行端口上并行执行所有3个添加。

请注意，循环计数器增量与对 x（有时是 y）执行的操作一样多。