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

#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; }
  }
}

#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; }
   }
}

#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

由于C在内存中布置二维数组的方式，您要求它跳转到整个位置。但是，现在开始讨论：为什么这很重要？所有内存访问都是相同的，对吗？

否：由于缓存。来自内存的数据会以小块（称为“缓存行”）的形式带入CPU，通常为64个字节。如果您有4字节的整数，这意味着您将在一个整齐的小束中获得16个连续的整数。获取这些内存块实际上相当慢。您的CPU可以在加载单个高速缓存行的时间上完成很多工作。整数，（2）修改所有整数，（3）重复4000 * 4000/16次。这样既好又快，并且CPU总是有工作要做。

第一个示例是（1）抓取16个int块，（2）仅修改其中一个，（3）重复4000 * 4000次这将需要从内存中“获取”次数的16倍。实际上，您的CPU必须花时间等待内存显示，而浪费时间却是宝贵的时间。

重要说明：

现在您有了答案，这里有个有趣的注释：没有第二个例子必须是快速的例子的内在原因。例如，在Fortran中，第一个示例将很快，而第二个示例将很慢。这是因为Fortran并未像C那样将其扩展为概念上的“行”，而是将其扩展为“列”，即：

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

-major”，而Fortran称为“ column-major”。如您所见，了解您的编程语言是行优先还是列优先非常重要！这是更多信息的链接：http://en.wikipedia.org/wiki/Row-major_order

#2 楼

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

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

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

#3 楼

版本2的运行速度要快得多，因为它比版本1更好地使用了计算机的缓存。如果您考虑一下，数组就是连续的内存区域。当您请求数组中的元素时，您的操作系统可能会将内存页面带入包含该元素的缓存中。但是，由于接下来的几个元素也在该页面上（因为它们是连续的），因此下一次访问将已经在缓存中！这是版本2为加快速度所做的工作。另一方面，版本1是按列访问元素，而不是按行访问元素。这种访问在内存级别不是连续的，因此程序无法充分利用OS缓存。

#4 楼

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

#5 楼

除了有关缓存命中的其他出色答案外，还有可能存在优化差异。您的第二个循环很可能会被编译器优化为等效于以下内容的代码：
“ p”每次具有4000。 p++不能，因此对其进行优化的好处较小。这也更加困难，因为编译器需要知道和使用内部数组的大小。而且，这种情况不会在普通代码的内部循环中发生（仅发生在多维数组中，在该数组中，最后一个索引在循环中保持不变，而倒数第二个是步进的），因此优化的优先级较低。

#6 楼

这是罪魁祸首：

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

第二个版本使用连续内存，因此会更快。

我尝试了

x[50000][50000];

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

#7 楼

我尝试给出一个通用的答案。因为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)迭代。您可能会以较慢的迭代顺序产生许多缓存未命中。