没有进行优化编译时，添加冗余赋值可以加快代码速度

Question

没有进行优化编译时，添加冗余赋值可以加快代码速度

performanceassemblyx86cpu-architecturemicro-architecture

9

我发现一个有趣的现象：

#include<stdio.h>
#include<time.h>

int main() {
    int p, q;
    clock_t s,e;
    s=clock();
    for(int i = 1; i < 1000; i++){
        for(int j = 1; j < 1000; j++){
            for(int k = 1; k < 1000; k++){
                p = i + j * k;
                q = p;  //Removing this line can increase running time.
            }
        }
    }
    e = clock();
    double t = (double)(e - s) / CLOCKS_PER_SEC;
    printf("%lf\n", t);
    return 0;
}

我使用在i5-5257U Mac OS上的GCC 7.3.0编译代码，没有进行任何优化。这是10次运行的平均运行时间：

也有其他人在其他Intel平台上测试此案例并获得相同的结果。我在这里张贴了由GCC生成的汇编代码：这里。两个汇编代码之间唯一的区别是在addl $1, -12(%rbp)之前，速度更快的那一个多了两个操作。

movl    -44(%rbp), %eax
movl    %eax, -48(%rbp)

那么为什么这样的赋值会使程序运行更快呢？

Peter的回答非常有帮助。在AMD Phenom II X4 810和ARMv7处理器（BCM2835）上进行的测试显示了与一些Intel CPU相关的存储转发加速相反的结果。
BeeOnRope的评论和建议促使我重新编写问题。 :)
这个问题的核心是与处理器架构和汇编相关的有趣现象。因此，我认为它值得讨论。

- helloqiu

5

你是否开启了优化来构建？任何没有启用优化的基准测试几乎毫无价值。 - Some programmer dude

2

“Runs faster”--快了多少？您能展示10次试验的运行时间吗？ - Ajay Brahmakshatriya

4

你正在对调试版本进行基准测试，这基本上是没有用的。但如果你想知道具体原因，瓶颈可能是所有存储/重载操作，很可能是关于k的循环依赖。如果你使用的是Skylake处理器，那么当相关的配对操作之间有更多操作（包括其他存储/加载操作）时，存储/重载延迟实际上可以更低（更好）。 - Peter Cordes

4

不进行任何优化是不够用于基准测试的。请至少使用“-O2”。 - Some programmer dude

5

我不同意@TobySpeight的观点。编译时没有使用优化对性能分析没有用处，但不管编译器设置如何，有可能会问为什么编译器发出的某个汇编片段比另一个慢，尽管第一个语句数量更少。这本身就是有趣的，正如Peter的答案所示。 - BeeOnRope

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

TL:DR: Sandybridge家族的存储转发在重新加载不需要立即发生时具有更低的延迟。添加无用代码可以加速调试模式循环，因为在-O0反优化代码中，循环延迟瓶颈几乎总是涉及C变量的存储/重新加载。
其他示例包括：超线程, 调用空函数, 通过指针访问变量。
而且显然也适用于低功耗Goldmont，除非那里有不同的原因导致额外的加载。

对于优化的代码来说，这些都不相关。存储转发延迟的瓶颈偶尔会发生，但是在代码中添加无用的复杂性并不能加速它。

你正在对调试版本进行基准测试，这基本上是无用的。它们与优化代码有不同的瓶颈，而不是统一的减速。

但显然，一个版本的调试构建运行速度比另一个版本的调试构建慢，这其中肯定有真正的原因。(假设您正确地测量了时间，并且不是CPU频率变化(涡轮/节能)导致墙钟时间差异。)

如果您想深入了解x86性能分析的细节，我们可以尝试解释为什么汇编会以第一种方式执行，以及为什么来自额外C语句的汇编(使用-O0编译为额外的汇编指令)可以使它整体上更快。这将告诉我们一些关于汇编性能影响的信息，但对优化C没有任何用处。

你没有展示整个内部循环，只有一些循环体，但是gcc -O0是相当可预测的。每个C语句都单独编译，与其他语句分开，每个语句块之间都要溢出/重新加载所有C变量。这使得您可以在单步调试时更改变量，甚至跳转到函数中的不同行，并且代码仍然有效。以这种方式编译的性能成本是灾难性的。例如，您的循环没有副作用（没有使用任何结果），因此整个三重嵌套循环可以编译为零条指令，在实际构建中无限制地运行得更快。或者更现实地说，即使没有优化或进行主要转换，每次迭代也可以运行1个周期，而不是约6个周期。

瓶颈可能在于循环中对k的依赖性，需要进行存储/重新加载和add操作来递增。存储转发延迟通常在大多数CPU上约为5个时钟周期左右。因此，内部循环仅能每6个时钟周期运行一次，即内存目标add的延迟。

如果您使用的是英特尔CPU，则当重新加载不能立即执行时，存储/重新加载延迟实际上可以更低（更好）。在相关情况下，具有更多独立的加载/存储操作可能会解释这一点。请参见Loop with function call faster than an empty loop。

因此，随着循环中的工作量增加，那个addl $1, -12(%rbp)将无法保持每6个时钟周期一次的吞吐量，而可能变成每4或5个周期只能迭代一次的瓶颈。

这种效应显然会在Sandybridge和Haswell上发生（不仅仅是Skylake），根据2013年博客文章的测量结果，因此是您的Broadwell i5-5257U最可能的解释。看来所有英特尔Sandybridge系列CPU都会发生这种效应。

没有更多有关您的测试硬件、编译器版本（或内部循环的汇编源代码）以及两个版本的绝对和/或相对性能数字，这是我最好的低成本猜测解释。在我的Skylake系统上进行基准测试/分析gcc -O0并不足够有趣，无法亲自尝试。下次请包含时间数字。

对于所有不属于循环相关依赖链的工作，存储/重新加载的延迟并不重要，只有吞吐量很重要。现代乱序CPU中的存储队列有效地提供了内存重命名，消除了写后写和写后读冲突，可以重用相同的堆栈内存来写入然后在其他地方读取和写入p。(有关特定的内存冲突，请参见https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_WAR_and_WAW_dependencies，有关延迟与吞吐量以及重用相同寄存器/寄存器重命名，请参见this Q&A)

内部循环的多个迭代可以同时进行，因为内存序缓冲区（MOB）会跟踪每个加载需要从哪个存储中获取数据，而不需要先前的相同位置的存储提交到L1D并离开存储队列。（有关CPU微架构内部的更多信息，请参见英特尔的优化手册和Agner Fog的微架构PDF。MOB是存储缓冲区和加载缓冲区的组合）

这是否意味着添加无用语句会加速实际程序？（启用优化）

一般来说，不会。编译器会将循环变量保存在最内层的寄存器中。并且启用优化后，无用语句实际上会被优化掉。

为gcc -O0调整源代码是没有用的。请使用-O3进行测试，或者使用您的项目默认构建脚本提供的其他选项。

此外，存储转发加速是针对英特尔Sandybridge系列的特定优化，除非其他微架构也具有类似的存储转发延迟效果，否则您在其他微架构上如Ryzen上看不到此优化效果。

存储转发延迟在实际（经过优化的）编译器输出中可能会成为问题，特别是如果您没有使用链接时优化（LTO）来让微小函数内联，尤其是那些通过引用传递或返回任何内容的函数（因此必须通过内存而不是寄存器）。缓解这个问题可能需要一些hack，比如如果你真的想在Intel CPU上解决它，可以使用volatile，但可能会在其他CPU上使情况变得更糟。请参见评论中的讨论。