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

for(int i = 0; i<100; i++) for(int j = 0; j<100; j++) array[j][i] = 0; // array[i][j] = 0; 

我的教授说,第一种方式初始化二维数组要比第二种方式要昂贵得多。 有人可以解释引擎盖下面发生了什么事情吗? 或者,这两种初始化方法是否具有相同的性能?

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

希望这可以帮助!

我可能会因此而被投票,但如果你正在编程C,那么“最佳”最有可能:

memset(array,0,sizeof(array));

然后,您可以将优化(您显然担心)的所有责任推迟到memset的实现。 可以在那里完成任何特定的硬件优势。

http://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/

http://www.cplusplus.com/reference/clibrary/cstring/memset/

另一个观察是,如果你是初始零,问问自己为什么? 如果你的数组是静态的(对于这个大的数组可能是?),那么cstartup会为你初始化为零。 同样,这可能会使用最有效的硬件方式。

我参加派对有点晚了,而且已经有了很好的答案。 但是,我想我可以通过演示如何使用分析工具(在Linux上)实验性地回答这个问题来做出贡献。

我将在Ubuntu 10.10软件包linux-tools-common使用perf工具。

这是我写的回答这个问题的小C程序:

 // test.c #define DIM 1024 int main() { int v[DIM][DIM]; unsigned i, j; for (i = 0; i < DIM; i++) { for (j = 0; j < DIM; j++) { #ifdef ROW_MAJOR_ORDER v[i][j] = 0; #else v[j][i] = 0; #endif } } return 0; } 

然后编译两个不同的版本:

 $ gcc test.c -O0 -DROW_MAJOR_ORDER -o row-maj $ gcc test.c -O0 -o row-min 

注意我已经使用-O0禁用了优化,因此gcc没有机会重新排列循环以提高效率。

我们可以通过执行perf list perf可用的性能统计信息。 在这种情况下,我们对缓存未命中感兴趣,这是事件cache-misses

现在它就像运行程序的每个版本一样简单并且取平均值:

 $ perf stat -e cache-misses -r 100 ./row-min Performance counter stats for './row-min' (100 runs): 286468 cache-misses ( +- 0.810% ) 0.016588860 seconds time elapsed ( +- 0.926% ) $ perf stat -e cache-misses -r 100 ./row-maj Performance counter stats for './row-maj' (100 runs): 9594 cache-misses ( +- 1.203% ) 0.006791615 seconds time elapsed ( +- 0.840% ) 

现在,我们已经通过实验validation您确实看到“行 - 次要”版本有两个数量级的缓存未命中。

如果查看每种技术访问的内存位置,第二种将访问连续的字节,而第一种将跳过100字节的跳跃。 如果以第二种方式执行,内存缓存将更有效地工作。