用于迭代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

1. 对于数组[100] [100] - 它们都是相同的,如果L1高速缓存大于100*100*sizeof(int)== 10000*sizeof(int)== [通常] 40000.注意在Sandy Bridge中 - 100*100整数应该是足够的元素来看到差异,因为L1缓存只有32k.

2. 编译器可能会优化此代码

3. 假设没有编译器优化,并且矩阵不适合L1缓存 - 由于缓存性能[通常],第一个代码更好.每次在缓存中找不到元素时 - 都会出现缓存未命中 - 并且需要转到RAM或L2缓存[速度慢得多].从RAM到缓存[缓存填充]的元素是以块[通常是8/16字节]完成的 - 所以在第一个代码中,你得到的最多错过率是1/4[假设16字节缓存块,4字节整数]而在第二个代码中代码它是无界的,甚至可以是1.在第二个代码快照中 - 已经在缓存中的元素[插入到相邻元素的缓存填充中] - 被取出,并且您获得了冗余缓存未命中.

   • 这与局部性原理密切相关,局部性原理是实现缓存系统时使用的一般假设.第一个代码遵循这个原则,而第二个代码没有 - 因此第一个代码的缓存性能将优于第二个代码.

结论: 对于我所知道的所有缓存实现 - 第一个将不会比第二个更糟糕.它们可能是相同的 - 如果根本没有缓存或者所有数组完全适合缓存 - 或者由于编译器优化.

Answer 3

这种微优化与平台有关,因此您需要对代码进行分析,以便能够得出合理的结论.

Answer 4

在您的第二个片段中j,每次迭代中的更改都会生成一个空间局部性较低的模式.请记住,在幕后,数组引用计算:

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

考虑一个简化的L1缓存,它只有50行我们的数组有足够的空间.对于前50次迭代,您将支付50次缓存未命中的不可避免的成本,但接下来会发生什么？对于从50到99的每次迭代,您仍将缓存未命中并且必须从L2(和/或RAM等)获取.然后,x更改为1并重新y开始,导致另一个缓存未命中,因为阵列的第一行已从缓存中逐出,依此类推.

第一个片段没有这个问题.它以行主要顺序访问数组,从而实现更好的局部性 - 每行最多只需支付一次缓存未命中(如果在循环开始时缓存中没有数组的行).

话虽如此,这是一个非常依赖于架构的问题,因此您必须考虑具体情况(L1缓存大小,缓存行大小等)来得出结论.您还应该测量两种方式并跟踪硬件事件,以获得具体数据以得出结论.

Answer 5

考虑到C ++是行专业的，我相信第一种方法会更快一些。在内存中，二维数组以单维数组表示，并且性能取决于使用行主列或列主列对其进行访问