前缀和矩阵相关问题中为什么1个for循环比2个for循环运行更慢？

核心原因是CPU缓存的空间局部性差异 #

该现象是大内存操作场景下非常典型的缓存效率问题，具体原因如下：

• 二维数组在内存中采用行优先的存储顺序，连续按行遍历的内存访问模式缓存命中率最高，CPU的硬件预取器也可提前将后续要用到的内存块加载到高速缓存中，大幅降低内存访问延迟。
• 混合单循环版本中，单次迭代需要同时访问3块独立的内存区域：原始矩阵a、01矩阵lower、前缀和矩阵b，且前缀和计算需要访问b[i-1][j]（和当前b[i][j]的内存地址差了整行的长度，跨度极大），混乱的内存访问模式会导致频繁的缓存失效（cache miss），高速缓存利用率极低，大部分时间CPU都在等待内存数据加载。
• 拆分后的两个循环都遵循了最优的内存访问模式：
  1. 第一个循环仅顺序访问a和lower，完全按行遍历，缓存命中率接近100%
  2. 第二个循环仅顺序访问lower和b，虽然仍需要访问上一行的b数据，但此时整个b矩阵的访问是独立的，CPU预取效率更高，缓存失效的概率远低于混合循环
• 虽然拆分后循环的总指令数略有提升，但内存访问延迟带来的性能损耗远大于额外循环带来的指令开销，最终整体性能反而更高。这种现象在竞赛编程的大矩阵测试用例场景下会被放大，因为矩阵规模通常远超过CPU高速缓存的容量，缓存失效的代价极高。

内容的提问来源于stack exchange，提问作者silverfox