矩阵存储方式对cache miss penalty的影响：1D数组为何性能更差？

实验背景 #

• 实验目标：探究矩阵存储方式对缓存缺失惩罚的影响，选取最坏场景——行优先存储的矩阵采用列优先矩阵-向量乘法算法
• 对比存储实现：
  1. 指针数组（array of pointers）：存储行优先矩阵，每行对应一个独立指针
  2. 一维数组（1D array）：用连续内存块存储，通过线性索引i + j*N（N为矩阵行数）定位元素
• 实验环境：13代Intel i7-1360P、gcc 13.2.1 -O2
• 反常结果：一维数组的性能远差于指针数组，与“连续内存块访问更高效”的普遍认知相悖

核心原因分析 #

1. 内存访问模式与缓存预取的差异 #

• 指针数组场景：访问matrix[i][j]时，先读取行指针matrix[i]，再访问该行的第j个元素。行指针本身是连续存储的，CPU预取器会提前加载后续的行指针，使得指针访问的缓存命中率接近100%。虽然行内元素是列遍历（跳步访问），但每次仅需加载当前行的单个元素，指针预取的低开销抵消了部分行内缓存缺失的影响。
• 一维数组场景：线性索引i + j*N的内存访问步长等于矩阵行数N，若N较大（比如超过缓存行大小的倍数），会导致完全无法利用缓存预取——每次访问的地址既不在当前缓存行，也不在预取范围内，几乎每次元素访问都是缓存缺失，需要从主存加载，惩罚成本极高。

2. 编译器优化与计算开销差异 #

• 指针数组：编译器对二维指针的访问模式识别更清晰，容易生成循环展开、指针预取等优化指令；行内元素访问是直接的指针偏移，无额外计算开销。
• 一维数组：线性索引中的乘法j*N需要在循环内层反复执行，会积累额外的计算开销；同时编译器难以预测这种大跳步的访问模式，无法生成有效的预取优化，进一步放大了性能差距。

3. 缓存行利用率差异 #

• 指针数组：64位系统中每个行指针占8字节，一个64字节的缓存行可存储8个行指针。遍历列时，预取器会一次性加载后续多个行指针，指针访问的缓存行利用率为100%；行内元素虽缓存利用率低，但仅占整体访问的一部分。
• 一维数组：大跳步访问导致每个缓存行仅被使用1个元素（8字节），缓存行利用率不足13%，大量缓存空间被浪费，且每次加载缓存行的成本完全无法分摊。

总结 #

这种反常结果并不否定“连续内存块更优”的普遍结论——该结论的前提是访问模式与存储模式匹配（如行遍历行优先矩阵）。当访问模式与存储模式完全不匹配时，指针数组通过高利用率的指针缓存访问，抵消了部分行内元素的缓存缺失开销；而一维数组的大跳步访问完全无法利用缓存优势，最终导致性能更差。

内容的提问来源于stack exchange，提问作者j-hap