内存层次与缓存

把一个 4096 × 4096 的 float 矩阵所有元素加起来，按行遍历和按列遍历，做的加法完全一样多，结果也一样。在本机（Apple M3，clang -O2）上：

for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) s += a[i*N + j];  // 按行
for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) s += a[i*N + j];  // 按列

row-major  (i,j): 0.022 s
column     (j,i): 0.097 s

慢了 4 倍多。上一篇的 CPU 模型解释不了这个差距：指令数一样，依赖链一样。差别全在数据从哪里来。这一篇从测出来的延迟数字开始，一步步推出 cache 为什么存在、长什么样、怎么写代码才能让它帮你。

前置：机器级程序、信息的表示

一次读内存到底要多久

先直接量。构造一个随机排列的指针链：数组里每个元素存着下一个要访问的下标，cur = p[cur] 一直跳下去。每次读都依赖上一次的结果，CPU 没法提前或并行地取，测出来的就是纯粹的访问延迟。改变数组大小：

// 随机指针链：每次访问依赖上一次结果，测的是纯延迟
for (long s = 0; s < steps; s++) cur = p[cur];

     16 KB:   1.88 ns/load
     64 KB:   1.85 ns/load
    256 KB:   6.05 ns/load
   1024 KB:   8.59 ns/load
   4096 KB:  10.25 ns/load
  16384 KB:  17.92 ns/load
  65536 KB: 138.92 ns/load
 262144 KB: 184.77 ns/load

这条曲线不是平滑的，而是一级一级的台阶。对照本机的硬件参数（sysctl）：性能核的 L1 数据 cache 128 KB，L2 cache 16 MB，cache 行 128 字节。

• 数据 ≤ 64 KB：约 1.9 ns，全在 L1 里，大约 6 个周期。
• 256 KB 到 16 MB：6 到 18 ns，超出 L1 但还在 L2 里。台阶内部继续缓慢上升，部分原因是地址翻译用的 TLB 也开始不够用（见 虚拟内存）。
• 64 MB 以上：140 到 185 ns，大部分访问都要去 DRAM 主存。

L1 和主存差了约 100 倍。对 CPU 来说，一次主存访问的时间够它执行几百条算术指令。这就是存储层次（memory hierarchy）：

层级	典型容量	典型延迟	由谁管理
寄存器	几百字节	< 1 ns	编译器
L1 cache	几十到一百多 KB	~1 ns	硬件
L2/L3 cache	几 MB 到几十 MB	几到几十 ns	硬件
DRAM 主存	几 GB 到几百 GB	~100 ns	操作系统（虚拟内存）
SSD	TB 级	~10–100 μs	操作系统（文件系统与 IO）
网络 / 远程存储	无上限	ms 级	应用

为什么不全部用最快的存储？因为速度、容量、成本不可兼得。L1 由 SRAM 构成，每位需要 6 个晶体管，又必须靠近执行单元，做不大；DRAM 每位只需要 1 个晶体管加 1 个电容，密度高、便宜，但电容要充放电、要定期刷新，而且物理上离 CPU 远。于是每一层都是下一层的缓存：小而快的层存放大而慢的层里”最可能马上用到”的那部分数据。

这个设计能成功，前提是”最可能马上用到”真的能猜准。

局部性：为什么 cache 能猜准

程序的访存不是随机的。CSAPP 把这种规律总结为局部性（locality），分两种：

• 时间局部性：刚访问过的数据，很可能很快再被访问。循环变量、累加器、频繁调用的函数代码。
• 空间局部性：访问了某个地址，很可能很快访问它附近的地址。顺序遍历数组、顺序执行指令。

硬件针对这两点各有一招。对时间局部性：把访问过的数据留在 cache 里，下次直接命中。对空间局部性：每次从主存搬数据时不只搬一个字节，而是搬一整块，叫 cache 行（cache line）。x86 上通常是 64 字节，Apple M 系列是 128 字节。

现在开头的实验就能解释了。float 是 4 字节，一个 128 字节的行装 32 个元素。按行遍历时，第一次访问 a[0] 未命中，把 a[0..31] 整行搬进来，接下来 31 次访问都命中，未命中率约 1/32。而且访问是顺序的，硬件预取器（prefetcher）能识别这种模式，在你用到之前就把后面的行提前搬来，连那 1/32 的延迟也被藏掉了。

