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

小编典典

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

all

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

阅读 107

2022-03-23

共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 个整数的块，（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

2022-03-23