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

Question

可能重复:
为什么我的程序在完全循环8192个元素时会变慢？

我一直在修补一个程序,我用它来简单地总结一个二维数组的元素.一个错字导致了至少在我看来,一些非常奇怪的结果.

处理数组时,矩阵[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]

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

Answer 1

这是由于程序的缓存行为.

数组只是连续的内存块,因此当您访问[row] [column]时,您将按顺序访问内存.这意味着您访问的数据页面位于同一页面上,因此访问速度更快.

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

Answer 2

内存位置matrix[row][col]和matrix[row][col + 1]相邻.

内存位置matrix[row][col]和matrix[row + 1][col]SIZE项目的数量分开.

像访问内存的计算机顺序地不RANDOMLY,从而在相邻的访问更快.对于类比思考硬盘性能,顺序读/写总是优于随机读/写.这与您的CPU如何缓存内存并尝试预测接下来需要的内容有关.