performance - 在没有优化的情况下添加冗余分配可以加快代码的速度

Question

我发现一个有趣的现象:

#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倍以上的平均运行时间:

还有其他人在其他英特尔平台上测试该案例并获得相同结果。
我发布了由GCC here生成的程序集。两种汇编代码之间的唯一区别是，在 addl $1, -12(%rbp)之前，速度较快的一种具有两种更多的操作:

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

那么，为什么用这样的分配程序运行得更快？

Peter's answer非常有帮助。在 AMD Phenom II X4 810 和 ARMv7处理器(BCM2835)上进行的测试显示了相反的结果，该结果支持存储转发加速特定于某些Intel CPU。
BeeOnRope's comment and advice驱使我重写了问题。 :)
这个问题的核心是与处理器架构和组装相关的有趣现象。因此，我认为值得讨论。

Answer 1

TL:DR:如果重新加载不是立即尝试进行，则Sandybridge系列存储转发的延迟较低。添加无用的代码可以加快调试模式的循环，因为-O0反优化代码中的循环延迟延迟几乎总是涉及某些C变量的存储/重载。
其他示例:hyperthreading，calling an empty function，accessing vars through pointers。

这些都与优化代码无关。存储转发延迟有时会出现瓶颈，但是给您的代码增加无用的复杂性并不能加快速度。

您正在对调试版本which is basically useless 进行基准测试。

但是显然，一个版本的调试版本比另一版本的调试版本运行缓慢的确有原因。 (假设您正确地进行了测量，这不仅是导致挂钟时间不同的CPU频率变化(涡轮增压/节能)。)

如果您想了解x86性能分析的详细信息，我们可以尝试解释为什么asm首先执行它的方式，以及为什么额外的C语句(带有-O0的asm编译为额外的asm指令)中的asm可以使整体速度更快。 这将告诉我们一些有关asm性能影响的信息，但对于优化C并没有任何帮助。

您没有显示整个内部循环，仅显示了部分循环主体，但是gcc -O0是pretty predictable。每个C语句都与其他所有C语句分开编译，所有C变量在每个语句的块之间溢出/重新加载。这样，您就可以在单步执行时使用调试器来更改变量，甚至可以跳到函数中的另一行，并使代码仍然有效。以这种方式进行编译的性能成本是灾难性的。例如，您的循环没有副作用(不使用任何结果)，因此整个三嵌套循环可以并且将在实际构建中编译为零指令，并且运行速度无限快。或者更现实的是，即使不进行优化或进行重大转换，每次迭代运行1个周期而不是大约6个周期。

瓶颈可能是对k的循环依赖，带有存储/重载和add来增加。存储转发延迟通常为around 5 cycles on most CPUs。因此，您的内部循环仅限于每〜6个周期运行一次，这是内存目标add的延迟。

如果您使用的是Intel CPU，则当重新加载无法立即尝试执行时，存储/重新加载延迟实际上会更低(更好)。在依赖对之间有更多独立的加载/存储可能会解释您的情况。参见Loop with function call faster than an empty loop。

因此，如果在循环中进行更多工作，那么在连续运行时可以维持每6个周期吞吐量一次的addl $1, -12(%rbp)可能只会造成每4或5个周期一次迭代的瓶颈。

根据from a 2013 blog post的测量，这种影响显然发生在Sandybridge和Haswell(不仅是Skylake)上，所以是的，这也是Broadwell i5-5257U上最有可能的解释。看来这种影响发生在所有Intel Sandybridge系列CPU 上。

如果没有有关测试硬件，编译器版本(或内部循环的asm源)，以及这两个版本的绝对和/或相对性能数字的更多信息，这是我最好的省力猜测。在Skylake系统上进行基准测试/分析gcc -O0不够有趣，无法自己亲自尝试。下次，包括计时编号。

与循环无关的链中不包含的所有工作的存储/重载延迟并不重要，仅吞吐量无关紧要。现代无序CPU中的存储队列确实有效地提供了内存重命名，从而消除了write-after-write and write-after-read hazards重复使用相同的堆栈内存来写入p，然后在其他地方读取和写入的情况。 (有关详细的内存危害，请参见https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_WAR_and_WAW_dependencies；有关延迟与吞吐量的关系以及更多地重用同一寄存器/寄存器重命名，请参见this Q&A)

内部循环可以一次进行多次迭代，因为内存顺序缓冲区可以跟踪每个负载需要从哪个存储区获取数据，而无需将先前的存储区移至相同的位置以提交到L1D并退出。存储队列。 (有关CPU微体系结构内部的更多信息，请参阅Intel的优化手册和Agner Fog的microarch PDF。)

这是否意味着添加无用的语句将加快实际程序的速度？ (启用优化)

通常，不，它不是。编译器将循环变量保存在最内层循环的寄存器中。而无用的语句实际上将在启用优化的情况下进行优化。

调整gcc -O0的源是没有用的。 使用-O3或项目使用的默认构建脚本的任何选项进行度量。

另外，这种存储转发加速是特定于Intel Sandybridge系列的，除非在Ryzen之类的其他微体系结构上，您也不会看到它，除非它们也具有类似的存储转发延迟效果。

在真正的(优化的)编译器输出中，存储转发延迟可能是一个问题，尤其是如果您没有使用链接时间优化(LTO)来使微型函数内联，尤其是那些通过引用传递或返回任何内容的函数(因此它必须通过内存而不是寄存器)。如果您真的想在Intel CPU上解决该问题，则缓解此问题可能需要volatile之类的黑客，并且可能使某些其他CPU的情况更糟。参见discussion in comments