按列遍历时，相邻两次访问 a[i*N + j] 和 a[(i+1)*N + j] 相隔 N * 4 = 16 KB。每次访问落在不同的行上，搬进来的 128 字节只用了 4 字节。一列 4096 个元素要占 4096 个行、512 KB，超过了 L1，等回过头来访问下一列时，上一列搬进来的行早被挤掉了。空间局部性全部浪费。

一个数组访问的步长（stride）是衡量空间局部性的直接指标：步长为 1 最好，步长越大，每行利用率越低，直到每次访问都是一次未命中。可以直接量出来：对一个 256 MB 的 long 数组按不同步长求和，统计”真正用到的数据”的吞吐：

for (long i = 0; i < n; i += stride) s += p[i];

stride  1:   0.48 ns/elem, useful  16.8 GB/s (s=4)
stride  4:   0.64 ns/elem, useful  12.5 GB/s (s=5)
stride 16:   3.64 ns/elem, useful   2.2 GB/s (s=0)
stride 64:   4.63 ns/elem, useful   1.7 GB/s (s=4)

步长 16 个 long 正好是 128 字节，即每个元素独占一个 cache 行。从这里开始，每读 8 字节有用数据，内存系统都要搬 128 字节，有效吞吐跌到步长 1 时的八分之一以下；步长再大，每元素耗时也基本不再增加，因为”每次访问一行”已经是最坏情况。步长 1 和 4 差距不大，是因为步长 4 时每行仍有 4 个元素被用到，而预取器对固定步长同样有效。

注意每元素耗时（3.6 ns）远低于指针链实验里主存的 140 ns。两者都在访问主存，差别在于这里下一个地址不依赖当前数据，许多请求可以同时在路上。这个区别是最后一节”延迟与带宽”的主题。

停一下，检查理解单选

Apple M3 的 cache 行是 128 字节。顺序遍历一个很大的 double 数组（8 字节一个），只考虑冷启动、不考虑预取，未命中率约为多少？

1/81/161/1280，因为数组是连续的

检查答案

cache 的结构：一个地址被拆成三段

cache 怎么知道某个地址的数据在不在自己里面？它不能像哈希表那样随便存，查找必须在一两个周期内用纯硬件完成。CSAPP 用三个参数描述一个 cache：

• S 个组（set），
• 每组 E 行（E 叫相联度，associativity），
• 每行 B 字节数据。

总容量 C = S × E × B。每行除了 B 字节数据，还有一个有效位和一个标记（tag）。

查找时，硬件把地址拆成三段：

| tag (t 位) | set index (s 位) | block offset (b 位) |

其中 B = 2ᵇ，S = 2ˢ。最低 b 位是数据在行内的偏移；中间 s 位选出这个地址只能去的那一组；剩下的高位是 tag，用来在组内的 E 行里比对。命中的条件是：组里某一行有效且 tag 相同。

举个具体的数：一个 32 KB、8 路组相联、64 字节行的 cache，有 S = 32 KB / (8 × 64 B) = 64 组，于是 b = 6、s = 6。地址 0x12345678 的低 6 位是 0x38（行内第 56 字节），接下来 6 位是 25（第 25 组），剩下的高位 0x12345 是 tag。硬件拿 25 号组里 8 行的 tag 同时和 0x12345 比较，任一行有效且相等就命中，再用偏移 56 从这一行里取出数据。整个过程只有位选择和 8 个并行比较器，没有任何循环，所以能在几个周期内完成。

为什么用中间几位当组号，而不是最高几位？因为空间局部性：相邻的行地址只在中间位上不同，用中间位做索引，一段连续的数组会被均匀撒到所有组里；如果用高位做索引，连续的一大段内存全会挤进同一组。

E 的取值决定了 cache 的类型：

• 直接映射（E = 1）：每组一行。查找只需比一次 tag，电路最简单最快；但两个地址只要组号相同，就会互相踢出。
• E 路组相联（1 < E < C/B）：每组 E 行，同组最多容纳 E 个不同的行，满了按某种策略（通常是近似 LRU）替换。硬件要并行比较 E 个 tag。
• 全相联（S = 1）：只有一组，任何行可放任何位置，没有冲突，但比较器的成本随行数线性增长，只用于很小的结构（如 TLB）。

现代 CPU 的 L1 一般是 8 到 12 路组相联，L2/L3 是 12 到 16 路。L1 通常还分成两块：指令 cache 和数据 cache，因为取指和读写数据在流水线的不同阶段同时发生（见 机器级程序），分开后两者互不争抢端口；从 L2 开始指令和数据共用。多核芯片上 L1、L2 往往是每个核（或每组核）私有的，最后一级 cache 由所有核共享，所以一个程序独占机器时跑得快，旁边再跑一个吃内存的进程就会变慢，哪怕 CPU 核数够用。

