在迭代2D数组时，哪种嵌套循环的顺序更高效？
这个问题的出现是因为在遍历二维数组时，嵌套循环的顺序可能会影响代码的效率。在这个讨论中，某些情况下了两种不同的嵌套循环顺序，即第一种版本和第二种版本。然而，有人指出这种微观优化是依赖于平台的，因此需要对代码进行性能分析才能得出合理的结论。
然后，某些情况下了在实际的平台中是否存在第一种版本比第二种版本更慢的情况。尽管这是一种微观优化，可能并不会产生明显的差异，但如果你需要在两种等效的简单、清晰和有效的代码写法中进行选择，并且你正好知道其中一种至少不会比另一种更慢，那为什么不选择速度更快的呢？
接着，有人指出这个问题至少与编程语言相关。例如，Fortran在内存中的数组布局与其他语言不同，所以对于Fortran来说，第一种版本可能比第二种版本更慢。
因此，对于这个问题，没有一个统一的答案。最好的解决方法是使用性能分析工具来测试不同的嵌套循环顺序，以确定哪种方式更有效。在没有明确的性能需求之前，不需要过度优化。然而，如果在两种写法之间没有明显的区别，并且已知一种方式至少不会比另一种方式更慢，那么选择速度更快的方式是合理的选择。
问题的出现原因是：在迭代二维数组时，使用不同的嵌套循环顺序可能会影响效率。解决方法是根据缓存性能和局部性原理来选择合适的嵌套循环顺序。
在一个100x100的数组中，如果L1缓存大于100x100xsizeof(int)（通常为40000字节），两种嵌套循环顺序的效率是相同的。然而，如果L1缓存只有32k（如Sandy Bridge），那么100x100的整数元素就足够大以至于可以看出两种顺序之间的差异。
编译器通常会对这段代码进行相同的优化处理，所以无论使用哪种顺序都可能得到相同的结果。
假设没有编译器优化，并且矩阵不适合放入L1缓存，那么第一个代码更好，因为它可以提高缓存性能。每次在缓存中找不到一个元素时，就会发生缓存未命中，需要从RAM或L2缓存中获取（它们的速度要慢得多）。从RAM到缓存的数据传输是以块的形式进行的（通常是8/16字节），所以在第一个代码中，最多只会有1/4的缓存未命中率（假设缓存块是16字节，整数是4字节），而在第二个代码中未命中率是不受限制的，甚至可能为1。在第二个代码片段中，已经在缓存中的元素（在缓存块中填充相邻元素时插入的）会被取出，导致冗余的缓存未命中。
这与局部性原理密切相关，局部性原理是在实现缓存系统时使用的一般假设。第一个代码遵循这个原理，而第二个代码不遵循，所以第一个的缓存性能会更好。
对于我所了解的所有缓存实现，第一个代码至少不会比第二个更差。如果没有缓存或者整个数组完全适合缓存，它们可能是相同的，或者由于编译器优化的原因。
需要注意的是有两个问题：内存从L2缓存到寄存器需要的时间以及L2缓存和寄存器之间的带宽。如果只是考虑延迟问题，那么预取（无论是软件还是硬件）可以消除两种访问数据方式之间的大部分差异。然而，硬性限制在于带宽，因为每次内存访问读取整个缓存行而不是单个整数，根据您的假设，一个访问模式必须读取四倍于另一个访问模式的内存总量。
关于如何估计这些未命中率1/4和1的问题，请问您能解释一下吗？
对于迭代二维数组的嵌套循环，使用第一种方法更为高效。原因是，第一种方法中相邻的单元格被分配在一起。
第一种方法：
[ ][ ][ ][ ][ ] .... ^1号赋值 ^2号赋值 [ ][ ][ ][ ][ ] .... ^101号赋值
第二种方法：
[ ][ ][ ][ ][ ] .... ^1号赋值 ^101号赋值 [ ][ ][ ][ ][ ] .... ^2号赋值
这是不是意味着访问它们比其他一种方法更快？这意味着你会遇到更少的缓存未命中，处理器能够更好地猜测下一个要访问的内存。
Raymond Chen在他的博客上有一个类似的帖子，有图片和很好的解释：blogs.msdn.com/b/oldnewthing/archive/2005/08/05/448073.aspx。将位图视为一个更大的数组。
有趣的基准测试：在我的特定计算机和编译器上（i5处理器，Linux，gcc -O3），并且使用一个更大的矩阵，第一种方法花费了2秒，而第二种方法花费了19秒。
在我的计算机上进行的基准测试也得出了第一种方法更高效的结论。
- McCarthy：这是一个非常具体的基准测试，几乎没有意义，在大多数真实环境中（具有更重要的循环体）差异会更小甚至不存在。
- A：我不同意。查看大多数矩阵或图像库的实现（或其他操作大量数据数组的库）。它们通常会尽力避免以非顺序的方式访问数组，因为缓存未命中可能非常昂贵。
- B：如果你有一个内部循环速度太快的情况，是的，否则不会。事实上，第二种情况下的访问仍然非常可预测（跨度），除了列跳跃之外，任何现代CPU都会在你需要它们之前预取这些缓存行。
- A：哦，我同意。只有在访问顺序会产生很大差异的情况下，才会有很大的区别，例如数组足够大无法适应缓存的情况。另一方面，那些通常是循环体很小且缓存未命中非常明显的情况。如果处理大型数组，通常最好确保访问尽可能顺序（除非性能无关紧要）。