为什么在遍历2D数组时，循环的顺序会影响性能？
可能重复：
这两个循环中的哪一个在时间和缓存性能方面更有效率
下面是两个几乎相同的程序，只是我切换了i和j变量。 他们都跑了不同的时间。 有人能解释为什么发生这种情况
版本1
#include <stdio.h> #include <stdlib.h> main () { int i,j; static int x[4000][4000]; for (i = 0; i < 4000; i++) { for (j = 0; j < 4000; j++) { x[j][i] = i + j; } } }
版本2
#include <stdio.h> #include <stdlib.h> main () { int i,j; static int x[4000][4000]; for (j = 0; j < 4000; j++) { for (i = 0; i < 4000; i++) { x[j][i] = i + j; } } }
正如其他人所说，问题是存储在数组中的内存位置： x[i][j] 。 这里有一些洞察力为什么：
你有一个二维数组，但是计算机中的内存本质上是一维的。 所以，当你想象你的数组是这样的：
0,0 | 0,1 | 0,2 | 0,3 ----+-----+-----+---- 1,0 | 1,1 | 1,2 | 1,3 ----+-----+-----+---- 2,0 | 2,1 | 2,2 | 2,3
您的计算机将其作为一行存储在内存中：
0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3
在第二个例子中，你首先循环访问第二个数字，即：
x[0][0] x[0][1] x[0][2] x[0][3] x[1][0] etc...
意思是你按顺序击中了他们。 现在看第一个版本。 你在做：
x[0][0] x[1][0] x[2][0] x[0][1] x[1][1] etc...
由于C在内存中放置二维数组的方式，你要求它跳过所有的地方。 但现在踢球者：为什么这很重要？ 所有的内存访问都是一样的，对不对？
不，因为缓存。 内存中的数据以小块（称为“缓存行”）的形式传递给CPU，通常为64个字节。 如果你有4个字节的整数，这意味着你在一个整齐的小包中产生16个连续的整数。 取这些内存块实际上是相当慢的， 您的CPU可以在加载单个缓存行的时间内完成很多工作。
现在回头看看访问顺序：第二个例子是（1）抓取16个整数的块，（2）修改所有的块，（3）重复4000×4000/16次。 这很好，而且CPU总是有一些工作。
第一个例子是（1）抓取一个16个整数的块，（2）只修改其中的一个，（3）重复4000×4000次。 这将需要16倍的内存“提取”数量。 你的CPU实际上不得不花费时间等待内存出现，而坐在你周围的是浪费宝贵的时间。
重要的提示：
现在你已经得到了答案，这里有一个有趣的说明：没有固有的理由，你的第二个例子必须是最快的。 例如，在Fortran中，第一个例子很快，第二个例子很慢。 这是因为Fortran没有像C那样将概念扩展到概念“行”，而是扩展成“列”，即：
0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3
C的布局被称为“row-major”，Fortran被称为“column-major”。 正如您所看到的，知道您的编程语言是行大小还是列大小是非常重要的！ 以下是更多信息的链接： http ： //en.wikipedia.org/wiki/Row-major_order
与装配无关。 这是由于缓存未命中 。
C多维数组以最后一个维度存储为最快。 所以第一个版本将会在每次迭代中错过缓存，而第二个版本则不会。 所以第二个版本应该快得多。
另见： http : //en.wikipedia.org/wiki/Loop_interchange 。
版本2将运行得更快，因为它比版本1更好地使用计算机的缓存。如果仔细考虑，阵列只是连续的内存区域。 当你请求一个数组中的元素时，你的操作系统可能会将一个内存页面带入包含该元素的缓存中。 但是，由于接下来的几个元素也在该页面上（因为它们是连续的），下一个访问将已经在缓存中！ 这是版本2正在做的，以加快速度。
另一方面，版本1正在访问元素列明智，而不是明智的。 这种访问在内存级不是连续的，所以程序不能充分利用操作系统缓存。
原因是缓存本地数据访问。 在第二个程序中，您将通过内存进行线性扫描，从缓存和预取中受益。 您的第一个程序的内存使用模式更加分散，因此缓存行为更糟糕。
除了缓存命中的其他优秀答案外，还有一个可能的优化差异。 你的第二个循环很可能被编译器优化成等价的东西：
for (j=0; j<4000; j++) { int *p = x[j]; for (i=0; i<4000; i++) { *p++ = i+j; } }
这在第一个循环中是不太可能的，因为每次需要增加4000指针“p”。
编辑： p++甚至*p++ = ..可以被编译为大多数CPU的单个CPU指令。 *p = ..; p += 4000 *p = ..; p += 4000不能，所以在优化方面没有什么好处。 这也比较困难，因为编译器需要知道和使用内部数组的大小。 而且在正常代码的内部循环中不会出现这种情况（它只出现在多维数组中，最后一个索引在循环中保持不变，而倒数第二个则是步进的），所以优化的优先级低于优先级。
这条线的罪魁祸首：
x[j][i]=i+j;
第二个版本使用连续内存，因此将会大大加快。
我试着用
x[50000][50000];
版本1的执行时间是13秒，而版本2的执行时间是0.6秒。
我试着给出一个通用的答案。
因为i[y][x]是C中的*(i + y*array_width + x)的简写形式（尝试一下经典的int P[3]; 0[P] = 0xBEEF; ）。
在迭代y ，您将遍历大小为array_width * sizeof(array_element) 。 如果你在内部循环中有这个，那么你将在这些块上进行array_width * array_height迭代。
通过翻转顺序，你将只有array_height块迭代，并且在任何块迭代之间，你将只有sizeof(array_element) array_width迭代。
虽然在真正旧的x86-CPU上，这并不重要，现在的x86做了大量的预取和缓存数据。 您可能会在较慢的迭代顺序中产生许多缓存未命中 。