三种未命中与冲突的代价

未命中可以按原因分成三类，每类的解法不同：

• 冷未命中（compulsory）：第一次访问某行，必然未命中。只能靠预取掩盖。
• 容量未命中（capacity）：工作集比 cache 大，再怎么放都装不下。按列遍历大矩阵就是这一类，解法是改变访问顺序缩小工作集。
• 冲突未命中（conflict）：cache 明明还有空位，但几个频繁使用的行恰好映射到同一组，互相踢出。这是组相联要解决的问题。

冲突未命中最反直觉，用一个小模拟器看。设 cache 大小 1 KB、行 32 字节，两个各 1 KB 的数组 x、y 紧挨着放（相差恰好 1024 字节），交替读 x[i] 和 y[i]，就像计算点积：

from collections import OrderedDict
def simulate(addrs, S, E, B):
    sets = [OrderedDict() for _ in range(S)]   # 每组内用 LRU 顺序
    hits = 0
    for a in addrs:
        blk = a // B; s = blk % S; tag = blk // S
        line = sets[s]
        if tag in line: hits += 1; line.move_to_end(tag)
        else:
            if len(line) == E: line.popitem(last=False)
            line[tag] = True
    return hits, len(addrs)
# x 和 y 各 1024 字节，相隔恰好 1024：x[i] 和 y[i] 落进同一组
x, y = 0, 1024
trace = [a for i in range(0, 1024, 4) for a in (x + i, y + i)]
for S, E in [(32, 1), (16, 2)]:
    h, n = simulate(trace, S, E, 32)
    print(f"S={S:2} E={E} (1KB, 32B 行): 命中 {h}/{n} = {h/n:.1%}")

S=32 E=1 (1KB, 32B 行): 命中 0/512 = 0.0%
S=16 E=2 (1KB, 32B 行): 命中 448/512 = 87.5%

直接映射时，x[i] 和 y[i] 的地址相差 1024 = S × B，中间的组号位完全相同，tag 不同。读 x[0] 把 x 的行搬进组 0，读 y[0] 把它踢走，再读 x[1] 又把 y 踢走。命中率是 0，这种现象叫抖动（thrashing）。容量不是问题：总共只用到两行，cache 有 32 行。

同样 1 KB 换成 2 路组相联，同一组能同时放下 x 和 y 的行，每行 8 个 float 里只有第一次未命中，命中率回到 7/8 = 87.5%。

真实代码里，这种事最容易出现在大小是 2 的幂的数组上。矩阵的行长若是 4096 个 float（16 KB），按列访问时每个元素的地址相差 16 KB，低位全部相同，很可能映射到少数几个组，相联度再高也装不下。常见的修正是填充（padding）：把行长声明成 4096 + 16，打破这种对齐。

写操作还有一层选择：写命中时，是立刻写回下一层（write-through），还是只标记这一行为”脏”，等它被替换时再写回（write-back）；写未命中时，是先把行读进 cache 再写（write-allocate），还是绕过 cache 直接写下层。现代 CPU 的数据 cache 基本都是 write-back + write-allocate，因为对同一行的多次写只付一次写回的代价。多核之间如何保证各自 cache 里的副本一致（cache 一致性协议），以及两个线程写同一行不同变量时的伪共享（false sharing），归 并发与同步。

停一下，检查理解多选

一个 64 KB、4 路组相联、64 字节行的 cache。下面哪些说法正确？

它有 256 个组地址的最低 6 位是行内偏移，接下来 8 位是组号地址相差 16 KB 的两个字节一定落在不同的组只要工作集小于 64 KB，就不可能发生未命中

检查答案

cache 友好的代码：矩阵乘法

理解了 cache 的工作方式，最经典的应用是矩阵乘法 C = A × B。三重循环有 6 种嵌套顺序，算术量都是 2N³ 次浮点运算，但访存模式完全不同。对比两种（N = 1024，double，-O2）：

// ijk：内层沿 k 走，A 按行、B 按列
for (i) for (j) { double s = 0; for (k) s += A[i][k] * B[k][j]; C[i][j] = s; }
// ikj：内层沿 j 走，B 和 C 都按行
for (i) for (k) { double r = A[i][k]; for (j) C[i][j] += r * B[k][j]; }

