15

当我尝试测量算术运算的执行时间时,我遇到了非常奇怪的行为。包含for在循环体中具有一个算术运算的循环的代码块的执行速度总是比相同的代码块慢,但在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 秒。x,y = 1700000000,-3700000000

我检查了https://godbolt.org/上的程序集输出,但一切看起来都像我预期的那样:第二个块在程序集输出中又多了一个操作。

三个操作总是按预期运行:它们比1慢,比4快。那么为什么两次操作会产生这样的异常呢?

编辑:

让我重复一遍:我的所有 Windows 和 Unix 机器上都有这样的行为,但代码没有优化。我查看了我执行的程序集(Visual Studio、Windows),我看到了我想在那里测试的指令。无论如何,如果循环被优化掉,我在剩下的代码中没有任何问题。我在问题中添加了优化通知以避免“不测量未优化代码”的答案,因为优化不是我所问的。问题实际上是为什么我的计算机执行两个操作比一个更快,首先是在这些操作没有被优化掉的代码中。在我的测试中,执行时间的差异是 5-25%(非常明显)。

4

5 回答 5

10

这种效果只发生在-O0(或与volatile),并且是编译器将变量保存在内存(而不是寄存器)中的结果。 您希望通过ix和将固定数量的额外延迟引入循环承载的依赖链y,但现代 CPU 并不是那么简单。

在英特尔 Sandybridge 系列 CPU 上,当加载 uop 在重新加载其数据的存储之后运行一段时间时,存储转发延迟较低,而不是立即。 因此,在内存中有循环计数器的空循环是最坏的情况。我不明白什么样的 CPU 设计选择会导致这种微架构怪癖,但它是真实存在的。

这基本上是在没有优化的情况下编译时添加冗余分配加速代码的副本,至少对于英特尔 Sandybridge 系列 CPU。

这是您不应该在 进行基准测试-O0的主要原因之一:瓶颈与实际优化的代码不同。请参阅为什么 clang 会使用 -O0 产生低效的 asm(对于这个简单的浮点总和)?了解更多关于为什么编译器故意制造如此糟糕的 asm 的信息。

