在配置文件引导优化之后嵌套for循环更快但具有更高的缓存未命中

Question

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

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

并且有一个简单的双循环进行,有点像这样:

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%,考虑到计算的随机性,这是很多但不太令人惊讶.所以我做了一个配置文件引导优化a 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每次内部循环迭代时，变量都会从寄存器溢出到内存中。从理论上讲，将变量写入内存并将其加载回来可能会大大减慢速度。幸运的是，现代处理器通过存储到加载转发对其进行了优化，因此速度减慢并没有那么大。英特尔的优化手册仍然不建议将浮点变量溢出到内存中，特别是当它们是通过长延迟操作（例如浮点乘法）计算时。

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

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