用于循环性能差异和编译器优化

Question

---

我选择了David的答案,因为他是唯一一个在没有优化标志的for循环中提供解决方案的人.其他答案说明了在设置优化标志时会发生什么.

---

Jerry Coffin的回答解释了为此示例设置优化标志时会发生什么.仍然没有答案的是,当B执行一次额外的内存引用和每次迭代一次添加时,superCalculationA的运行速度比superCalculationB慢.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标志导致这种巨大的性能提升时,编译器正在做什么？

我检查了优化选项 - 使用GNU编译器集合(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甚至更好,大约320ms.

还要注意我已经改变了调用函数A和B的顺序来测试Jerry Coffin的假设.在没有优化器标志的情况下编译这个代码仍然让我在B中大约2.2秒,在A中大约2.8秒.所以我认为它不是缓存的东西.只是强化我在第一种情况下没有谈论优化(没有标志的那种),我只是想知道是什么让秒循环运行得比第一种更快.

Answer 1

我的直接猜测是第二个更快,不是因为你对循环所做的更改,而是因为它是第二个,所以缓存在运行时已经准备好了.

为了测试这个理论,我重新安排了你的代码,以颠倒调用两个计算的顺序:

#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 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);

    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);

    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;
}

我得到的结果是:

=====================================================
Elapsed time: 0.286 s | 286.000 ms | 286000.000 us
Elapsed time: 0.271 s | 271.000 ms | 271000.000 us
The first method, i.e. superCalculationA, succeeded.
The second method, i.e. superCalculationB, succeeded.
=====================================================

因此,当版本A首先运行时,它会变慢.当版本B第一次运行时,速度会变慢.

为了确认,我superCalculationB在对版本A或B进行计时之前添加了一个额外的调用.之后,我尝试运行该程序三次.对于那三次运行,我判断结果是平局的(版本A更快一次,版本B更快两次,但既没有可靠的赢得也没有足够宽的余量才有意义).

这并不能证明它实际上是一个缓存情况,但确实给出了一个非常强烈的迹象,表明它是调用函数的顺序,而不是代码本身的差异.

至于编译器如何使代码更快:它主要做的是展开循环的几次迭代.如果我们手动展开几次迭代,我们可以得到几乎相同的效果:

uint64_t superCalculationC(int init, int end)
{
    int f_end = end - ((end - init) & 7);

    int i;
    uint64_t total = 0;
    for (i = init; i < f_end; i += 8) {
        total += i;
        total += i + 1;
        total += i + 2;
        total += i + 3;
        total += i + 4;
        total += i + 5;
        total += i + 6;
        total += i + 7;
    }

    for (; i < end; i++)
        total += i;

    return total;
}

这有一些属性可能会发现相当奇怪:使用-O2编译时实际上比使用-O3更快.使用-O2进行编译时,使用-O3编译时,其速度也比其他两个快约五倍.

与编译器的循环展开相比,~5x速度增益的主要原因是我们已经比编译器以不同的方式展开循环(并且更智能地,IMO).我们计算f_end告诉我们展开的循环应该执行多少次.我们执行那些迭代,然后我们执行一个单独的循环来"清理"最后的任何奇数迭代.

编译器生成的代码大致相当于这样的代码:

for (i = init; i < end; i += 8) {
    total += i;
    if (i + 1 >= end) break;
    total += i + 1;
    if (i + 2 >= end) break;
    total += i + 2;
    // ...
}

虽然这比完全没有展开循环要快得多,但是从主循环中消除那些额外的检查仍然要快得多,并为任何奇数迭代执行单独的循环.

鉴于这样一个简单的循环体被执行了这么多次,你还可以通过展开循环的更多迭代来进一步提高速度(当用-O2编译时).展开了16次迭代,它的速度大约是上面代码的两倍,展开了8次迭代:

uint64_t superCalculationC(int init, int end)
{
    int first_end = end - ((end - init) & 0xf);

    int i;
    uint64_t total = 0;
    for (i = init; i < first_end; i += 16) {
        total += i + 0;
        total += i + 1;
        total += i + 2;

        // code for `i+3` through `i+13` goes here

        total += i + 14;
        total += i + 15;
    }

    for (; i < end; i++)
        total += i;

    return total;
}

我没有试图通过展开这个特定的循环来探索增益的极限,但是展开32次迭代几乎使速度再次翻倍.根据您使用的处理器,您可能会通过展开64次迭代获得一些小的收益,但我猜我们已经开始接近极限 - 在某些时候,性能提升可能会趋于平稳,然后(如果您展开更多的迭代)可能会下降,很可能是戏剧性的.

