存储层次

为什么需要层次

CPU 寄存器:  ~0.3 ns    几百字节
L1 Cache:    ~1 ns      32~64 KB
L2 Cache:    ~4 ns      256 KB ~ 1 MB
L3 Cache:    ~10 ns     8~64 MB（多核共享）
主内存:      ~80 ns     8~64 GB
SSD:         ~100 μs    ← 慢 1000 倍
机械硬盘:    ~10 ms     ← 慢 10 万倍
网络:        ~10~100 ms

速度差 3 个数量级，成本差也是——所以只能分级。

局部性原理（层次结构有效的前提）：

时间局部性：刚访问过的数据很快会再访问
空间局部性：访问了一个地址，附近地址很快会访问

Cache 的结构

地址: [Tag | Index | Offset]

      ┌──────────────────────┐
      │  Set 0: [way0][way1]...│   每个 way 是一行（cache line）
      │  Set 1: [way0][way1]...│
      │  ...                   │
      └──────────────────────┘

Cache line（缓存行）：内存和 cache 之间传输的最小单位，64 字节（x86）。

这是性能的关键：读一个 int 实际上会把周围 64 字节都加载进来 → 顺序访问极快。

三种 Miss（3C 模型）

类型	原因	解法
Compulsory（强制）	第一次访问必然 miss	预取
Capacity（容量）	工作集超过 cache 容量	减小工作集
Conflict（冲突）	多个地址映射到同一个 set	提高相联度、改变布局

替换策略

策略	特点
LRU	最久未用。理论好，硬件实现贵（需要计数器）
PLRU（伪 LRU）	用二叉树的位近似，硬件便宜
随机	最简单，实际效果接近 LRU
RRIP	现代 Intel 用，考虑"再引用距离"

写策略

策略	做法
Write-through	同时写 cache 和内存。简单但慢
Write-back	只写 cache，淘汰时才写回。快，但有一致性问题

现代 CPU 都用 write-back + MESI 协议保证多核一致。

对程序员的意义

// 慢：按列遍历，每次跳 1 行（跨 cache line）
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

// 快：按行遍历，顺序访问
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

$N = 4096$ 时差距可达 20 倍以上。

其他优化：

技巧	说明
分块（tiling / loop blocking）	把大矩阵切成 cache 能装下的小块
数组合并（AoS → SoA）	结构体数组 → 数组结构体，只加载需要的字段
对齐	让数据对齐到 cache line
避免伪共享	不同线程的数据不要在同一 cache line
预取	`__builtin_prefetch` 或硬件自动预取

// 坏：两个线程写相邻的变量，在同一 cache line → 反复失效
struct { int a; int b; } shared;      // 线程1 写 a，线程2 写 b

// 好：padding 到不同 cache line
struct { alignas(64) int a; alignas(64) int b; } shared;

症状：多线程反而比单线程慢。这是最难查的性能问题之一。