为什么这个C++for循环的执行时间有很大的不同？[副本]

Question

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[i][j];
        }
}

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[j][i];
        }
}

matrix[i][j] 

到

matrix[j][i]

？

Answer 1

这是内存缓存的问题。

矩阵[i][j]比矩阵[j][i]具有更好的缓存命中，因为矩阵[i][j]具有更多的连续内存访问机会。

例如，当我们访问矩阵[i][0]时，缓存可能会加载包含矩阵[i][0]的连续内存段，因此，访问矩阵[i][1]、矩阵[i][2]、...，将从缓存速度中受益，因为矩阵[i][1]、矩阵[i][2]、...，接近于矩阵[i][0]。