用于迭代2D数组的嵌套循环的哪种排序更有效-Java 学习之路

在时间（缓存性能）方面，嵌套循环在迭代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;    
   }
}

10 回答

第一种方法略好一些，因为被指定的细胞彼此相邻 .

第一种方法：

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

第二种方法：

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

回复于 2024-04-27T11:13:21+08:00

2
- 对于数组[100] [100] - 它们都是相同的，如果L1缓存大于100 * 100 * sizeof（int）== 10000 * sizeof（int）== [通常] 40000.注意Sandy Bridge - 100 * 100整数应该是足够的元素来看到差异，因为L1缓存只有32k .
- 编译器可能会优化此代码
- 假设没有编译器优化，并且矩阵不适合L1缓存 - 由于缓存性能[通常]，第一个代码更好 . 每次在缓存中找不到元素时 - 你得到一个cache miss - 并且需要转到RAM或L2缓存[它们慢得多] . 从RAM到缓存[缓存填充]的元素以块[通常为8/16字节]完成 - 因此在第一个代码中，您获得 at most 未命中率 1/4 [假设16字节缓存块，4字节整数]而在第二个代码中代码它是无界的，甚至可以是1.在第二个代码快照中 - 已经在缓存中的元素[插入到相邻元素的缓存填充中] - 被取出，并且您获得了冗余缓存未命中 .
- 这与principle of locality密切相关，这是实现缓存系统时使用的一般假设 . 第一个代码遵循这个原则，而第二个代码没有 - 因此第一个代码的缓存性能将优于第二个代码 .
Conclusion: 对于我所知道的所有缓存实现 - 第一个将不会比第二个更糟糕 . 它们可能是相同的 - 如果根本没有缓存或者所有数组完全适合缓存 - 或者由于编译器优化 .
回复于 2024-04-27T11:13:21+08:00
9

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

回复于 2024-04-27T11:13:21+08:00
3
在第二个片段中，每次迭代中 j 的更改会生成一个空间局部性较低的模式 . 请记住，在幕后，数组引用计算：
```
( ((y) * (row->width)) + (x) )
```
考虑一个简化的L1缓存，它只有50行我们的数组有足够的空间 . 对于前50次迭代，您将支付50次缓存未命中的不可避免的成本，但接下来会发生什么？对于从50到99的每次迭代，您仍将缓存未命中并且必须从L2（和/或RAM等）获取 . 然后， x 更改为1并且 y 重新开始，导致另一个缓存未命中，因为阵列的第一行已从缓存中逐出，依此类推 .

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

话虽如此，这是一个非常依赖于架构的问题，因此您必须考虑具体情况（L1缓存大小，缓存行大小等）来得出结论 . 您还应该测量两种方式并跟踪硬件事件，以获得具体数据以得出结论 .
回复于 2024-04-27T11:13:21+08:00
1

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

回复于 2024-04-27T11:13:21+08:00
0

这是关于 cache line bouncing 的经典问题

在大多数时候第一个更好，但我认为确切的答案是： IT DEPENDS ，不同的架构可能会有不同的结果 .

回复于 2024-04-27T11:13:21+08:00
63

在第二种方法中， Cache miss, because the cache stores contigous data. 因此第一种方法比第二种方法有效 .

回复于 2024-04-27T11:13:21+08:00
41
在你的情况下（填充所有数组1的值），这将更快：
```
for(j = 0; j < 100 * 100; j++){
      a[j] = 10;
   }
```
你仍然可以将 a 视为二维数组 .

EDIT ：正如Binyamin Sharet所提到的那样，如果 a 被声明的话，你可以这样做：
```
int **a = new int*[100];
for(int i = 0; i < 100; i++){
    a[i] = new int[100];
}
```
回复于 2024-04-27T11:13:21+08:00
12

通常，更好的局部性（大多数响应者注意到）只是循环＃1性能的第一个优势 .

第二个（但相关的）优点是，对于 loops like ＃1 - 编译器通常能够 efficiently auto-vectorize 具有stride-1内存访问模式的代码（stride-1意味着在每个下一个中逐个连续访问数组元素迭代） . 相反， for loops like #2 ，自动矢量化通常不会正常工作，因为内存中没有连续的stride-1迭代访问contiguos块 .

好吧，我的回答是一般的 . 对于非常简单的循环，就像＃1或＃2一样，可能会使用更简单的激进编译器优化（对任何差异进行分级），编译器通常也能够使用stride-1自动向量化＃2进行外循环（特别是＃ pragma simd或类似的） .

回复于 2024-04-27T11:13:21+08:00
4

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

回复于 2024-04-27T11:13:21+08:00

用于迭代2D数组的嵌套循环的哪种排序更有效

10 回答

相关问题