内存层级 入门

下面的数字是经典「Latency Numbers Every Programmer Should Know」 (Jeff Dean,~2009,按现代硬件更新)。跨越 10 个数量级。 右边那列是最有用的教学把戏:把 L1 命中当成 1 秒,所有其他操作按比例缩放。 DRAM 访问变成 100 秒;跨 DC 的 TCP packet 变成 19 天; 跨洲往返变成 16 年。

这张表是用来干啥的

记下这些数量级是基础。从中落出两种具体决策形状:

• 相邻层级之间的 100× 规则。层级往下每一步大致加 100 倍。 L1 → DRAM 是 100×、DRAM → SSD 又是 1000×、SSD → 跨洲又是 1000×。 这意味着把任何东西缓存到合适层级,工作时是 100–1000× 的胜利。
• 一次 DRAM 未命中等价于 ~100 条有用 ALU 指令。3 GHz 核稳态下每周期 3 条指令。100 ns miss = 300 周期 = ~900 条本可以在等待期间做的 独立无依赖工作。乱序执行能回收一部分,但不是全部 —— 而等待本身就是把内存受限负载下 IPC 拉到 1 以下的原因。

为啥右边那列比左边重要

原始 ns 数字不能自然映射到人类推理。我们对 1 ns vs 100 ns 没直觉 —— 两个都「瞬间」。 缩放到秒 vs 月,把差距捕捉成人脑每天处理的形状。 问「我会不会为它开车穿城」对应跨 DC RTT,成了可用的成本框架; 问「我会不会飞」对应跨洲 RTT 也是。 大多数性能设计错误都来自把这些距离按数量级低估。

这张表没显示的两个数字

带宽,而不是延迟。这张表是按操作的延迟。 每个层级的聚合带宽也值得知道:L1 ~1 TB/s、DRAM ~80 GB/s(单通道)、 NVMe ~7 GB/s、10 GbE NIC ~1 GB/s。跨 DRAM 的 memcpy 被带宽卡,不被延迟卡; 预取良好的数组迭代尽管有延迟,也能跑接近 DRAM 峰值带宽。

方差。延迟是一个分布,不是一个数。 DRAM 访问均值 100 ns,但在争用下尾值会拉得很高。 「NVMe SSD」100 μs 延迟是中位数;负载下的 99 分位可能高 10 倍。 右边那列对方差撒谎。对尾延迟敏感的系统,p99 数字才是重要的,不是中位数。

想象你可以随便设计内存。你想要它快(延迟低于 1 ns)、大(每片 TB 量级)、便宜(每 GB 1 美元)。每个约束单独都能实现;任意两个能;三个一起做不到。 层级是工程妥协 —— 给你一小撮「又快又贵」的内存挨着 ALU,加上大量「又慢又便宜」的内存, 软件得到「单一连续地址空间」的错觉。

约束 1:光速

光在真空中每纳秒走约 30 cm,在硅和铜里大约一半。 1 cm² 芯片一角到对角的信号要走 ~1 cm 往返,光速下已经是 0.1 ns。 穿过晶体管和线的实际信号传播延迟是这个的几倍。 离 ALU 几毫米以外的任何东西,延迟下限就是纳秒级。 ALU 边的 SRAM 单元之所以快,正是因为小到能放在近处; 封装另一边的 DRAM bank 已经远到「往返」成为主因。

约束 2:晶体管密度与刷新

SRAM(缓存用的技术)一个比特要 6 个晶体管。 DRAM(主存用的技术)一个比特要 1 个晶体管 + 1 个电容。 所以 DRAM 每平方毫米塞 ~10× 多比特,代价是需要每隔几毫秒刷新每个单元(电容漏电)、 访问慢 100 倍(因为每次读要通过小电容给 bit-line 充电)。

