c++ - 是否优先访问二维数组的第一维而不是访问第二维？

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，顺序访问模式是否也是首选？

Answer 1

如果你在内存中画出数组的图片，你会更好地理解这一点:

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

你访问的地址会在Y方向线性增长(345, 345+1, 345+2...)，但如果Y很大(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

EDIT2:另请注意，正如 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);
}