在二维数组上迭代的嵌套循环的哪个顺序更有效

在时间(缓存性能)方面，以下嵌套循环中哪一个在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;
}
}
9415 次浏览
小开

在您的情况下(填充所有数组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];
}
小开
最佳答案

第一种方法稍微好一点，因为分配给它们的单元格彼此挨着。

第一种方法:

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

第二种方法:

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

这种微观优化依赖于平台，因此您需要对代码进行概要分析，以便能够得出合理的结论。

小开

  1. 对于数组[100][100]-它们是相同的，如果 L1缓存大于100 * 100 * sizeof (int) = = 10000 * sizeof (int) = = [通常]40000。注意在 沙桥-100 * 100整数应该足够的元素看到一个差异，因为 L1缓存只有32k。

  2. 编译器可能仍然会优化这些代码

  3. 假设没有编译器优化，矩阵不适合 L1缓存-第一个代码更好，因为缓存性能[通常]。每次在缓存中没有找到元素时——你得到一个 缓存未命中——并且需要转到 RAM 或 L2缓存(它们要慢得多)。从 RAM 到缓存的元素[缓存填充]是以块的形式完成的[通常是8/16字节]-所以在第一段代码中，你得到 最多的错过率为 1/4[假设缓存块为16字节，4字节整数] ，而在第二段代码中它是无界的，甚至可以是1。在第二个代码管理单元(已经在缓存中的元素[插入到缓存中填充相邻的元素])被删除，并且您会得到一个冗余的缓存丢失。

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

结论: 对于我所知道的所有缓存实现来说，前者不会比后者更糟。它们可能是相同的——如果根本没有缓存，或者数组完全适合缓存——或者由于编译器最佳化。

小开

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

小开

在第二个代码片段中，每次迭代中 j的更改将生成一个具有低空间局部性的模式。请记住，在幕后，数组引用计算:

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

考虑一个简化的 L1缓存，它只能容纳数组中的50行。对于前50次迭代，您将为50次缓存丢失付出不可避免的代价，但接下来会发生什么？对于从50到99的每次迭代，您仍然会缓存丢失，并且必须从 L2(和/或 RAM 等)获取。然后，x更改为1，y重新启动，导致另一个缓存丢失，因为数组的第一行已经从缓存中删除，等等。

第一个片段没有这个问题。它访问 主要订单中的数组，这样可以获得更好的位置——每行只需要为缓存丢失付费一次(如果循环启动时数组中的一行不在缓存中)。

也就是说，这是一个非常依赖于体系结构的问题，因此您必须考虑具体细节(L1缓存大小、缓存行大小等)才能得出结论。您还应该度量这两种方式，并跟踪硬件事件，以便从中获得可以得出结论的具体数据。

小开

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

在大多数情况下，第一个更好，但我认为确切的答案是: 看情况了，不同的架构可能会有不同的结果。

小开

在第二个方法中，< strong > Cache miss，因为缓存存储连续数据。 因此第一种方法比第二种方法有效。

小开

一般来说，更好的位置(被大多数响应者注意到)只是循环 # 1性能的第一个优势。

第二个(但相关的)优势是，对于 就像 # 1-编译器通常能够对 有效地自动向量化的代码进行跨1内存访问模式(跨1意味着在每次下一次迭代中可以连续访问数组元素)。 相反，像 # 2这样的循环自动向量化通常不能正常工作，因为在内存中不存在对连续块的连续跨越 -1迭代访问。

我的答案是一般。对于像 # 1或 # 2这样的非常简单的循环，可以使用更简单的积极的编译器优化(对任何差异进行评级) ，而且编译器通常能够为 外面循环使用大步 -1自动向量化 # 2(特别是使用 # 杂注 simd 或类似的方法)。

小开

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


提交答案