在配置文件引导的优化之后，嵌套for循环速度更快，但缓存丢失率更高

Question

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

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，它运行得相当快，但是对于进一步的优化，我使用了Cache分析，发现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

gcc 4.8.1在linux下。

配置文件引导的优化与上述命令。g++ -g开关和valgrind --tool=callgrind --simulate-cache=yes ./sscce完成了考勤的工作。

Answer 1

我只注意到在使用或不使用PGO生成的汇编代码之间只有一个显著的差异。如果没有PGO，sum变量将从寄存器溢出到内存，每次内循环迭代一次。从理论上讲，将变量写入内存并将其加载回内存可能会显著降低内存的速度。幸运的是，现代处理器通过存储到负载转发优化了它，这样就不会太慢了。尽管如此，英特尔的优化手册不建议将浮点变量泄漏到内存中，特别是当它们是通过长延迟运算计算时，比如浮点乘法。

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

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