在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; }
}
}
56199 次浏览
小开

与组装无关。这是由于缓存错过。

C多维数组以最后一个维度作为最快维度进行存储。因此，第一个版本在每次迭代时都会错过缓存，而第二个版本则不会。因此，第二个版本应该要快得多。

参见:http://en.wikipedia.org/wiki/Loop_interchange。

小开

版本2运行得更快，因为它比版本1更好地利用了计算机的缓存。仔细想想，数组只是内存中连续的区域。当你请求数组中的一个元素时，你的操作系统可能会在缓存中引入一个包含该元素的内存页。然而，由于接下来的几个元素也在该页上(因为它们是连续的)，下一次访问将已经在缓存中!这就是版本2为提高速度所做的工作。

另一方面，版本1是按列访问元素，而不是按行。这种访问在内存级别上不是连续的，因此程序不能充分利用操作系统缓存。

小开

原因是缓存本地数据访问。在第二个程序中，您将线性扫描内存，这得益于缓存和预取。您的第一个程序的内存使用模式更加分散，因此具有更糟糕的缓存行为。

小开

这句话是罪魁祸首:

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元。

在大多数CPU中，编辑: p++甚至*p++ = ..都可以编译为一条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做了大量的预取和缓存数据。你可能会在较慢的迭代顺序中产生许多缓存错过。


提交答案