在二维数组上缓存不友好的循环比缓存友好的循环更快

Question

为什么使用 MSVC++ 编译时版本 1 比版本 2 快？

版本 1：

for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
        for (int k = 0; k < N; ++k)
            res1[i][j] += mat1[i][k] * mat2[k][j];

版本 2：

for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
        for (int k = 0; k < N; ++k)
            res1[i][j] += mat1[i][k] * mat2[j][k];

(N=1000; res1,mat1,mat2 是double[N][N]数组)

版本 2 不应该更快，因为在循环中使用 [j][k] 对 mat2 进行索引是缓存友好的（当将 mat2[j][k] 从 ram 加载到缓存 mat2[j][k 时+1], mat2[j][k+2],... 也将被加载，因为它们在同一条缓存线上))?

（如果我关闭编译器优化（使用："#pragma optimize( "", off )"）版本 2 比版本 1 快，但代码运行速度慢很多（显然））。

编辑：

性能：（使用 windows.h ==> QueryPerformanceCounter 测量的时间）

使用编译器优化：版本 1：~493 毫秒；版本 2：954 毫秒没有编译器优化：版本 1：~3868 毫秒；版本 2：~2266 毫秒

Answer 1

使用优化，对于第一个版本，编译器显然可以将内部两个循环重新排序为：

for (int i = 0; i < N; ++i)
    for (int k = 0; k < N; ++k)
        for (int j = 0; j < N; ++j)
            res1[i][j] += mat1[i][k] * mat2[k][j];

这将使第一个版本在缓存感知方面与第二个版本相似。

第一个版本快两倍的原因，可能是它的第二个术语的缓存：mat1[i][k]因为它在进行上述优化后，在内循环中没有改变。

Cache unfriendly loop over 2d-array faster than cache friendly loop