总结:使用-O3编译器展开循环的多次迭代.在这种情况下,这是非常有效的,主要是因为我们有很多几乎可能的最简单的循环体的执行.手动展开循环比让编译器更有效 - 我们可以更智能地展开,我们可以简单地展开比编译器更多的迭代.额外的智能可以为我们提供大约5:1的改进,并且额外的迭代另外4:1左右¹(以更长,稍微可读的代码为代价).

最后的警告:一如既往的优化,您的里程可能会有所不同.编译器和/或处理器的差异意味着你可能会得到至少与我不同的结果.在大多数情况下,我希望我的手动展开循环比其他两个循环快得多,但确切地说可能变化多快.

^{但请注意,这是将带有-O2的手动展开循环与带-O3的原始循环进行比较.使用-O3编译时,手动展开的循环运行得慢得多.}

Answer 2

检查装配输出真的是照亮这些东西的唯一方法.

编译器的优化将做的事情很多,包括事物不严格"符合标准"(虽然,这是不符合的情况下-O1和-O2,据我所知) -例如支票,-Ofast开关.

我发现这是很有帮助的:http://gcc.godbolt.org/,并与您的演示代码在这里

Answer 3

-02

解释-O2结果很容易,查看从Godbolt变为-O2 的代码

main:
pushq   %rbx
movl    $.LC2, %edi
call    puts
call    std::chrono::_V2::system_clock::now()
movq    %rax, %rbx
call    std::chrono::_V2::system_clock::now()
pxor    %xmm0, %xmm0
subq    %rbx, %rax
movsd   .LC4(%rip), %xmm2
movl    $.LC6, %edi
movsd   .LC5(%rip), %xmm1
cvtsi2sdq   %rax, %xmm0
movl    $3, %eax
mulsd   .LC3(%rip), %xmm0
mulsd   %xmm0, %xmm2
mulsd   %xmm0, %xmm1
call    printf
call    std::chrono::_V2::system_clock::now()
movq    %rax, %rbx
call    std::chrono::_V2::system_clock::now()
pxor    %xmm0, %xmm0
subq    %rbx, %rax
movsd   .LC4(%rip), %xmm2
movl    $.LC6, %edi
movsd   .LC5(%rip), %xmm1
cvtsi2sdq   %rax, %xmm0
movl    $3, %eax
mulsd   .LC3(%rip), %xmm0
mulsd   %xmm0, %xmm2
mulsd   %xmm0, %xmm1
call    printf
movl    $.LC7, %edi
call    puts
movl    $.LC8, %edi
call    puts
movl    $.LC2, %edi
call    puts
xorl    %eax, %eax
popq    %rbx
ret

没有调用2个函数,进一步没有比较结果.

现在为什么会这样？它当然是优化的力量,程序太简单了......

首先应用内联的强大功能,之后编译器可以看到所有参数实际上都是文字值(111,1000000111,1000000000,500000110500000000),因此也就是常量.

它发现init + todo是一个循环不变量并用end替换它们,在循环之前从B定义end作为end = init + todo = 111 + 1000000000 = 1000000111

现在已知两个循环仅包含编译时间值.它们完全相同:

uint64_t total = 0;
for (int i = 111; i < 1000000111; i++)
    total += i;
return total;

编译器看到它是一个求和,total是累加器,它是一个相等的步长1 sum所以编译器使得最终循环展开,即all,但它知道这个形式有总和

重写高斯的formel s = n*(n + 1)

111+1000000110
110+1000000109
...
1000000109+110
1000000110+111=1000000221

loops = 1000000111-111 = 1E9

一半,因为我们得到了双倍的寻找

1000000221*1E9/2 = 500000110500000000

这是结果寻找500000110500000000

现在它的结果是一个编译时常量,它可以将它与想要的结果进行比较,并注意它总是为真所以它可以删除它.

记下的时间是PC上system_clock的最短时间.

-O0

-O0的时序更加困难,并且很可能是函数和跳转缺失对齐的伪像,μops缓存和loopbuffer都喜欢32字节的对齐.如果添加一些,可以测试一下

asm("nop");

在A的循环前,2-3可能会成功.Storeforwards也喜欢他们的价值观自然对齐.

Answer 4

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

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

首先，程序集（用于 -O0 构建），从 Nemo 的答案复制，并内嵌了一些我自己的评论：

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。