成本上:SRAM ~$100/GB、DRAM ~$5/GB、NAND flash(SSD)~$0.10/GB、磁盘 ~$0.02/GB。 每一层比上一层便宜大约 100 倍。如果按 SRAM 价格给机器配 1 TB L1 缓存,要花 1 亿美元; 配 1 TB 磁盘:20 美元。层级是让电脑能买得起的原因。

约束 3:热量预算

更快的内存意味着每字节存储更多功率,静态(空闲)和动态(访问)都是。 现代桌面 CPU 散热 ~150 W;服务器 CPU 300–400 W。 如果建一颗带 10 GB 缓存级 SRAM 的芯片,静态功耗就是千瓦量级 —— 没等任何程序跑起来,硅就熔了。层级让快的那层小到能装进封装的热量预算。

层级怎么化解

「小又快」叠在「大又慢」上面。每一级装的是它下一级的一个热子集。 CPU 的内存子系统对软件隐藏层级:一条 load 指令问一个地址, L1 先查;不在就 L2、然后 L3、然后 DRAM、然后(经过 OS 的缺页处理)磁盘。 程序的视角只有一份内存,硬件透明地在层级间搬字节。

包含 / 排斥(inclusion / exclusion)策略决定每级装什么:包含式的 L3 装 L1 和 L2 的超集(简化 coherence 但浪费容量);排斥式的 L3 只装内层缓存里没有的(总容量更大,代价是复杂的 coherence)。 现代 Intel 通常是包含式;AMD Zen 和 Apple 通常是排斥式或非包含式(弱化版本)。

层级与其说解决了问题,不如说让平均情况快。最坏情况(缓存冷、页表冷、磁盘寻道) 仍然是 §1 数字说的灾难。整个性能工作的游戏就是把热路径留在温的那层。

Cache line —— 传输的单位

缓存不从 DRAM 单字节加载。它加载 cache line —— 固定大小的块,在每一台现代常见 CPU(x86、ARM64、Apple Silicon、POWER)上都是 64 字节。 你读一个不在 cache 里的字节,硬件把含这个字节的整条 64 字节 line 都取回来。 再读 10 个地址外的另一个字节 —— 同一行、已缓存、免费。 再读 100 个地址外的另一个字节 —— 不同行、又一次完整传输。

这就是为啥空间局部性重要:一次 cache miss 已经付了 64 字节的钱, 把它们用完基本免费。在数组上顺序迭代,把一次 DRAM 访问摊到许多元素读上; 以大于 64 字节的步长迭代,每行只用 1 字节、浪费另外 63 字节。

Set associativity —— 一条 line 允许住哪

缓存有有限个槽位,要从大得多的内存里抽。新行来时,该放哪个槽?3 种策略:

• 直接映射(direct-mapped):每个内存地址映射到恰好一个槽 (由地址的某些位决定)。便宜、快,但碰到冲突未命中(两个热地址恰好映射到同一槽)时受罪。
• 全关联(fully associative):任何地址可以住任何槽。 命中率最高,但需要并行搜所有槽 —— 超过很小的缓存(16–32 项,像 TLB)就太贵。
• N 路组关联(N-way set-associative):实际的妥协。 缓存分成多个 set;每个地址映射到恰好一个 set; 在那个 set 里,它可以住 N 个 way 中的任一个。 现代 L1 通常 8 路,L3 是 16 路或更高。 查找在 N 个 tag 上并行比较 —— 硬件成本可控。

淘汰策略 —— set 满了时丢谁

一个 set 里 N 路全占了、新行又来时,得丢一个。 真正的 LRU(Least Recently Used)在「看不到未来」的策略里理论最优, 但精确跟踪 LRU 顺序要每个 set 用 log₂(N!) 位,对硬件太多。真实缓存近似它:

• Pseudo-LRU (PLRU):一棵位的二叉树,每个 set O(log N) 位, 近似 LRU 已经够好。
• Random:随机挑一路。便宜,意外地能打。
• NRU (Not Recently Used):每行带一个「用过」位;周期性清掉; 在「用过」位为 0 的行里挑一个淘汰。

