logo标签列表

哪种嵌套循环的顺序适用于迭代二维数组更有效率？

cperformancefor-loopcpu-cache
72

在时间（缓存性能）方面，以下哪种嵌套循环的顺序来遍历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;    
   }
}
6
小提示：使用"++i"而不是"i++"。 它更快（虽然对于数字而言与"i++"的差异非常小，但对于STL迭代器而言则不是这样）。 - Raxillan
12
@Raxillan - 这个说法在现代处理器和编译器中并非总是正确的，具体情况取决于实际使用的编程语言。 - user177800
33
@Raxillan那是错误的。它们将同样高效，除非你在使用70年代的编译器。 - Luchian Grigore
10
在这种情况下，不需要复制。优化器足够聪明地知道它不需要一份副本。 - Luchian Grigore
5
为什么会有所改变呢？新值和旧值都没有在同一表达式中使用，编译器也知道这一点。那么为什么会有所不同呢？ - glglgl
显示剩余4条评论
10个回答
65

第一种方法稍微好些，因为被分配的单元格都在相邻位置。

第一种方法：

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

第二种方法：

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment
2
Raymond Chen在他的博客上也有一篇类似的帖子，配有图片和很好的解释：http://blogs.msdn.com/b/oldnewthing/archive/2005/08/05/448073.aspx。将位图视为更大的数组。 - chris
28
有趣的基准测试：在我的特定计算机和编译器上（i5处理器，Linux，gcc -O3），并且使用更大的矩阵，第一种方法花费了2秒钟，而第二种方法花费了19秒钟。 - Thomas Padron-McCarthy
3
我的电脑测试结果也表明第一种方法更有效。 - Jesse Good
2
@Leo：如果你有一个内部循环太快，是的，否则：不必要。问题是第二种情况下的访问仍然非常可预测（跨度），除了列跳跃之外，任何现代CPU都会在你需要它们之前预取这些缓存行。 - KillianDS
1
@KillianDS：哦，我同意这个观点。唯一的情况是当数组足够大而无法适应缓存时，访问顺序会产生很大的差异。另一方面，这些通常是循环体非常小且缓存未命中非常明显的情况。如果使用大型数组，则通常最好确保访问尽可能连续（除非性能无关紧要）。 - Leo
显示剩余4条评论
44

  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。在第二段代码快照中 - 已经在高速缓存填充中插入的元素[为相邻元素]将被取出，这样您就会得到冗余的缓存未命中。

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

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

K.... 所以意味着第一个总是更有效率的... 我们可以更快地访问元素... - Sachin Mhetre
5
就我所知，对于所有缓存实现方式而言，第一个与第二个并不会更糟。它们可能相同——如果没有缓存或整个数组都适合缓存的话。 - amit
值得注意的是，这里有两个问题：内存从L2高速缓存到寄存器所需的时间以及L2高速缓存和寄存器之间的带宽。如果仅仅是延迟的问题，那么预取（无论是在软件中还是在硬件中）可以消除访问数据的两种方式之间的大部分差异。然而，在这里的硬性限制是带宽；由于每个内存访问读取整个缓存行而不是单个int，因此根据您的假设，一种访问模式必须总共读取四倍的内存。 - user1084944
1
@amit，您能否解释一下您是如何估计这些缺失率 1/4 和 1 的呢？ - sgnsajgon
13

这种微小的优化取决于平台，因此您需要对代码进行剖析以得出合理结论。

23
如果有人真正展示了一个现实世界的平台，第一版比第二版慢，我会投赞成票。是的，这是微观优化。是的，它可能并没有明显的差别。不过，除非性能分析器表明它们是关键性能因素，否则你不应该浪费时间重写循环。但是，如果你需要在两种同样简单、清晰和有效的编写代码方式之间做出选择，并且你刚好知道一个经验法则，可以说明其中一种至少不比另一种慢，那么为什么不选择不慢的呢？ - Ilmari Karonen
2
@IlmariKaronen 我赞同了你的评论。但请注意，这至少与编程语言有关。例如，Fortran在内存中排列数组的方式与其他语言不同，因此对于Fortran而言，第一个版本可能比第二个版本慢。 - fishinear
10
在你的第二个片段中，每次迭代中j的变化会产生一个具有低空间局部性的模式。请记住，在幕后，数组引用计算的是：
( ((y) * (row->width)) + (x) )
考虑一个简化的 L1 缓存，它只有足够空间来容纳数组的 50 行。在前 50 次迭代中，你将支付 50 次不可避免的缓存未命中成本，但是接下来会发生什么呢？从第 50 次到第 99 次的每次迭代中，你仍然会出现缓存未命中并且必须从 L2（和/或 RAM 等）获取。然后，x 改变为 1，y 重新开始，导致另一个缓存未命中，因为数组的第一行已经被驱逐出缓存，等等。
第一个代码片段没有这个问题。它按行主序访问数组，可以实现更好的局部性 - 每行最多只需要支付一次缓存未命中 (如果在循环开始时缓存中不存在数组的某一行)。
话虽如此，这是一个非常依赖于架构的问题，所以你需要考虑具体细节（L1 缓存大小、缓存行大小等）来得出结论。你也应该测量两种方法并跟踪硬件事件，以获得具体数据以得出结论。
6

考虑到C++是行主序，我认为第一种方法会稍微快一些。在内存中，二维数组表示为单维数组，性能取决于使用行主序还是列主序进行访问。

4
在第二种方法中，由于缓存存储的是连续数据，所以会出现缓存未命中。因此，第一种方法比第二种方法更有效。
4

这是一个关于缓存行反弹的经典问题。

大多数情况下，第一种方法更好，但我认为确切的答案是：取决于具体情况，不同的架构可能会有不同的结果。

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];
}
4
你需要使用指针来完成这个操作，不能直接这样赋值。 - MByD
1
抱歉有点麻烦，但你需要双重引用它 :) - MByD
2

总的来说，更好的局部性（大多数回答者都注意到了）只是循环#1性能的第一个优点。

第二个（但相关的）优点是，对于像循环#1这样的循环，编译器通常能够使用步幅为1的内存访问模式（步幅为1表示在每个下一次迭代中连续访问数组元素），从而有效地自动向量化代码。相反，对于像循环#2这样的循环，自动向量化通常不会很好地工作，因为在内存中没有连续的步幅为1的迭代访问连续块。

嗯，我的答案是普遍的。对于像#1或#2这样的非常简单的循环，可能会使用更简单的激进编译器优化（分级任何差异），并且编译器通常能够使用步幅为1的自动向量化外部循环#2（特别是使用#pragma simd或类似方法）。

1

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接