c++ - For 循环性能差异，以及编译器优化

Question

我选择了 David 的答案，因为他是唯一一个针对没有优化标志的 for 循环中的差异提出解决方案的人。其他答案演示了设置优化标志时会发生什么。

Jerry Coffin 的回答解释了在为这个例子设置优化标志时会发生什么。仍然没有回答的是为什么 superCalculationA 运行得比 superCalculationB 慢，因为 B 为每次迭代执行一次额外的内存引用和一次加法。 Nemo 的帖子显示了汇编器输出。我用 -S 确认了这个编译按照 Matteo Italia 的建议，我的 PC 上的标志为 2.9GHz Sandy Bridge (i5-2310)，运行 Ubuntu 12.04 64 位。

当我偶然发现以下案例时，我正在试验 for 循环的性能。

我有以下代码以两种不同的方式进行相同的计算。

#include <cstdint>
#include <chrono>
#include <cstdio>

using std::uint64_t;

uint64_t superCalculationA(int init, int end)
{
    uint64_t total = 0;
    for (int i = init; i < end; i++)
        total += i;
    return total;
}

uint64_t superCalculationB(int init, int todo)
{
    uint64_t total = 0;
    for (int i = init; i < init + todo; i++)
        total += i;
    return total;
}

int main()
{
    const uint64_t answer = 500000110500000000;

    std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
    double elapsed;

    std::printf("=====================================================\n");

    start = std::chrono::high_resolution_clock::now();
    uint64_t ret1 = superCalculationA(111, 1000000111);
    end = std::chrono::high_resolution_clock::now();
    elapsed = (end - start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
    std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);

    start = std::chrono::high_resolution_clock::now();
    uint64_t ret2 = superCalculationB(111, 1000000000);
    end = std::chrono::high_resolution_clock::now();
    elapsed = (end - start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
    std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);

    if (ret1 == answer)
    {
        std::printf("The first method, i.e. superCalculationA, succeeded.\n");
    }
    if (ret2 == answer)
    {
        std::printf("The second method, i.e. superCalculationB, succeeded.\n");
    }

    std::printf("=====================================================\n");

    return 0;
}

编译此代码

g++ main.cpp -o output --std=c++11

导致以下结果:

=====================================================
Elapsed time: 2.859 s | 2859.441 ms | 2859440.968 us
Elapsed time: 2.204 s | 2204.059 ms | 2204059.262 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================

我的第一个问题是: 为什么第二个循环比第一个循环快 23%？

另一方面，如果我编译代码

g++ main.cpp -o output --std=c++11 -O1

结果改善了很多，

=====================================================
Elapsed time: 0.318 s | 317.773 ms | 317773.142 us
Elapsed time: 0.314 s | 314.429 ms | 314429.393 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================

并且时间差几乎消失了。

但是当我设置 -O2 标志时，我简直不敢相信自己的眼睛，

g++ main.cpp -o output --std=c++11 -O2

得到了这个:

=====================================================
Elapsed time: 0.000 s | 0.000 ms | 0.328 us
Elapsed time: 0.000 s | 0.000 ms | 0.208 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================

所以，我的第二个问题是: 当我设置 -O1 和 -O2 标志导致这种巨大的性能改进时，编译器在做什么？

我查了 Optimized Option - Using the GNU Compiler Collection (GCC) ，但这并没有澄清事情。

顺便说一下，我正在用 g++ (GCC) 4.9.1 编译这段代码。

编辑以确认 Basile Starynkevitch 的假设

我编辑了代码，现在 main看起来像这样:

int main(int argc, char **argv)
{
    int start = atoi(argv[1]);
    int end   = atoi(argv[2]);
    int delta = end - start + 1;

    std::chrono::time_point<std::chrono::high_resolution_clock> t_start, t_end;
    double elapsed;

    std::printf("=====================================================\n");

    t_start = std::chrono::high_resolution_clock::now();
    uint64_t ret1 = superCalculationB(start, delta);
    t_end = std::chrono::high_resolution_clock::now();
    elapsed = (t_end - t_start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
    std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);

    t_start = std::chrono::high_resolution_clock::now();
    uint64_t ret2 = superCalculationA(start, end);
    t_end = std::chrono::high_resolution_clock::now();
    elapsed = (t_end - t_start).count() * ((double) std::chrono::high_resolution_clock::period::num / std::chrono::high_resolution_clock::period::den);
    std::printf("Elapsed time: %.3f s | %.3f ms | %.3f us\n", elapsed, 1e+3*elapsed, 1e+6*elapsed);

    std::printf("Results were %s\n", (ret1 == ret2) ? "the same!" : "different!");
    std::printf("=====================================================\n");

    return 0;
}

这些修改确实增加了计算时间，对于 -O1和 -O2 .现在两者都给了我大约 620 毫秒。 这证明 -O2 确实在编译时做了一些计算 .

