缓存模型：cache line、局部性、缓存层级

HPC/AI Infra 性能题之首。多数面试「为什么这段循环慢」到最后都归结到 内存而不是 CPU——现代处理器算得快但访存慢。

一、缓存层级（现代 x86 常识数值）

层	典型大小	延迟(约)	每核/共享
寄存器	微	~0	每核
L1	32–64KB	~1 ns (4-5 cycles)	每核 (指令+数据)
L2	256KB–1MB	~3-5 ns	每核
L3 (共享)	8-64MB	~12-40 ns	多核共享
主存 DRAM	GB	~80-120 ns	全系统

关键数量级：一次 DRAM miss（~100ns）≈ 几百条指令时间！所以缓存命中率决定吞吐上限。 （数值给范围即可，别背死——给「L1 ~4-5cyc、L3 ~几十 ns、主存 ~80-120ns、延迟差两个数量级」足够有说服力。）

二、Cache Line（缓存行）：最小加载单位

• x86/AArch64 通常 64 字节；一次 miss 把整行 64B 拉进 cache（顺带把邻居数据也带上——这是局部性收益来源）。
• 读一整行只需一次 miss：连续访问 64B 内数据都是命中。
• 对 HPC 的意义：
  1. 大量连续 traverse（for i=0..n-1 数组）天然缓存友好；
  2. 避免跳着访存（每次访问跨行 → 每元素一次 miss，灾难）；
  3. 假共享：不同线程写不同变量却在同一行 → 见并发篇。

三、空间与时间局部性

• 时间局部性：同一数据短期重复使用 → 留在 cache（如内层循环变量复用）。
• 空间局部性：相邻数据 → 一次加载多命中（访问连续数组）。
• 写代码判断：我的外层循环是否在跳着访问（m[k][i] 列优先 vs m[i][k] 行优先）？

四、经典问题：行优先 vs 列优先遍历

C/C++ 二维数组按行优先存储：

double m[N][N];
// 快速（行优先，连续地址 → 缓存友好）
for (int i=0;i<N;i++) for (int j=0;j<N;j++) sum += m[i][j];
// 慢速（每次跨行跳 N*8 字节 → 每元素 miss）
for (int j=0;j<N;j++) for (int i=0;i<N;i++) sum += m[i][j];

访问图案同样次数，内层顺序不同，性能可差 10~100×（尤其 N 大到塞不进 cache）。

五、Cache Blocking / Tiling（矩阵粒度复用）

目的：让内层循环的数据块能留在 cache 反复利用，减少 miss。

// 朴素朴素阵乘 A*x：每次都对 A 整行 … cache 不友好
// block 版思路：
#define BLK 32
for (int i0=0;i0<N;i0+=BLK)
  for (int k0=0;k0<N;k0+=BLK)
    for (int j0=0;j0<N;j0+=BLK)
      for (int i=i0;i<i0+BLK;i++)
        for (int k=k0;k<k0+BLK;k++)
          for (int j=j0;j<j0+BLK;j++)
            C[i][j] += A[i][k]*B[k][j];

块小到 L1/L2 装得下 → A 的 BLK 行反复用而不换出。矩阵乘从三重循环 naive 到 blocking/向量化 通常提升数十倍（配合 -O3 + SIMD）。同思路 = BLAS 的 GEMM、tiling 技术。

六、写策略：write-back / write-through、非临时存储

• x86 L1/L2 write-back（延迟写回主存，cpu 不直接写 DRAM）；写也经过 cache（write allocate）。
• 要绕过 cache 直写流的特殊指令 _mm_stream_* (non-temporal store)——《不污染 cache 的大块顺序写》。
• memset/memcpy 用上 SIMD + non-temporal 可更快（编译器/库自动做或手动）。

七、别名 / restrict 对性能的影响

restrict(restrict) 告诉编译器指针不 alias，允许重排/向量化不保守；否则每次循环差点都假设可能重叠保守处理。HPC 内核常加 restrict。

八、HPC 面试答「为什么慢 / 怎么优化」万能框架

1. 先想是算得快还是访存快（arithmetic intensity）：访存受限 → 优化局部性/向量化；计算受限 → 算法/编译器。
2. 看cache miss：用 perf cache-misses、Intel perf stat/vtune，命中率是否接近 100%。
3. 命中率低 → 连续化、拆小步长、tiling、SoA。
4. 命中率都高还慢 → 分支预测、向量化、并行（Amdahl）、指令级并行。
5. 最后才怀疑具体指令数——先用 profiler 数据说话，别拍脑袋。

九、自测

1. 一次 cache miss 大概多少指令时间？(几十~几百)
2. cache line 多大 → 共享？不同线程写相邻变量为啥慢？
3. 什么时候数组转置/分块加速？为什么块大小别太离谱大？