数组连续性对CPU缓存性能的影响分析

数组在内存中的物理连续性是决定CPU缓存行性能的关键——连续布局能让多个数据元素“打包”进同一64字节缓存行，顺序访问时一次加载即可复用多次，显著提升命中率（如数组遍历可达90%以上）；而链表节点分散、二维数组列优先访问或结构体未对齐等不匹配连续性的做法，会引发大量跨行加载和cache miss，严重拖慢程序速度。真正影响性能的不是缓存是否存在，而是“一次加载能支撑多少次计算”。

数组的物理连续性直接决定了 CPU 缓存行能否被高效利用。关键不是“有没有缓存”，而是“一次加载能用多久”——连续布局让多个元素挤进同一缓存行，大幅减少内存访问次数。

缓存行加载机制与数组连续性的匹配关系

CPU 每次从内存取数据，不是按字节、也不是按变量，而是按固定大小的块（通常是 64 字节）整块搬入缓存。数组在内存中是挨着排的，比如 int 类型占 4 字节，那么一个缓存行就能装下 16 个连续 int 元素。当你顺序访问 arr[0]、arr[1]、arr[2]……前 16 个元素大概率已在第一次加载时全部进缓存，后续访问基本不触发新内存读取。

• 反例：链表节点分散分配，哪怕只存两个指针（16 字节），每次跳转都大概率跨缓存行，造成大量空载加载（64 字节只用 16 字节）
• 实测现象：遍历百万级 int 数组，L1 缓存命中率常超 90%；同规模链表遍历，命中率可能低于 20%

二维数组遍历时的行优先 vs 列优先差异

二维数组本质仍是线性存储，C/C++ 默认按行优先（row-major）排布：a[0][0]、a[0][1]、a[0][2]……a[0][n-1]、a[1][0]……因此访问模式必须匹配这个物理顺序，才能让缓存行“物尽其用”。

• 推荐写法（行优先）：for (i=0; i —— 每次内层循环都在同一缓存行内滑动，预取器能稳定跟上
• 低效写法（列优先）：for (j=0; j —— 每次 i 变化都跳到下一行首地址，间隔为 N×sizeof(int)，极易导致每步都 cache miss
• 实验显示：对 2048×2048 的 int 数组，列优先遍历耗时可能是行优先的 2–8 倍

结构体数组与缓存行对齐的实际影响