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