c++ - 配置文件引导优化后嵌套 for 循环更快，但缓存未命中率更高

Question

我有一个程序，它的核心是一个二维数组，形式为 a

std::vector<std::vector< int > > grid

还有一个简单的双 for 循环，有点像这样:

for(int i=1; i<N-1; ++i)
    for(int j=1; j<N-1; ++j)
        sum += grid[i][j-1] + grid[i][j+1] + grid[i-1][j] + grid[i+1][j] + grid[i][j]*some_float;

使用 g++ -O3 它运行得非常快，但为了进一步优化，我使用 callgrind 进行了分析，发现 L1 缓存未命中率约为 37%，而 LL 为 33%，虽然很多但也不算太多考虑到计算的随机性，这令人惊讶。所以我做了一个配置文件引导的优化 la

g++ -fprofile-generate -O3 ...
./program
g++ -fprofile-use -O3 ...

程序运行速度提高了大约 48%!但令人费解的是:缓存未命中甚至增加了! L1 数据缓存未命中率现在为 40%，LL 相同。

怎么可能呢？循环中没有可以优化预测的条件，缓存未命中率甚至更高。但速度更快。

编辑:好的，这是 sscce:http://pastebin.com/fLgskdQG .在不同的运行时使用 N。编译通过

g++ -O3 -std=c++11 -sscce.cpp

在 linux 下的 gcc 4.8.1 上。

使用上述命令进行配置文件引导的优化。 Callgrind 是通过 g++ -g 开关和 valgrind --tool=callgrind --simulate-cache=yes ./sscce

完成的

Answer 1

我注意到使用或不使用 PGO 生成的汇编代码之间只有一个显着差异。如果没有 PGO，sum 变量从寄存器溢出到内存，每次内部循环迭代一次。理论上，将变量写入内存并将其加载回内存可能会显着降低速度。幸运的是，现代处理器通过存储到加载转发对其进行了优化，因此速度下降的幅度并不大。 Intel 的优化手册仍然不建议将浮点变量溢出到内存中，尤其是当它们由长延迟操作(如浮点乘法)计算时。

这里真正令人费解的是为什么 GCC 需要 PGO 来避免寄存器溢出到内存。未使用的浮点寄存器已经足够了，即使没有 PGO 编译器也可以从单个源文件中获取适当优化所需的所有信息...

这些不必要的加载/存储操作不仅解释了为什么 PGO 代码更快，还解释了为什么它增加了缓存未命中的百分比。没有 PGO 寄存器总是溢出到内存中的相同位置，因此这种额外的内存访问会增加内存访问次数和缓存命中次数，同时不会改变缓存未命中次数。使用 PGO，我们有更少的内存访问，但缓存未命中的数量相同，因此它们的百分比增加了。