在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&nbsp; &nbsp;^2nd assignment[ ][ ][ ][ ][ ] ....^101st assignment第二种方法：[ ][ ][ ][ ][ ] ....^1st assignment&nbsp; &nbsp;^101st assignment[ ][ ][ ][ ][ ] ....^2nd assignment

Answer 2

在您的第二个代码段中j，每次迭代中的更改都会产生一种空间局部性较低的模式。请记住，在幕后，数组引用会计算：( ((y) * (row->width)) + (x) )&nbsp;考虑一个简化的L1缓存，该缓存具有足够的空间来容纳数组的50行。对于前50个迭代，您将为50个缓存未命中付出不可避免的代价，但是接下来会发生什么呢？对于从50到99的每次迭代，您仍将缓存未命中，并且必须从L2（和/或RAM等）获取。然后，x更改为1并重新y开始，导致另一个高速缓存未命中，因为阵列的第一行已从高速缓存中逐出，依此类推。第一个片段没有这个问题。它以行优先的顺序访问数组，从而获得更好的局部性-您仅需为每行最多一次（如果在循环开始时数组中的行不存在于高速缓存中）支付高速缓存未命中的费用。话虽如此，这是一个非常依赖于体系结构的问题，因此您必须考虑细节（L1缓存大小，缓存行大小等）才能得出结论。您还应该同时衡量这两种方式，并跟踪硬件事件，以获取具体的数据以得出结论。