是否首先访问第一个维度而不是访问二维数组的第二个维度？

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),则会在X方向上大幅跳跃.当缓存加载内存块时,如果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);
}