下面是两个几乎完全相同的程序，只是我把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[j][i]=i+j;
第二个版本使用连续内存，因此速度会快得多。
我试过
x[50000][50000];
版本1的执行时间是13秒，而版本2的执行时间是0.6秒。
正如其他人所说，问题是存储到数组中的内存位置: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
在第二个例子中，你通过循环第2个数字来访问数组，即:
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语言的布局被称为“行-主布局”，Fortran的布局被称为“列-主布局”。正如您所看到的，知道您的编程语言是行为主还是列为主是非常重要的!这里有更多信息的链接:http://en.wikipedia.org/wiki/Row-major_order
除了缓存命中的其他优秀答案之外，还有一个可能的优化差异。你的第二个循环很可能被编译器优化成类似于:
for (j=0; j<4000; j++) {
int *p = x[j];
for (i=0; i<4000; i++) {
*p++ = i+j;
}
}
对于第一个循环，这种情况不太可能发生，因为它每次都需要将指针“p”增加4000。
编辑:p++和*p++ = ..可以在大多数CPU中编译为单个CPU指令。*p = .;P += 4000不能，所以优化它的好处较少。这也比较困难，因为编译器需要知道和使用内部数组的大小。在普通代码的内部循环中并不经常出现这种情况(它只发生在多维数组中，其中最后一个索引在循环中保持不变，倒数第二个索引是阶梯式的)，因此优化的优先级不那么高。
我试着给出一个一般的答案。
因为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做了大量的预取和缓存数据。在较慢的迭代顺序中，可能会产生许多缓存丢失。
原因是缓存本地数据访问。在第二个程序中，您将线性扫描内存，这得益于缓存和预取。您的第一个程序的内存使用模式更加分散，因此具有更糟糕的缓存行为。
