访问二维数组时，首先访问第一维比访问第二维更优吗？

Question

以下是代码：

int array[X][Y] = {0,};

// 1 way to access the data
for (int x = 0; x < X; x++)
  for(int y = 0; y < Y; y++)
    array[x][y] = compute();

// the other way to access the data
for (int y = 0; y < Y; y++)
  for (int x = 0; x < X; x++)
    array[x][y] = compute();

第一种方式是否比第二种更高效，因为 CPU 缓存（L1、L2？）优化？换句话说，即使是在 RAM 中，连续访问模式也更受欢迎吗？

- Thomson

---

在担心这种微观优化之前，测量是必要的建议 - 仍然是一个有趣的问题。 - Nick Van Brunt

@Nick：在这种情况下，我认为可以非常肯定地说，从性能上来看它确实有所不同。一般来说，遍历二维数组的成本相当高，而错误的方法很容易使执行时间翻倍。 - jalf

你为什么把x作为第一维度？我会用y。 - fredoverflow

Answer 1

如果你在内存中画出数组的图像，你会更好地理解这个问题：

  Y ->
X xxxxx ...
| xxxxx
v xxxxx
  .
  .

您所访问的地址在Y方向上呈线性增长（345、345+1、345+2...），但如果Y很大，则在X方向上跳跃非常剧烈（345、345+X、345+X*2）。由于缓存加载内存块，当Y足够大时，您将很快跳出它们，但在沿Y方向行走时始终会在缓存页面中，直到必须刷新缓存为止。此外，请注意，在使用动态分配时，这种效果可能更加极端。使用完全优化的以下程序给我以下输出（以秒为单位的时间）。

0.615000
9.878000

编辑：其他有趣的措施：

将数组代码替换为int array[X][Y];将使用栈内存，其受限制，因此您无法测试更大的X/Y值，但速度也非常快:

0.000000
0.000000

将 int array[X][Y]; 作为全局变量使用会使用一块堆内存，并且速度较慢。因此，即使没有动态分配，第一种情况仍然要好得多：

0.929000
8.944000

使用 X=1500，Y=1500 可以显示即使使用较小的数组也可以测量效果：

0.008000
0.059000

编辑2：还要注意，正如jalf在你的问题评论中所说，代码还有其他可能的优化。使用这种优化确实将速度几乎提高了一倍（X=Y=10000时为0.453秒）：

// an even faster way to access the array
for (int x = 0; x < X; x++) {
  int* arrayptr = array[x];
  for (int y = 0; y < Y; y++, arrayptr++)
    *arrayptr = x;
}

代码：（请注意，您也可以使用此方法来测量差异情况，除了大X和Y的情况外，差异不应该那么明显。正如其他人已经说过的，测量这个值将使您受益匪浅）。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define X 10000
#define Y 10000

int main() {

  int** array = new int*[X];

  for (int x = 0; x < X; x++) {
    array[x] = new int[Y];
  }

  double c = clock();  

  // 1 way to access the data
  for (int x = 0; x < X; x++)
    for(int y = 0; y < Y; y++)
      array[x][y] = x;

  printf("%f\n", (clock() - c) / CLOCKS_PER_SEC);

  c = clock();  

  // the other way to access the data
  for (int y = 0; y < Y; y++)
    for (int x = 0; x < X; x++)
      array[x][y] = x;

  printf("%f\n", (clock() - c) / CLOCKS_PER_SEC);

  for (int x = 0; x < X; x++) {
    delete(array[x]);
  }
  delete(array);
}

- schnaader

---

即使数组不是“非常大”，你也会注意到差异。除非整个数组适合单个高速缓存行，否则如果按列遍历它，你将得到所有位置的高速缓存未命中。 - jalf

@jalf：你说得对，我用小值进行了测量并进行了更正。 - schnaader

Answer 2

是的。特别是当行适合缓存行时。如果您使用第二种方法，并且您的数组中有足够大的行，则没有缓存局部性，缓存行将不断被抛弃。

- Jeff Mercado

Answer 3

是的，第一个更快。在内存矩阵中，一行接着一行存储（行主序），因此相邻元素在虚拟内存中处于同一页的概率更大（整个页面被缓存，因此访问时间更短）。

对于较大的矩阵，另一种方法将生成更多的缓存未命中。

- Klark

---

缓存不包含整个页面，它包含的缓存行比页面要小得多。单个缓存行的范围从几个字节到几百个字节不等。一个页面至少有几千字节。尽管术语上有些错误，但在高性能代码中，访问模式确实很重要。问题仍然是：X和Y有多大，实际基准测试的结果是什么 :)。 - Pieter

@Pieter，X和Y都可能非常大，特别是Y。 - Thomson

Answer 4

测量它。

顺序访问是首选的。应该在很大程度上取决于X和Y的值。对于某些X和Y的选择，我预计差异会相当大。

您应该考虑使用类似于vector、valarray或boost::matrix的容器。C风格的数组可能会导致可避免和烦人的错误。

- Gabriel Schreiber

Answer 5

一个著名的表达式：“由于现代计算机的速度，这可能不会产生明显的差异。”

- Alexander Rafferty

---

缓存未命中可能会带来巨大影响，尤其是在现代电脑中，CPU速度远远超过了RAM速度。 - Ferruccio