c++ - 为什么这个 C++ for 循环的执行时间有显着差异？

Question

我正在遍历循环，发现在访问循环方面存在显着差异。 我不明白在这两种情况下导致这种差异的原因是什么？

第一个例子:

执行时间； 8 秒

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];
        }
}

第二个例子:

执行时间:23秒

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

这是内存缓存的问题。

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

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

但是，当我们访问matrix[j][0]时，它与matrix[j - 1][0]相距甚远，可能没有被缓存，并且无法从缓存速度中受益。尤其是矩阵通常存储为连续的大段内存，缓存器可以预测内存访问的行为并始终缓存内存。

这就是 matrix[i][j] 更快的原因。这在基于 CPU 缓存的性能优化中很常见。