在2D数组上进行迭代时，嵌套循环的哪种排序更为有效

Question

在时间（缓存性能）方面，以下哪种嵌套循环在2D数组上进行迭代更有效？为什么？int a[100][100];for(i=0; i<100; i++){   for(j=0; j<100; j++)   {       a[i][j] = 10;       }}要么for(i=0; i<100; i++){   for(j=0; j<100; j++)   {      a[j][i] = 10;       }}

Answer 1

第一种方法稍好一些，因为分配给的像元彼此相邻放置。

第一种方法：

[ ][ ][ ][ ][ ] ....

^1st assignment

   ^2nd assignment

[ ][ ][ ][ ][ ] ....

^101st assignment

第二种方法：

[ ][ ][ ][ ][ ] ....

^1st assignment

   ^101st assignment

[ ][ ][ ][ ][ ] ....

^2nd assignment

Answer 2

在您的第二个代码段中j，每次迭代中的更改都会产生一种空间局部性较低的模式。请记住，在幕后，数组引用会计算：

( ((y) * (row->width)) + (x) ) 

考虑一个简化的L1缓存，该缓存具有足够的空间来容纳数组的50行。对于前50个迭代，您将为50个缓存未命中付出不可避免的代价，但是接下来会发生什么呢？对于从50到99的每次迭代，您仍将缓存未命中，并且必须从L2（和/或RAM等）获取。然后，x更改为1并重新y开始，导致另一个高速缓存未命中，因为阵列的第一行已从高速缓存中逐出，依此类推。

第一个片段没有这个问题。它以行优先的顺序访问数组，从而获得更好的局部性-您仅需为每行最多一次（如果在循环开始时数组中的行不存在于高速缓存中）支付高速缓存未命中的费用。

话虽如此，这是一个非常依赖于体系结构的问题，因此您必须考虑细节（L1缓存大小，缓存行大小等）才能得出结论。您还应该同时衡量这两种方式，并跟踪硬件事件，以获取具体的数据以得出结论。