在2d数组上的缓存不友好循环比缓存友好循环快

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是双[N][N]数组)

版本2不应该更快，因为在循环中索引mat2[j][k]是缓存友好的(当从ram将mat2[j][k]加载到缓存mat2[j][k+1]， mat2[j][k+2]，…也会被加载，因为它们在相同的缓存线上))?

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

编辑:

性能:(使用windows.h ==> QueryPerformanceCounter测量的时间)

与编译器优化:版本1:~493毫秒;版本2:954毫秒未经编译器优化:Version1: ~3868 ms;版本2:~2266 ms

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]，因为它在做了上面的优化之后，在内部循环中没有改变。