优化百万级二维数组遍历：行优先还是列优先？

本文分析了高效遍历100万级二维数组 matrix[x][y] 的两种方法，并比较了它们的性能差异。

方法一：行优先遍历

for (int x = 0; x < size; x++) {
  for (int y = 0; y < size; y++) {
    // ...操作...
  }
}

方法二：列优先遍历

for (int y = 0; y < size; y++) {
  for (int x = 0; x < size; x++) {
    // ...操作...
  }
}

虽然两种方法看起来只是循环顺序不同，但实际测试表明，行优先遍历（方法一）显著快于列优先遍历（方法二）。

这是因为计算机内存通常采用行优先存储方式。方法一符合内存布局，充分利用CPU缓存的空间局部性，减少内存访问次数，提高效率。而方法二则导致CPU缓存命中率降低，频繁访问内存，性能下降。 可以将方法一比作连续读取数据，方法二则像在内存中跳跃式读取，后者耗时更多。

尽管汇编层面的指令差异可能很小，但由于内存访问模式的差异，行优先遍历在实际运行中展现出明显的性能优势。 这说明高效代码编写需要充分考虑数据结构的内存存储方式和CPU缓存机制，才能最大限度地优化程序性能。