在迭代2D数组时，为什么循环的顺序会影响性能？-Java 学习之路

314

可能重复：这两个for循环中的哪一个在时间和缓存性能方面更有效

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

7 回答

541
正如其他人所说，问题是存储到数组中的内存位置： 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在内存中布置2-d数组的方式，你要求它在整个地方跳跃 . 但现在对于踢球者：为什么这很重要？所有内存访问都是一样的，对吧？

不：因为缓存 . 来自内存的数据以小块（称为“缓存行”）传递给CPU，通常为64字节 . 如果你有4字节的整数，那意味着你要在一个整齐的小包中找到16个连续的整数 . 获取这些内存块实际上相当慢;您的CPU可以在加载单个缓存行所需的时间内完成大量工作 .

现在回顾一下访问顺序：第二个例子是（1）抓取一个16个整数的块，（2）修改所有这些，（3）重复4000 * 4000/16次 . 这很好用而且速度很快，而且CPU总是有一些工作要做 .

第一个例子是（1）抓取一个16个整数的块，（2）只修改其中一个，（3）重复4000 * 4000次 . 这将需要16倍于内存中“提取”的数量 . 你的CPU实际上必须花时间坐在那里等待记忆显示出来，而当它坐在你周围时你会浪费宝贵的时间 .

Important Note:

既然你有了答案，这里有一个有趣的说明：你的第二个例子必须是快速的，没有固有的原因 . 例如，在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的布局称为'row-major'和Fortran 's is called ' column-major '. As you can see, it'非常重要，以了解您的编程语言是行主要还是列主要！这是一个更多信息的链接：http://en.wikipedia.org/wiki/Row-major_order
回复于 2024-04-29T11:15:35+08:00
22

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

回复于 2024-04-29T11:15:35+08:00
62

与装配无关 . 这是由于cache misses .

存储C多维数组，最后一个维度最快 . 因此第一个版本将在每次迭代时错过缓存，而第二个版本则不会 . 所以第二个版本应该快得多 .

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

回复于 2024-04-29T11:15:35+08:00
12

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

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

回复于 2024-04-29T11:15:35+08:00
3
除了缓存命中的其他优秀答案之外，还存在可能的优化差异 . 您的第二个循环很可能由编译器优化为等效于：
```
for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }
```
这对于第一个循环不太可能，因为它需要每次增加指针“p”4000 .

EDIT: p++ 甚至 *p++ = .. 可以在大多数CPU中编译为单个CPU指令 . *p = ..; p += 4000 不能，因此优化它的好处较少 . 它也更难，因为编译器需要知道并使用内部数组的大小 . 并且通常在正常代码的内部循环中不会发生（它仅出现在多维数组中，其中最后一个索引在循环中保持不变，而倒数第二个索引是步进的），因此优化不是优先级 .
回复于 2024-04-29T11:15:35+08:00
8

我试着给出一个通用的答案 .

因为 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 块迭代，并且在任何块迭代之间，您将只有 array_width 迭代，只有 sizeof(array_element) .

虽然在真正老的x86-CPU上这并不重要，但现在'x86做了很多预取和数据缓存 . 您可能在较慢的迭代顺序中生成许多cache misses .

回复于 2024-04-29T11:15:35+08:00
10
这条线的罪魁祸首：
```
x[j][i]=i+j;
```
第二个版本使用连续存储器因此将大大加快 .

我试过了
```
x[50000][50000];
```
版本1的执行时间为13秒，版本2的执行时间为0.6秒 .
回复于 2024-04-29T11:15:35+08:00

在迭代2D数组时，为什么循环的顺序会影响性能？

7 回答

相关问题