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

Question

可能重复:
这两个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; }
   }
}

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在内存中布置2-d数组的方式,你要求它在整个地方跳跃.但现在对于踢球者:为什么这很重要？所有内存访问都是一样的,对吧？

不:因为缓存.来自内存的数据以小块(称为"缓存行")传递给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的布局称为'row-major',Fortran称为'column-major'.正如您所看到的,了解您的编程语言是行主要还是列专业是非常重要的!以下是更多信息的链接:http://en.wikipedia.org/wiki/Row-major_order

Answer 2

与装配无关.这是由于缓存未命中.

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

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

Answer 3

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

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

Answer 4

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

Answer 5

除了缓存命中的其他优秀答案之外,还存在可能的优化差异.您的第二个循环很可能由编译器优化为等效于:

  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不能,所以优化它的好处就少了.它也更难,因为编译器需要知道并使用内部数组的大小.并且通常在正常代码的内部循环中不会发生(它仅出现在多维数组中,其中最后一个索引在循环中保持不变,而倒数第二个索引是步进的),因此优化不是优先级.

Answer 6

这条线的罪魁祸首:

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

第二个版本使用连续存储器因此将大大加快.

我试过了

x[50000][50000];

版本1的执行时间为13秒,版本2的执行时间为0.6秒.