微基准测试很难;如果您可以让编译器为您要测量的东西发出实际优化的 asm 循环,那么您只能正确地测量一些东西。(即便如此,您也只是在测量吞吐量延迟,而不是两者;对于乱序流水线 CPU 上的单个操作,这些是不同的事情:在预测现代超标量处理器上的操作延迟时需要考虑哪些因素以及如何计算它们用手?

有关将变量保存在寄存器中的循环的测量+解释,请参阅@rcgldr 的答案。

使用 clang,benchmark::DoNotOptimize(x1 += 31)也会去优化以保存x在内存中,但使用 GCC,它确实只是保留在寄存器中。不幸的是,@SashaKnorre 的答案在 QuickBench 上使用了 clang,而不是 gcc,以获得类似于您的-O0asm 的结果。它确实显示了许多短 NOP 被内存瓶颈隐藏的成本,以及当这些 NOP 延迟重新加载下一次迭代的时间足够长以使存储转发达到较低延迟的好情况时略有加速。(我认为 QuickBench 在 Intel Xeon 服务器 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 Benchmark,我们可以获得不会优化工作但不会存储/重新加载以引入新瓶颈的 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)

我假设benchmark::DoNotOptimize类似于asm volatile("" : "+rm"(x) )GNU C inline asm)使编译器x在寄存器或内存中具体化,并假设左值已被该空 asm 语句修改。(即忘记它所知道的关于值的任何事情,阻止常量传播、CSE 等等。)这可以解释为什么当 GCC 选择一个寄存器时 clang 存储/重新加载到内存:这是一个长期存在的缺少优化的 bug,它具有 clang 的内联 asm 支持. 它喜欢在有选择的情况下选择内存,有时您可以使用多种替代约束(例如"+r,m". 但不是在这里;我不得不放弃记忆替代品;无论如何,我们不希望编译器溢出/重新加载到内存中。

对于 GNU C 兼容的编译器,我们可以asm volatile手动使用只有"+r"寄存器约束来让 clang 制作好的标量汇编(Godbolt),比如 GCC。我们得到一个基本相同的内部循环,有 3 个添加指令,最后一个是可以宏融合的add 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++ 中运算符的成本 - 它可以根据上下文/周围代码进行非常不同的编译。即使不考虑提升工作的循环不变的东西。例如x + (y<<2) + 4,可以编译为 x86 的单个 LEA 指令。


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

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

请注意,循环计数器增量与您正在使用的操作x(有时y)一样多。

于 2020-06-04T00:51:41.223 回答
6

ETA: 这是一个猜测,Peter Cordes 对为什么它不正确做了很好的论证。去投票彼得的答案。

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


有根据的猜测:

它是流水线、关闭内核部分电源和动态频率缩放的综合效果。

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

假设运行代码的核心有两个算术/逻辑单元 (ALU)。一遍又一遍地重复的单个算术指令只需要一个 ALU。使用两个 ALU 无济于事,因为下一个操作取决于当前操作的完成,因此第二个 ALU 只会等待。

但是在您的两个表达式测试中,表达式是独立的。要计算 的下一个值y,您不必等待当前操作x完成。现在,由于节能特性,第二个 ALU 可能首先会断电。在意识到它可以使用第二个 ALU 之前,内核可能会运行几次迭代。此时,它可以启动第二个 ALU,大多数双表达式循环的运行速度将与单表达式循环一样快。因此,您可能期望这两个示例花费的时间大致相同。

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

我认为这是通过启发式方法完成的。在第二个 ALU 保持断电的情况下,启发式可能会决定不值得提高时钟。在两个 ALU 上电并以最高速度运行的情况下,它可能会决定提高时钟。因此,本应与单表达式情况一样快的双表达式案例实际上以更高的平均时钟频率运行,使其能够在略短的时间内完成两倍的工作。

鉴于您的数字,差异约为 14%。我的 Windows 机器在大约 3.75 GHz 时闲置,如果我通过在 Visual Studio 中构建一个解决方案来稍微推动它,时钟会攀升到大约 4.25GHz(观察任务管理器中的性能选项卡)。这是时钟速度的 13% 差异,所以我们处于正确的范围内。

于 2020-06-01T17:14:10.287 回答
5

我将代码拆分为 C++ 和程序集。我只是想测试循环,所以我没有返回总和。我在 Windows 上运行,调用约定是rcx, rdx, r8, r9,循环计数在rcx. 该代码将立即值添加到堆栈上的 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 位,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 个寄存器(两者都可能更快,但我们希望它们都在 Ivy Bridge 上以 1 次迭代/时钟执行,因为它有 3 个整数 ALU 端口;有什么考虑预测现代超标量处理器上的操作延迟以及如何手动计算它们?)。

3 个寄存器的长度是 1.5 倍,比理想的 1.333 个周期/迭代从 4 个微指令(包括循环计数器宏融合 dec/jnz)的 3 个具有完美调度的后端 ALU 端口稍差。

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
于 2020-06-01T19:22:49.220 回答
2

@PeterCordes在许多假设中证明了这个答案是错误的,但作为对该问题的一些盲目研究尝试,它仍然很有用。

我设置了一些快速基准,认为它可能以某种方式与代码内存对齐有关,这真是一个疯狂的想法。

但似乎@Adrian McCarthy 在动态频率缩放方面做得对。

无论如何,基准测试表明插入一些 NOP 可以帮助解决这个问题,在块 1 中 x+=31 之后的 15 个 NOP 导致与块 2 几乎相同的性能。真正令人惊讶的是,单指令循环体中的 15 个 NOP 如何提高性能。

http://quick-bench.com/Q_7HY838oK5LEPFt-tfie0wy4uA

我还尝试过 -Ofast 认为编译器可能足够聪明,可以丢弃一些插入此类 NOP 的代码内存,但似乎并非如此。 http://quick-bench.com/so2CnM_kZj2QEWJmNO2mtDP9ZX0

编辑:感谢@PeterCordes,很明显优化在上述基准测试中从未像预期的那样工作(因为全局变量需要添加指令来访问内存),新基准http://quick-bench.com/HmmwsLmotRiW9xkNWDjlOxOTShE清楚地表明 Block对于堆栈变量,1 和块 2 的性能相同。但是 NOP 仍然可以通过循环访问全局变量来帮助单线程应用程序,在这种情况下您可能不应该使用它,而只是在循环之后将全局变量分配给局部变量。

编辑 2:实际上优化从未奏效,因为快速基准宏使变量访问不稳定,从而阻止了重要的优化。只加载一次变量是合乎逻辑的,因为我们只是在循环中修改它,因此易失性或禁用的优化是瓶颈。所以这个答案基本上是错误的,但至少它显示了 NOP 如何加速未优化的代码执行,如果它在现实世界中有意义的话(有更好的方法,比如分桶计数器)。

于 2020-06-01T18:04:07.840 回答
1

如今,处理器非常复杂,我们只能猜测。

编译器发出的程序集并不是真正执行的。CPU 的微码/固件/任何东西都会解释它并将其转换为执行引擎的指令,就像 C# 或 java 等 JIT 语言一样。

这里要考虑的一件事是,对于每个循环,没有 1 或 2 条指令,而是 n + 2,因为您还会递增 i 并将其与您的迭代次数进行比较。在绝大多数情况下,这无关紧要,但在这里它确实如此,因为循环体是如此简单。

让我们看看组装:

一些定义:

#define NUM_ITERATIONS 1000000000ll
#define X_INC 17
#define Y_INC -31

C/C++:

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

ASM:

    mov     QWORD PTR [rbp-32], 0
.L13:
    cmp     QWORD PTR [rbp-32], 999999999
    jg      .L12
    add     QWORD PTR [rbp-24], 17
    add     QWORD PTR [rbp-32], 1
    jmp     .L13
.L12:

C/C++:

for (long i = 0; i < NUM_ITERATIONS; i++) {x+=X_INC; y+=Y_INC;}

ASM:

    mov     QWORD PTR [rbp-80], 0
.L21:
    cmp     QWORD PTR [rbp-80], 999999999
    jg      .L20
    add     QWORD PTR [rbp-64], 17
    sub     QWORD PTR [rbp-72], 31
    add     QWORD PTR [rbp-80], 1
    jmp     .L21
.L20:

所以这两个程序集看起来非常相似。但是让我们三思而后行:现代 CPU 具有 ALU,其运算的值大于其寄存器大小。所以有可能比第一种情况下,对 x 和 i 的操作是在同一个计算单元上完成的。但是你必须再次阅读 i ,因为你对这个操作的结果设置了一个条件。阅读意味着等待。

因此,在第一种情况下,要在 x 上迭代,CPU 可能必须与 i 上的迭代同步。

在第二种情况下,可能 x 和 y 在与处理 i 的单元不同的单元上处理。所以事实上,你的循环体与驱动它的条件并行运行。你的 CPU 计算和计算一直在进行,直到有人告诉它停止。走得太远也没关系,与刚刚获得的时间相比,返回几个循环仍然很好。

因此,为了比较我们想要比较的内容(一个操作与两个操作),我们应该尝试让 i 不碍事。

一种解决方案是通过使用 while 循环完全摆脱它:C/C++:

while (x < (X_INC * NUM_ITERATIONS)) { x+=X_INC; }

ASM:

.L15:
    movabs  rax, 16999999999
    cmp     QWORD PTR [rbp-40], rax
    jg      .L14
    add     QWORD PTR [rbp-40], 17
    jmp     .L15
.L14:

另一种是使用过时的“注册”C 关键字:C/C++:

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

ASM:

    mov     ebx, 0
.L17:
    cmp     rbx, 999999999
    jg      .L16
    add     QWORD PTR [rbp-48], 17
    add     rbx, 1
    jmp     .L17
.L16:

这是我的结果:

x1 为:10.2985 秒。x,y =
17000000000,0 x1 而:8.00049 秒。x,y =
17000000000,0 x1 注册时间:7.31426 秒。x,y =
17000000000,0 x2 为:9.30073 秒。x,y = 17000000000,-31000000000
x2 而:8.88801 秒。x,y = 17000000000,-31000000000
x2 注册时间:8.70302 秒。x,y = 17000000000,-31000000000

代码在这里:https ://onlinegdb.com/S1lAANEhI

于 2020-06-02T21:10:18.860 回答