c++ - c++ 2d数组访问速度根据[a][b]顺序变化？

Question

可能重复：
为什么我的程序在恰好循环 8192 个元素时很慢？

我一直在修改我用来简单地对二维数组的元素求和的程序。一个错字导致了至少在我看来，一些非常奇怪的结果。

处理数组时，matrix[SIZE][SIZE]：

for(int row = 0; row < SIZE; ++row)
    for(int col = 0; col < SIZE; ++col)
        sum1 += matrix[row][col];

运行非常快，但是上面的行 sum1... 被修改：

sum2 += matrix[col][row]

正如我在没有意识到的情况下偶然发生的那样，我注意到我的运行时间显着增加。为什么是这样？

score 15 · Accepted Answer

这是由于您的程序的缓存行为。

数组只是连续的内存块，因此当您访问 [row][column] 时，您正在按顺序访问内存。这意味着您正在访问的数据页面在同一页面上，因此访问速度要快得多。

当您执行 [column][row] 时，您不再按顺序访问该内存，因此您最终会遇到更多缓存未命中，因此您的程序运行速度会慢得多。

score 5 · Accepted Answer

matrix[row][col]和的内存位置matrix[row][col + 1]是相邻的。

matrix[row][col]和的内存位置matrix[row + 1][col]由项目的 SIZE 数量分隔。

计算机喜欢按顺序访问内存而不是随机访问，因此相邻访问速度更快。打个比方想想硬盘的性能，顺序读/写总是比随机读/写好。这与您的 CPU 如何缓存内存并尝试预测您接下来需要什么有关。

score 3 · Accepted Answer

这是因为在更快的情况下，当您以线性方式迭代时，CPU 的内存预取实际上很有用。在缓慢的情况下，您在内存中跳跃，因此预取几乎没有影响，因为数据不太可能在缓存中。

score 3 · Accepted Answer

这取决于矩阵的排序方式。您正在以行优先或列优先访问数组。取决于它在内存中的存储方式，两者之间的速度会有所不同

score -5 · Accepted Answer

二维数组只是指向指针的指针。所以它看起来像

[*p][*p][*p]
  |   |   |
  v   v   v
 [d] [d] [d]
 |a| |a| |a|
 |t| |t| |t|
 [a] [a] [a]

因此，当您在非主阵列上调用数据（此指针指示的内容）时，您的操作系统会将其放入 CPU 缓存。

5 回答 5