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

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所提到的,这是由于引用的位置,并且与计算机中的物理硬件如何工作有关.

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

主存储器(RAM)比寄存器慢很多,通常是数百到数千.因此,如果可能的话,应该避免从记忆中读取.为解决这个问题,大多数计算机通常都有称为高速缓存的特殊内存区域.高速缓存的作用是保存最近从存储器访问的数据,这样如果再次访问相同的存储区域,则可以从高速缓存(快速)而不是从主存储器(慢速)中提取该值.通常,设计高速缓存使得如果从存储器读入值,则将该值加上一大堆相邻值拉入高速缓存.这样,如果迭代一个数组,那么在读取第一个值之后,数组中的其余值将位于缓存中,并且可以更有效地访问.

您的代码比它需要的慢的原因是它不会按顺序访问数组元素.在C中,2D数组按行主要顺序排列,这意味着存储器排列为

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++代码时,请尝试以行主顺序而不是列主顺序进行迭代.您可以在程序中获得明显的加速.

希望这可以帮助!