Helloqiu's Blog

helloqiu 的博客

Store-forwarding Speedup 现象

昨天我在知乎上看到了这样一个有趣的问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}

在一个三重循环的内部加入了一条赋值语句，却让整个程序的速度变快了！

对于这种类似玄学的问题，反正我是不太懂的，于是在好奇心的驱使下去 Stack Overflow 上提问了一下，没想到马上得到了解答。
首先，我把在 x64 下用 gcc 7.3.0 配合 -O0 得到的汇编代码放到了这里。
通过汇编我们可以看到，两份代码会议的不同就是在 addl $1, -12(%rbp) 之前，多了

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

这两行。这就是问题的核心，明明多了这两个 memory -> register 和 register -> memory 的操作，为什么反而变快了？
根据 Stack Overflow 上的回答

If you’re on Skylake, store/reload latency can actually be lower (better) when the reload can’t try to execute right away. Having more independent loads/stores in between the dependent pair may explain it in your case.

大体意思是说在 store 之后重新 reload 之间如果加入一些不相关的 load/store，在 Skylake 上时延要短一些。所以这一部分的下一句

1
addl	$1, -12(%rbp)

也就是说，在两次 k + 1 并且 CMP 的过程中，本该串行的后续操作由于乱序执行或者分支预测或者其他某些技术，让内层循环的包含不相关的 load/store 的代码已经在流水线上执行了，这让这个 6 个周期的操作实际上减小到 4-5 个周期。

同时，回答还补充了现代的 CPU 都支持 memory renaming （我猜和计算机系统结构讲的寄存器重命名类似）,也就是说根据分支预测，还在这里对 k 进行加一的时候，对 p 的操作就已经在执行了，但这样会造成数据冒险，这种内存重命名的方式可以解决这种冒险让这个解释成立。

同时，回答还还补充了内层的循环是可以同时执行多个的，因为 memory-order buffer 可以追踪每次 load 之前的 store，不用等待 store 写入 L1D（一级数据缓存），保证了这种多循环并行的正确性。

同时，回答还还还补充了，这种在循环里加代码的模式能不能用到真正的编程中呢？不能，因为编译器会把最内层循环的循环变量保存在寄存器中，并且那些没有意义的操作会直接被编译器优化掉，这也是为什么开了 -O2 这一部分代码就会执行飞快并且没有差别。几乎所有 Stack Overflow 上留言或者回答的人都说这种 -O0 的情况是不值得讨论的，因为生产环境不会用得到。

同时，回答还还还还补充了，这种现象是 skylake 上的，在其余比如 Ryzen 处理器上，这种现象应该就不会出现。我实际上在 broadwell 上也复现了，但是在 raspberry pi 上得到的结果的确是删掉之后变快了，和这种奇怪的现象不符，which 验证了 Stack Overflow 上的回答。个人猜测这可能是 intel CPU 独有的特性。

附 Stack Overflow 上的链接：Add an assignment but the code runs faster
知乎链接： https://www.zhihu.com/question/268453752/answer/338007479

技术