嵌套循环访问数组的C代码中Vector2运行更快、Cache misses更少的原因

你们的初步猜想方向是对的，但只摸到了表层，要结合Cache line的块加载规则、时间局部性、硬件预取逻辑才能把差异说透：

基础参数先对齐 #

• 单个INT4占4字节，题目里的Cache line是64B，算下来一条Cache line能连续放16个INT4元素。Cache和主存交互的时候，是按整条Cache line搬数据的，只要访问到块里随便一个元素，CPU就会把整64B的数据一次性拉进Cache，后面再访问块里任何位置都不会再跑主存。
• 总Cache大小是12288KB也就是12MB，分析的时候默认数组规模和Cache容量差不多，不考虑数组大到把Cache完全挤爆的极端情况。

两段代码的实际Cache行为拆解 #

Vector2（外层跑100次k循环，内层顺着i遍历整个数组）的表现 #

• 冷启动阶段：第一次跑k=0的内层循环时，Cache是空的，i从0顺着走到n，每碰到没加载过的Cache块就触发一次强制miss，把对应块拉进Cache。因为内层i是严格按4B步长连续往高地址走，完全踩中了CPU硬件预取器的触发规则，预取器会提前把后面要访问的Cache块拉进Cache，不用等真正访问的时候才现等主存，延迟低很多。
• 循环复用阶段：第一次k循环跑完整个数组之后，只要数组总大小没超过12MB的Cache容量，所有数组对应的Cache块都会稳稳留在Cache里。后面99轮k循环再遍历数组的时候，所有访问都是直接命中Cache，几乎不会再产生新的容量或者冲突miss，总miss数很低。

Vector1（外层顺着i遍历数组，内层对每个i跑100次k循环）的表现 #

• 虽然Vector1的外层i也是顺着地址走的，但内层循环是死死盯住同一个v[i]读写100次，访问节奏是“对同一个地址怼100次，再跳到相邻地址再怼100次”。这种带长间隔的跳变，完全不符合预取器要求的“短间隔、固定步长连续访问”的触发条件，预取器根本预判不到后面要哪个块，所有miss都要现场等主存响应，延迟比Vector2高一大截。
• 而且当数组规模接近Cache容量的时候，Vector1在每个i上花的100次循环时间太长，按照LRU的Cache替换规则，之前已经加载进来的相邻块，因为长时间没被访问，会被后续加载的新块提前挤出去。等后面真的需要访问这些块的时候，又要重新从主存拉，白白多了很多不必要的miss，总miss数自然比Vector2高。

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