ijk: 2.17 s  C[7][9]=356277760
ikj: 0.25 s  C[7][9]=356277760

结果一样，快了近 9 倍。分析内层循环：

• ijk：A[i][k] 沿行走，步长 1，很好；B[k][j] 沿列走，步长是一整行 8 KB，每次访问都是一个新的行。B 有 8 MB，远大于 L1，每次内层循环都要把 B 的一整列重新从更低层拉上来。
• ikj：r = A[i][k] 在内层循环里是常数，放在寄存器里；B[k][j] 和 C[i][j] 都沿行走，步长 1，每个 cache 行被完整用完，预取器也很开心。顺带地，内层是对两个连续数组做 C += r * B，没有跨迭代依赖，编译器能把它向量化成 SIMD 指令，这也贡献了一部分加速。

CSAPP 对 6 种顺序做过系统分析：内层循环中每次迭代的未命中数，jki/kji 最差（两个列访问），ijk/jik 居中，kij/ikj 最好。一个可以直接记住的经验法则是：让最内层循环沿着连续内存走。

停一下，检查理解单选

矩阵乘 C = A × B 的 kji 顺序（最内层沿 i 走）的内层循环是 C[i][j] += A[i][k] * r，其中 r = B[k][j]。它的 cache 表现最接近哪一种？

和 ikj 一样好，因为也把一个元素提到了寄存器最差的一类，因为 A[i][k] 和 C[i][j] 在内层都按列访问和 ijk 一样，只有一个数组按列访问无法判断，取决于 N 是否为 2 的幂

检查答案

分块：把工作集塞进 cache

ikj 已经让每个 cache 行被充分利用，但还有一个问题：对每个 i，内层要扫过整个 B 矩阵（8 MB），这个工作集远大于 L1 甚至 L2，B 的每个元素被 N 次重复从下层读上来，时间局部性没利用上。

分块（blocking / tiling）把矩阵切成 b × b 的小块，按块做乘法：

for (ii = 0; ii < N; ii += b)
  for (kk = 0; kk < N; kk += b)
    for (jj = 0; jj < N; jj += b)
      // 只在 A[ii..ii+b][kk..kk+b]、B[kk..][jj..]、C[ii..][jj..] 三个小块上做 ikj

只要三个 b × b 的块能同时放进 cache（b = 32 时，3 × 32 × 32 × 8 B = 24 KB），每个块被搬进来之后就会被反复使用 b 次才离开。对 A 和 B 每个元素的平均访存次数从约 N 次降到约 N/b 次。

转置是更纯粹的例子，因为它没有任何计算，只有搬运。对 4096 × 4096 的 double 矩阵，朴素写法和 32 × 32 分块写法：

for (i) for (j) T[j][i] = M[i][j];                          // 朴素：T 按列写
for (ii += BS) for (jj += BS)                               // 分块：一次处理一个 32x32 子块
  for (i = ii; i < ii+BS; i++) for (j = jj; j < jj+BS; j++) T[j][i] = M[i][j];

naive   transpose: 0.194 s (T[5][7]=28677)
blocked transpose: 0.115 s (T[5][7]=28677)

（第二次运行是 0.252 s 对 0.159 s，绝对时间有波动，比例稳定在 1.6 倍左右。）朴素版里，T 的每次写入跨越 32 KB，写完一行 M 要碰到 4096 个不同的 cache 行，回到下一行时它们早已被挤出；分块版在子块内只碰 32 个 T 的行，它们在 cache 里停留到被完整写满。加速没有矩阵乘那么夸张，是因为转置本身的访存量是固定的 2N² 次，分块能省掉的只是重复搬运，而写满一整行这件事无论如何都要做。

块大小 b 怎么选？要求是参与的几个子块能同时放进目标 cache，又不能太小，否则循环开销和行内浪费会变大。b 取 2 的幂且让一行子块恰好是 cache 行的整数倍，是常见起点，最终仍要靠实测；高性能库会在安装或启动时自动搜索这个参数。

这个思想的推广远远超出矩阵乘：

• 算术强度（arithmetic intensity）= 计算量 / 访存量。矩阵乘的计算量是 O(N³)，数据只有 O(N²)，理论上每个数可以复用 O(N) 次，所以它能做到”计算受限”；而向量加法每读两个数只算一次，再怎么优化也是”访存受限”。分块就是在把理论上的复用变成实际的复用。这个比值配合硬件的峰值算力和带宽，就是 roofline 模型，在 GPU 与 Kernel 里展开。
• BLAS 库（OpenBLAS、Apple Accelerate、MKL）对 L1、L2、L3 和寄存器各做一层分块，再加上 SIMD，比上面的 ikj 还能快一个数量级。PyTorch 在 CPU 上的 matmul 就调用这些库。
• GPU 上的矩阵乘 kernel 把块搬进 shared memory，FlashAttention 把 attention 也做成分块计算，让 N × N 的中间矩阵根本不写回显存，见 FlashAttention。

