72

在时间（缓存性能）方面，以下哪种嵌套循环的顺序迭代二维数组更有效？为什么？

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;    
   }
}
4

10 回答 10

64

第一种方法稍微好一些，因为分配给的单元格彼此相邻。

第一种方法：

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment

第二种方法：

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment
于 2012-03-27T10:56:47.993 回答
44

  1. 对于 array[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 字节] 的形式完成 - 因此在第一个代码中，您最多会获得 [假设 16 字节缓存块，4 字节整数] 的未命中率，1/4而在第二个代码中代码它是无界的，甚至可以是 1。在第二个代码快照中 - 已经在缓存中的元素 [插入到相邻元素的缓存填充中] - 被取出，你会得到一个冗余的缓存未命中。

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

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

于 2012-03-27T10:58:42.790 回答
13

这种微优化取决于平台，因此您需要分析代码才能得出合理的结论。

于 2012-03-27T10:57:44.863 回答
10

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

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

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

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

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

于 2012-03-27T11:12:03.773 回答
6

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

于 2012-03-27T11:01:14.537 回答
4

这是一个经典的问题cache line bouncing

在大多数情况下，第一个更好，但我认为确切的答案是：它取决于，不同的架构可能不同的结果。

于 2012-03-27T11:22:01.080 回答
4

在第二种方法中，缓存未命中，因为缓存存储的是连续数据。 因此第一种方法比第二种方法有效。

于 2012-03-30T05:45:36.947 回答
3

在您的情况下（填充所有数组 1 值），这会更快：

   for(j = 0; j < 100 * 100; j++){
      a[j] = 10;
   }

你仍然可以将a其视为二维数组。

编辑：正如 Binyamin Sharet 提到的，如果你a是这样声明的，你可以这样做：

int **a = new int*[100];
for(int i = 0; i < 100; i++){
    a[i] = new int[100];
}
于 2012-03-27T10:54:18.883 回答
2

一般来说，更好的局部性（大多数响应者都注意到）只是循环 #1 性能的第一个优势。

第二个（但相关的）优点是对于像 #1 这样的循环- 编译器通常能够使用 stride-1 内存访问模式有效地自动矢量化代码（stride-1 意味着在每次下一次迭代）。相反，对于像 #2 这样的循环，自动矢量化通常不会正常工作，因为没有连续的 stride-1 迭代访问内存中的连续块。

嗯，我的回答很笼统。对于与#1 或#2 完全相同的非常简单的循环，可能会使用更简单的积极编译器优化（对任何差异进行分级），并且编译器通常能够使用 stride-1 自动矢量化#2用于外循环（尤其是使用 # pragma simd 或类似的）。

于 2013-10-03T19:44:33.567 回答
1

第一个选项更好，因为我们可以存储a[i] in a temp variable在第一个循环中，然后在其中查找 j 索引。从这个意义上说，它可以说是缓存变量。

于 2015-03-25T16:31:13.877 回答