添加冗余分配可在编译时加速代码而无需优化

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生成的程序集.两个汇编代码之间的唯一区别是,在addl $1, -12(%rbp)更快的一个之前还有两个汇编代码:

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

那么为什么程序运行得更快呢？

---

彼得的回答非常有帮助.对AMD Phenom II X4 810和ARMv7处理器(BCM2835)的测试显示了相反的结果,它支持存储转发加速特定于某些Intel CPU.
而BeeOnRope的评论和建议让我重写了这个问题.:)
这个问题的核心是与处理器架构和汇编有关的有趣现象.所以我认为值得讨论.

Answer 1

您正在对调试版本进行基准测试,这基本上是无用的.

但显然有一个真正的原因,一个版本的调试版本比另一个版本的调试版本运行得慢. (假设您测量正确,并且不仅仅是CPU频率变化(涡轮/省电)导致挂钟时间的差异.)

如果你想深入了解x86性能分析的细节,我们可以尝试解释为什么asm首先执行它的方式,以及为什么asm来自额外的C语句(-O0编译为额外的asm指令)让它整体更快. 这将告诉我们关于asm性能效果的一些信息,但对优化C没什么用处.

你没有显示整个内部循环,只显示了一些循环体,但是-O0非常可预测.每个C语句都与其他语句分开编译,所有C变量在每个语句的块之间溢出/重新加载.这使您可以在单步执行时使用调试器更改变量,甚至可以跳转到函数中的不同行,并使代码仍然有效.编译这种方式的性能成本是灾难性的.例如,你的循环没有副作用(没有使用任何结果)所以整个三重嵌套循环可以并且将在真实构建中编译为零指令,运行速度更快.

瓶颈可能是循环携带的依赖关系gcc -O0,存储/重新加载和k增加.在大多数CPU上,存储转发延迟通常约为5个周期.因此,您的内部循环仅限于每~6个循环运行一次,即内存目标的延迟add.

如果您使用的是英特尔CPU,那么当重新加载无法立即执行时,存储/重新加载延迟实际上会更低(更好).在依赖对之间具有更多独立的加载/存储可以在您的情况下解释它.请参阅循环函数调用比空循环快.

因此,在循环中进行更多工作add时,在背靠背运行时每6个周期可以维持一个吞吐量的工作可能只会产生每4或5个周期一次迭代的瓶颈.

更新:根据2013年博客文章的测量结果,这种影响显然发生在Sandybridge和Haswell上,所以是的,这也是你Broadwell i5-5257U最可能的解释.看起来这种效应发生在所有Intel Sandybridge系列CPU上.

如果没有关于测试硬件,编译器版本(或内循环的asm源)以及两个版本的绝对和/或相对性能数据的更多信息,这是我最好的低功耗猜测.addl $1, -12(%rbp)对我的Skylake系统进行基准测试/分析并不足以让我自己尝试.下一次,包括时间数字.

不属于循环承载依赖关系链的所有工作的存储/重新加载的延迟无关紧要,只有吞吐量.现代无序CPU中的存储队列确实有效地提供了内存重命名,消除了重写相同的堆栈内存以便gcc -O0在其他地方重新编写和读写之后的写后写和读后读取危险.(有关内存危险的更多信息,请参阅https://en.wikipedia.org/wiki/Memory_disambiguation#Avoiding_WAR_and_WAW_dependencies,有关延迟与吞吐量的更多信息以及重复使用相同的寄存器/寄存器重命名,请参阅此问答)

内循环的多次迭代可以同时进行,因为内存顺序缓冲区跟踪每个负载需要从哪个存储中获取数据,而不需要先前存储到同一位置以提交到L1D并离开存储队列.(有关CPU微体系结构内部的更多信息,请参阅英特尔的优化手册和Agner Fog的microarch PDF.)

这是否意味着添加无用的语句会加速真正的程序？(启用优化)

一般来说,不,它没有.编译器将循环变量保存在最内层循环的寄存器中.无用的语句实际上会在启用优化的情况下进行优化.

调整你的源代码p是没用的.gcc -O0使用项目的默认构建脚本或其他选项进行 测量.

此外,这种存储转发加速特定于Intel Sandybridge系列,你不会在像Ryzen这样的其他微体系结构上看到它,除非它们也有类似的存储转发延迟效果.

存储转发延迟可能是实际(优化)编译器输出中的问题,特别是如果您不使用链接时优化(LTO)让微小函数内联,尤其是通过引用传递或返回任何内容的函数(因此它具有通过内存而不是寄存器).缓解这个问题可能需要黑客,比如-O3你真的想在Intel CPU上解决这个问题,并且可能会让其他一些CPU更糟糕.请参阅评论中的讨论