工作集装得下缓存时,淘汰策略几乎不重要。装不下时,LRU 和 Random 的差距是个位数百分点。 决定输赢的因素是「工作集能不能装下」—— 见 locality 这一节。

硬件 prefetcher

CPU 一旦注意到顺序访问模式(连续行,或固定步长),就开始 prefetch —— 为程序还没要的行发出推测 load,赌它会要。现代 prefetcher 独立追踪多条流、 能检测跨几条 cache line 的步长模式、甚至在 TLB 配合下能跨页边界 prefetch。

prefetcher 是隐形的 —— 直到它不是。在数组上的线性扫描跑接近 DRAM 峰值带宽, 因为 prefetcher 让 cache 一直热。伪随机访问模式(链表遍历、哈希表探测)击败它: 没步长可检测,prefetcher 帮不上忙。 这就是「cache-friendly 数据结构」(数组、struct-of-arrays)在同样算法复杂度下 打过「cache-hostile」(链表、指针树)的技术原因。

TLB 简短一笔

每次内存访问都过虚拟 → 物理地址翻译。TLB(Translation Lookaside Buffer) 是最近翻译过的页表项的一个极小缓存(现代 Intel 核上 L1 ~64 项、L2 ~1500 项)。 翻译在 TLB 里没命中时,CPU 要在 DRAM 里走页表 —— x86-64 上 4 次内存读, 每次都可能 cache miss。TLB 是它自己的性能悬崖: 触碰 TLB 覆盖外的页的程序(默认 4 KB 页下工作集 > ~256 MB,或者大堆上的任何随机访问模式) 可能大部分时间在走页表、而不是在做实际数据访问。 virtual-memory primer 里有深入介绍。

缓存是赌「程序的访问模式不均匀」—— 最近用过的、附近用过的数据更可能再被访问。两种赌:

时间局部性(temporal locality)

你刚用过地址 X,大概率很快会再用。循环计数器、当前请求结构体、文件描述符表、 链表头指针 —— 都在很短的时间窗口里被反复敲打。 缓存替换策略(LRU 及近似)直接赌这个:留最近用过的,淘汰没碰的。

违反时间局部性的程序还是能跑 —— 只是一直 cache miss。 一个每次迭代碰一个新页、从不重访的循环,保证持续冲刷缓存,无论缓存多大。memset、memcpy、大 Bloom filter 哈希、 任何「扫一次就完」类型的负载,访问模式都是这样。 带宽,而不是缓存,是限制它们的因素。

空间局部性(spatial locality)

你用了地址 X,大概率很快用 X 旁边的地址。数组、结构体字段、协议头 —— 相邻项总是一起被碰。缓存利用这一点,一次 miss 传 64 字节、不是 1 字节。 所以读 URL 字符串里 1 字节,顺带把后面 63 字节免费拉进来; 读结构体第一个字段,通常也把接下来几个字段加载进来。

矩阵迭代 —— 经典演示

2-D C 数组 M[N][N] 是行主序存储:M[i][j] 在内存里挨着M[i][j+1];M[i+1][j] 在 N 个元素外。 按 for i: for j: 顺序迭代访问连续地址 —— 每次 miss 覆盖接下来 64 字节 (~8 个 double 或 16 个 float),prefetcher 启动。 按 for j: for i: 迭代,每步跳 N 个元素 —— 每次访问落在不同 cache line。

// 行主序(cache-friendly)               // 列主序(cache-hostile)
for (int i = 0; i < N; i++)              for (int j = 0; j < N; j++)
  for (int j = 0; j < N; j++)              for (int i = 0; i < N; i++)
    sum += M[i][j];                          sum += M[i][j];

4096×4096 的 double 矩阵(128 MB)上,错误顺序通常慢 5–10 倍, 尽管执行的指令条数完全相同。Fortran 默认列主序存储, 所以同样的循环在 Fortran 里 cache 行为相反。 这就是为啥 C 和 Fortran 之间的数值代码移植,有时候会无端调换循环顺序, 领域专家看不出原因。

