395

下面是两个几乎相同的程序，只是我切换了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; }
   }
}
4

7 回答 7

628

正如其他人所说，问题是存储到数组中的内存位置：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 的布局称为“行优先”，而 Fortran 的布局称为“列优先”。如您所见，了解您的编程语言是行优先还是列优先非常重要！以下是更多信息的链接：http ://en.wikipedia.org/wiki/Row-major_order

于 2012-03-30T03:32:13.220 回答
71

与组装无关。这是由于缓存未命中。

C 多维数组以最后一维为最快的存储。所以第一个版本在每次迭代时都会错过缓存，而第二个版本不会。所以第二个版本应该快得多。

另见：http ://en.wikipedia.org/wiki/Loop_interchange 。

于 2012-03-30T02:20:03.313 回答
24

版本 2 将运行得更快，因为它比版本 1 更好地使用计算机的缓存。如果您考虑一下，数组只是内存的连续区域。当您请求数组中的元素时，您的操作系统可能会将内存页面引入包含该元素的缓存中。但是，由于接下来的几个元素也在该页面上（因为它们是连续的），下一次访问将已经在缓存中！这就是第 2 版为加快速度所做的工作。

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

于 2012-03-30T02:21:45.470 回答
12

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

于 2012-03-30T02:22:38.747 回答
11

除了缓存命中的其他出色答案外，还存在可能的优化差异。您的第二个循环可能会被编译器优化为相当于：

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不能，因此优化它的好处较少。这也更加困难，因为编译器需要知道并使用内部数组的大小。并且在普通代码的内部循环中不会经常发生（它仅发生在多维数组中，其中最后一个索引在循环中保持不变，倒数第二个是步进的），因此优化不是优先级.

于 2012-03-30T11:28:36.500 回答
9

这条线是罪魁祸首：

x[j][i]=i+j;

第二个版本使用连续内存，因此速度会快很多。

我试过了

x[50000][50000];

版本 1 的执行时间为 13 秒，而版本 2 的执行时间为 0.6 秒。

于 2012-03-30T02:29:24.653 回答
4

我试图给出一个通用的答案。

因为i[y][x]是 C 中的简写*(i + y*array_width + x)（试试 classy int P[3]; 0[P] = 0xBEEF;）。

当您迭代时y，您会迭代大小的块array_width * sizeof(array_element)。如果您的内部循环中有它，那么您将对array_width * array_height这些块进行迭代。

通过翻转顺序，您将只有array_height块迭代，并且在任何块迭代之间，您将array_width只有sizeof(array_element).

虽然在真正旧的 x86-CPU 上这无关紧要，但如今的 x86 做了很多数据的预取和缓存。您可能会以较慢的迭代顺序产生许多缓存未命中。

于 2012-03-30T15:20:15.313 回答