停一下，检查理解单选

二维数组 double M[N][N] 在 C 里按行优先存储。要对它做转置 T[j][i] = M[i][j]，内层循环无论沿 i 还是沿 j，都会有一个数组按列访问。下面哪种思路能同时改善两边的局部性？

换成 float 让数组变小一半改成内层沿 i、外层沿 j分块：每次处理一个小的 b × b 子块，让 M 和 T 的对应子块都能同时放进 cache增大 cache 行，让一次读取包含更多元素

检查答案

延迟与带宽：两个不同的瓶颈

到目前为止只讨论了延迟（latency）：一次访问等多久。存储系统还有另一个维度：带宽（bandwidth），单位时间能搬多少字节。两者经常被混淆，但对应完全不同的优化方法。

指针链实验测的是延迟：每次访问都依赖上一次，同一时刻只有一个请求在路上，主存的 140 ns 一点都没被隐藏。顺序扫描数组则不同，下一个地址不依赖当前数据，CPU 的乱序执行和预取器可以同时发出几十个未完成的请求，访存时间相互重叠。这时速度由带宽决定，现代台式机 DRAM 带宽通常是几十到一百多 GB/s，Apple M 系列的统一内存带宽从 100 GB/s 到 800 GB/s 不等。

一个简化的关系（Little 定律）把两者联系起来：带宽 = 在途请求数 × 每个请求的字节数 / 延迟。延迟 100 ns、每个请求 128 字节，要跑满 100 GB/s，需要同时约 80 个请求在路上。单线程的链式访问只有 1 个在途请求，只能拿到约 1 GB/s，这就是链表、树、哈希表随机查找比数组扫描慢得多的根本原因：它们的访问模式天然是”下一个地址取决于这一个的内容”。

所以优化方向要先判断瓶颈：

• 受延迟所限（指针追逐、随机访问）：改数据结构，让相关数据放在一起（数组代替链表、B 树代替二叉树，见 数据结构、数据库系统）；或者软件预取、增加并发请求。
• 受带宽所限（大数组顺序扫描）：减少搬运的字节数，例如用更低的精度（fp32 换 bf16，见 信息的表示），或者把多个操作合并成一次遍历（kernel fusion）。

LLM 推理的 decode 阶段就是典型的带宽受限：每生成一个 token，要把全部权重和 KV cache 从显存读一遍，而计算量很小，所以吞吐几乎完全由显存带宽决定，这部分的定量分析归 推理系统。

停一下，检查理解多选

一段代码遍历一个 1 亿个节点的链表求和，比遍历同样大小的数组慢几十倍。下面哪些解释正确？

链表节点在内存中通常不连续，每个节点很可能落在不同的 cache 行，空间局部性差下一个节点的地址要读完当前节点才知道，CPU 无法同时发出多个访存请求，延迟无法被重叠链表需要执行更多的加法指令主存带宽被链表节点里的指针字段占满了

检查答案

记住这三件事

1. 存储层次的每一层比上一层大而慢：L1 约 1 ns，主存约 100 ns，相差两个数量级；cache 能起作用，全靠程序的时间局部性和空间局部性。
2. cache 按行（64 或 128 字节）搬数据，按地址中间几位选组、高位比 tag；步长为 1 的访问用满每一行，2 的幂步长容易引发冲突未命中。
3. 写 cache 友好代码的要领是让内层循环沿连续内存走、用分块把工作集塞进 cache；先判断是延迟受限还是带宽受限，再决定优化方向。

延伸阅读

• Bryant & O’Hallaron, Computer Systems: A Programmer’s Perspective, 第 6 章 The Memory Hierarchy
• CMU 15-213 讲义 Cache Memories 与 Cache Lab：https://www.cs.cmu.edu/~213/
• Ulrich Drepper, What Every Programmer Should Know About Memory（2007）：https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
• Jeff Dean 等整理的 Latency Numbers Every Programmer Should Know
• Samuel Williams 等, Roofline: An Insightful Visual Performance Model for Multicore Architectures（CACM 2009）