Array-of-Structs vs Struct-of-Arrays

假设你有 100 万粒子,每个带位置(3 float)、速度(3 float)、颜色(3 float)。 两种存法:

// Array of Structs(AoS)—— 自然的 OOP 布局
struct Particle { vec3 pos, vel, color; };
Particle particles[1'000'000];

// Struct of Arrays(SoA)—— SIMD 友好
struct Particles {
    float pos_x[1'000'000], pos_y[1'000'000], pos_z[1'000'000];
    float vel_x[1'000'000], vel_y[1'000'000], vel_z[1'000'000];
    float color_r[1'000'000], color_g[1'000'000], color_b[1'000'000];
};

如果一个更新步骤只读位置和速度,SoA 每条 cache line 只带 6 float/粒子,带宽充分利用。 AoS 每粒子带全 9 float,即便颜色不需要 —— 浪费 30% 带宽。 SoA 还让编译器向量化容易很多(每个分量数组能用 SIMD 处理)。 游戏引擎、物理模拟器、每个 ML 框架的内层循环, 从 AoS 迁到 SoA,就是这个原因。

Cache-friendly vs cache-hostile 数据结构

• std::vector<T> 对几乎所有访问模式都打过std::list<T>,尽管很多操作算法复杂度一样。 vector 的连续存储让空间局部性自动;list 每元素带个指针,让每步遍历都可能是未缓存的 load。
• B 树在数据库里打过二叉搜索树,因为每个 B 树节点装在 1 个或几个 cache line (或页)里,每次比较一次性带回 64+ 个 key,而不是 1 个。 B 树基本就是「二叉树,只是 cache-aware」。
• 哈希表有很好的摊销复杂度,但 cache 行为多变。 开放寻址哈希表(Robin Hood、swiss table)在实际中打过链式哈希表, 因为所有项在一个连续数组里;链式每次冲突都是一次指针追踪。
• Cache-oblivious 算法(递归细分的矩阵乘法、van Emde Boas 树、funnel sort)不知道缓存参数的情况下也能拿到好的缓存性能 —— 通过把工作递归拆成所有大小的块。基本情形最终总能装进某层缓存,无论那层多大。

工作集悬崖

只要工作集装进某层缓存,性能平滑变化;一旦溢出,性能阶梯式下降。 在 32 MB L3 缓存的芯片上跑 30 MB 工作集的负载接近峰值; 同样负载 34 MB 工作集,每次访问掉到 DRAM 速度。 悬崖很陡,因为缓存未命中率在工作集大小很小一段范围里从 ~0% 升到接近 100%。

实际推论:Linux 上 perf stat -e cache-misses,LLC-load-misses立刻告诉你热循环是否装在缓存里。如果 LLC miss 率高,要么缩工作集、要么改访问模式、 要么接受 DRAM 受限的性能。

Code review 红旗

• 热内层循环里的链表遍历。每一步都是一次潜在的未缓存指针 load。 换成连续容器,或者接受代价。
• 用 Array of Pointers (AoP) 而 Array of Structs 就够用。std::vector<std::unique_ptr<T>> 在 std::vector<T>可用时,意味着每次访问是两条 cache line 而不是一条。
• 哈希表 probe 之间局部性差。紧凑循环里的链式哈希表; 考虑开放寻址(Robin Hood、swiss table)。
• 步长是 cache-set 大小倍数的步长访问。在行主序矩阵里连续访问多个 M[i][0],而行的字节数是 L1 set 大小的倍数, 会反复打到同一 set、把它的 N 个 way 耗尽 —— 冲突未命中。 给行 pad 一条 cache line 就打破这个模式。
• 工作集恰好超过 LLC 大小。一个比必要大 5% 的结构体能把工作集推下悬崖。 压紧结构体字段、把冷字段移到单独的结构体、或者用更小的类型。