我仍然不明白这些标志在做什么来提高性能，以及 -Ofast做得更好，大约 320 毫秒。

另请注意，我更改了调用函数 A 和 B 以测试 Jerry Coffin 假设的顺序。在没有优化器标志的情况下编译这段代码仍然给我大约 2.2 秒的 B 和 2.8 秒的 A。所以我认为这不是缓存的事情。只是强调我是 不是 谈论第一种情况下的优化(没有标志的情况)，我只想知道是什么让秒循环比第一种运行得更快。

Answer 1

编辑:在了解更多关于处理器流水线中的依赖关系后，我修改了我的答案，删除了一些不必要的细节并提供了对减速的更具体的解释。

似乎 -O0 情况下的性能差异是由于处理器流水线。

首先，从 Nemo 的回答中复制的程序集(对于 -O0 版本)，并附有我自己的一些评论:

superCalculationA(int, int):
    pushq   %rbp
    movq    %rsp, %rbp
    movl    %edi, -20(%rbp)    # init
    movl    %esi, -24(%rbp)    # end
    movq    $0, -8(%rbp)       # total = 0
    movl    -20(%rbp), %eax    # copy init to register rax
    movl    %eax, -12(%rbp)    # i = [rax]
    jmp .L7
.L8:
    movl    -12(%rbp), %eax    # copy i to register rax
    cltq
    addq    %rax, -8(%rbp)     # total += [rax]
    addl    $1, -12(%rbp)      # i++
.L7:
    movl    -12(%rbp), %eax    # copy i to register rax
    cmpl    -24(%rbp), %eax    # [rax] < end
    jl  .L8
    movq    -8(%rbp), %rax
    popq    %rbp
    ret

superCalculationB(int, int):
    pushq   %rbp
    movq    %rsp, %rbp
    movl    %edi, -20(%rbp)    # init
    movl    %esi, -24(%rbp)    # todo
    movq    $0, -8(%rbp)       # total = 0
    movl    -20(%rbp), %eax    # copy init to register rax
    movl    %eax, -12(%rbp)    # i = [rax]
    jmp .L11
.L12:
    movl    -12(%rbp), %eax    # copy i to register rax
    cltq
    addq    %rax, -8(%rbp)     # total += [rax]
    addl    $1, -12(%rbp)      # i++
.L11:
    movl    -20(%rbp), %edx    # copy init to register rdx
    movl    -24(%rbp), %eax    # copy todo to register rax
    addl    %edx, %eax         # [rax] += [rdx]  (so [rax] = init+todo)
    cmpl    -12(%rbp), %eax    # i < [rax]
    jg  .L12
    movq    -8(%rbp), %rax
    popq    %rbp
    ret

在这两个函数中，堆栈布局如下所示:

Addr Content

24   end/todo
20   init
16   <empty>
12   i
08   total
04   
00   <base pointer>

(请注意， total 是一个 64 位的 int，因此占用了两个 4 字节的槽。)

这些是 superCalculationA() 的关键行:

    addl    $1, -12(%rbp)      # i++
.L7:
    movl    -12(%rbp), %eax    # copy i to register rax
    cmpl    -24(%rbp), %eax    # [rax] < end

堆栈地址 -12(%rbp) (保存 i 的值)被写入 addl指令，然后立即在下一条指令中读取。在写入完成之前，读取指令无法开始。这代表管道中的一个块，导致 superCalculationA()比 superCalculationB() 慢.

你可能会好奇为什么 superCalculationB()没有这个相同的管道块。它实际上只是 gcc 如何编译 -O0 中的代码的一个工件，并不代表任何根本上有趣的东西。基本上，在 superCalculationA() ，比较 i<end通过阅读 i 来执行来自 注册 , 而在 superCalculationB() ，比较 i<init+todo通过阅读 i 来执行来自 堆栈 .

为了证明这只是一个工件，让我们替换

for (int i = init; i < end; i++)

与

for (int i = init; end > i; i++)

在 superCalculateA() .生成的程序集看起来是一样的，只是对关键行进行了以下更改:

    addl    $1, -12(%rbp)      # i++
.L7:
    movl    -24(%rbp), %eax    # copy end to register rax
    cmpl    -12(%rbp), %eax    # i < [rax]

现在 i从堆栈中读取，并且管道块消失了。以下是进行此更改后的性能数据:

=====================================================
Elapsed time: 2.296 s | 2295.812 ms | 2295812.000 us
Elapsed time: 2.368 s | 2367.634 ms | 2367634.000 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================

应该注意的是，这实际上是一个玩具示例，因为我们正在使用 -O0 进行编译。在现实世界中，我们使用 -O2 或 -O3 进行编译。在这种情况下，编译器以最小化流水线块的方式对指令进行排序，我们不必担心是否要写 i<end。或 end>i .