c - 为什么循环顺序会影响二维数组迭代时的性能？

Question

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

Answer 1

正如其他人所说，问题在于数组中内存位置的存储: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 个整数的 block ，(2)修改所有这些，(3)重复 4000*4000/16 次。这很好，而且速度很快，而且 CPU 总是有工作要做。

第一个示例是 (1) 抓取 16 个整数的 block ，(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