c - 为什么像这样初始化二维数组会更糟​​？

Question

for(int i = 0; i<100; i++)

    for(int j = 0; j<100; j++)

         array[j][i] = 0;
         // array[i][j] = 0;

我的教授说，与第二种方式相比，以第一种方式初始化二维数组的成本要高得多。有人可以解释引擎盖下发生的事情吗？或者，这两种初始化方式是否具有相同的性能？

Answer 1

正如@dlev 提到的，这是由于 locality of reference 并且与计算机中物理硬件的工作方式有关。

在计算机内部，有许多不同类型的内存。通常，只有某些内存位置(寄存器)可以对其执行实际操作；其余时间，如果您对数据执行操作，则必须将其从内存加载到寄存器中，执行一些计算，然后将其写回。

主内存 (RAM) 比寄存器慢得多，通常慢数百到数千倍。因此，应尽可能避免从内存中读取数据。为了解决这个问题，大多数计算机通常都有称为 caches 的特殊内存区域。 .缓存的作用是保存最近从内存中访问过的数据，这样如果再次访问同一内存区域，就可以从缓存中(快)而不是从主内存(慢)中提取值。通常，缓存被设计成如果从内存中读入一个值，则该值以及一大堆相邻值被拉入缓存。这样，如果您遍历一个数组，那么在读取第一个值后，数组中的其余值将位于缓存中并且可以更有效地访问。

您的代码比需要的慢的原因是它没有按顺序访问数组元素。在 C 中，二维数组布局在 row-major order 中。 , 表示内存排列为

A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ...

因此，如果你使用这个 for 循环:

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        // Do something with A[i][j]
    }
}

然后您将获得出色的局部性，因为您将按照数组元素在内存中出现的顺序访问数组元素。这使得主内存的读取次数非常少，因为所有内容通常都在缓存中并准备就绪。

但是，如果像您所做的那样交换循环，您的访问将在内存中跳跃，并且不一定是连续的。这意味着您将有很多缓存未命中，其中您接下来读取的内存地址不在缓存中。这会增加缓存加载的次数，从而显着降低程序速度。

编译器开始变得足够聪明，可以自动交换这样的循环，但我们距离能够忽略这些细节还有很长的路要走。作为一般规则，在为多维数组编写 C 或 C++ 代码时，请尝试以行优先顺序而不是列优先顺序进行迭代。您可以在程序中获得明显的加速。

希望这对您有所帮助!