下面是两个几乎完全相同的程序，只是我把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秒。
其他回答
与组装无关。这是由于缓存丢失。
C多维数组以最后一个维度作为最快维度进行存储。因此，第一个版本在每次迭代时都会错过缓存，而第二个版本则不会。因此，第二个版本应该要快得多。
参见:http://en.wikipedia.org/wiki/Loop_interchange。
除了缓存命中的其他优秀答案之外，还有一个可能的优化差异。你的第二个循环很可能被编译器优化成类似于:
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做了大量的预取和缓存数据。在较慢的迭代顺序中，可能会产生许多缓存丢失。
版本2运行得更快，因为它比版本1更好地利用了计算机的缓存。仔细想想，数组只是内存中连续的区域。当你请求数组中的一个元素时，你的操作系统可能会在缓存中引入一个包含该元素的内存页。然而，由于接下来的几个元素也在该页上(因为它们是连续的)，下一次访问将已经在缓存中!这就是版本2为提高速度所做的工作。
另一方面，版本1是按列访问元素，而不是按行。这种访问在内存级别上不是连续的，因此程序不能充分利用操作系统缓存。
原因是缓存本地数据访问。在第二个程序中，您将线性扫描内存，这得益于缓存和预取。您的第一个程序的内存使用模式更加分散，因此具有更糟糕的缓存行为。
