迭代二维数组的嵌套循环的顺序更有效率
在时间（高速caching性能）方面，下列哪个嵌套循环顺序遍历二维数组更有效？ 为什么？
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; } }
第一种方法稍好一点，因为细胞被分配到彼此相邻。
第一种方法：
[ ][ ][ ][ ][ ] .... ^1st assignment ^2nd assignment [ ][ ][ ][ ][ ] .... ^101st assignment
第二种方法：
[ ][ ][ ][ ][ ] .... ^1st assignment ^101st assignment [ ][ ][ ][ ][ ] .... ^2nd assignment
-
对于array [100] [100] – 如果L1caching大于100 * 100 * sizeof（int）== 10000 * sizeof（int）== [[通常]为40000），它们都是相同的。注意在Sandy Bridge -因为L1caching只有32k，所以100 * 100的整数应该是足够的元素来看看区别。
-
编译器可能会尽可能地优化这个代码
-
假设没有编译器优化，并且matrix不适合L1caching – 第一个代码由于caching性能[通常]更好。 每次在高速caching中找不到某个元素时 – 会发生高速caching未命中 – 并需要进入RAM或L2高速caching[速度较慢]。 从RAM中获取元素来caching[caching填充]是以块（通常是8/16字节）完成的 – 所以在第一个代码中， 最多可以得到
1/4错失率[假设16字节caching块，4字节整数]在第二个代码中它是无界的，甚至可以是1.在第二个代码snap中，已经在高速caching中的元素（插入到相邻元素的高速caching填充中）被取出，并且会得到冗余高速caching未命中。- 这与局部性原理密切相关，这是实现caching系统时的一般假设。 第一个代码遵循这个原则，而第二个代码没有 – 所以第一个代码的性能会比第二个更好。
结论：对于所有的caching实现我知道 – 第一个将不会更糟。 它们可能是相同的 – 如果根本没有caching，或者所有的数组完全适合caching – 或者由于编译器优化。
这种微观优化是依赖于平台的，所以你需要对代码进行剖析，以便能够得出合理的结论。
在第二个片段中，每次迭代中j的变化产生一个低空间局部性的模式。 请记住，在幕后，数组引用计算：
( ((y) * (row->width)) + (x) )
考虑一个简化的L1高速caching，只有50行的arrays有足够的空间。 对于前50次迭代，你将支付50次caching未命中的不可避免的成本，但是会发生什么？ 对于从50到99的每次迭代，您仍然会caching未命中，并且必须从L2（和/或RAM等）中获取。 然后， x更改为1， y开始，导致另一个caching未命中，因为arrays的第一行已从caching中逐出，等等。
第一个片段没有这个问题。 它以行优先顺序访问数组，从而获得更好的局部性 – 每行最多只需支付一次caching未命中（如果在循环启动时，caching未存在于caching中）。
这就是说，这是一个非常依赖于架构的问题，因此您必须考虑具体情况（L1caching大小，caching行大小等）来得出结论。 您还应该测量两种方式，并跟踪硬件事件，以获得具体的数据，从中得出结论。
考虑到C ++是行重点，我相信第一种方法会快一点。 在内存中，二维数组用单维数组表示，性能取决于使用行主或列主要访问它
这是关于cache line bouncing一个经典问题
在大多数情况下，第一个更好，但我认为正确的答案是： IT依赖 ，不同的架构可能会有不同的结果。
在第二种方法中， 高速caching未命中，因为高速caching存储连续数据。 因此第一种方法比第二种方法有效。
在你的情况（填充所有数组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]; }
一般来说，更好的地方性（被大多数响应者注意到）只是循环1性能的第一个优势。
第二个（但相关的）优点是对于像 ＃1那样的循环 ，编译器通常能够有效地自动向量化具有stride-1存储器访问模式的代码（stride-1意味着在数组元素中连续访问每下一个迭代）。 相反， 对于像＃2这样的循环 ，自动vector化通常不会正常工作，因为对内存中的连续块没有连续的第一次迭代访问。
那么，我的答案是一般的。 对于非常简单的循环，就像＃1或＃2一样，甚至可以使用更简单的攻击性编译器优化（对所有差异进行分级），而且编译器通常能够自动vector化外部循环的stride-1（特别是＃杂注simd或类似）。
第一个选项是更好的，因为我们可以将第一个循环中a[i] in a temp variable存储a[i] in a temp variable ，然后在其中查找第j个索引。 在这个意义上，它可以被称为cachingvariables。
