存储层次与延迟阶梯:为什么顺序访问快 100 倍

一个让人不舒服的事实:你的 CPU 大部分时间在等内存

我们在 ch00-01 立下过那个命题:std::vector 的二分查找(O(log n))能在中等规模下打败 std::set 的查找(也是 O(log n)),复杂度相同,性能差一个数量级。当时一句话带过的原因是「vector 连续缓存友好、set 节点分散 cache miss」。这一章我们把这个「缓存友好」彻底拆开,它背后是现代 CPU 一个冰冷的物理事实:CPU 算得飞快,但数据搬不过来。

具体到数字,一颗当代 CPU 流水线每周期可以退休多条指令,而跑到主存(DRAM)取一个数据要花上百个周期。也就是说,只要你的数据不在 cache 里,CPU 就得干等上百个周期,算力根本用不上。Brendan Gregg 把这种现象叫做「CPU 是喷气式发动机,内存是自行车」,发动机再猛,被自行车拖着也快不起来。

理解这件事的前提,是先建立存储层次(hierarchy)的精确图像:数据离 CPU 越近,越小越贵越快;越远,越大越便宜越慢。这一篇我们就用本机实测把这张「延迟阶梯」画出来,然后讲清楚它怎么决定你写 C++ 时的每一个布局决策。

存储层次:一层快但小,下一层慢但大

先上一张「教科书 + 本机实测」对照表。延迟数字给量级(随架构和频率变化),但比例关系是稳定的,这才是要记的:

层	典型延迟(周期)	本机实测(ns)	容量(本机 AMD Ryzen 7 5800H)
寄存器	0 周期	—	通用寄存器若干,编译器分配
L1 cache(数据)	~4 周期	~1.2	32 KB,每核私有
L2 cache	~14 周期(Zen3)	~3–9	512 KB,每核私有
L3 cache	~47 周期(Zen3)	~11–60	16 MB,全核共享
主存 DRAM	~200–400 周期	~120	几十 GB

周期数取自 Agner Fog《The microarchitecture of Intel, AMD and VIA CPUs》第 23 章 AMD Zen 3(Table 23.1:L1=4、L2=14、L3=47 周期);ns 为本机 5800H 实测的指针追逐结果(见下文)。

把这张表竖着看,你会得到本卷最重要的一组比例:L1 命中约 1 纳秒,DRAM 取数约 120 纳秒,差了整整 100 倍,也就是两个数量级。 这是「为什么顺序遍历比随机快两个数量级(延迟上)」的物理根基:顺序访问把后续数据提前拉进 cache,随机访问每次都 cold miss,只能去 DRAM 现取。

讲到这里,先别急着信我的话,我们把这张阶梯亲手测出来。

上手跑一跑:本机实测延迟阶梯

测延迟最干净的办法是指针追逐(pointer chasing):在内存里铺一条「下一个地址藏在当前数据里」的环形链,让 CPU 走完它。关键在于下一个地址依赖当前这次 load 的结果,这是真依赖,硬件预取器没法提前猜(它不知道下一个要访问哪),所以测出来的就是裸访存延迟。

核心循环就这么几行(完整程序见本章代码 memory_mountain.cpp):

cpp

// 构造一条贯穿全部节点的置乱单环:nxt[perm[i]] = perm[(i+1) % n]
std::vector<long> nxt(elems);
for (long i = 0; i < elems; ++i) nxt[perm[i]] = perm[(i + 1) % elems];

long idx = 0;
auto t0 = std::chrono::steady_clock::now();
for (long s = 0; s < total_steps; ++s) {
    idx = nxt[idx];            // 下一个地址依赖本次 load → 真依赖,预取器束手无策
    sink = sink + g_data[idx]; // 读 data[idx],制造链上的依赖
}
auto t1 = std::chrono::steady_clock::now();

把工作集(数组大小)从 4 KB 扫到 128 MB,跨越 L1/L2/L3/DRAM 各级边界,每次都让它把整个工作集「踩」一遍,我本机(taskset -c 0 绑核 0 降噪,WSL2 环境)跑出来的结果是:

text

===== B. 指针追逐随机读延迟 (ns/访问) =====
      size      elems  ns/access level(推断)
       4K        512       1.19          L1d
       8K       1024       1.18          L1d
      16K       2048       1.24          L1d
      32K       4096       2.50          L1d     ← 工作集 = L1d 容量(32K),开始溢出
      64K       8192       3.33          L2
     128K      16384       4.04          L2
     256K      32768       6.02          L2
     512K      65536       8.88          L2      ← 工作集 ≈ L2 容量(512K),开始溢出
    1024K     131072      11.42          L3
    2048K     262144      12.40          L3
    4096K     524288      22.59          L3
    8192K    1048576      59.99          L3
   16384K    2097152      96.27          L3      ← 工作集 = L3 容量(16M),剧烈颠簸
   32768K    4194304     135.92         DRAM
   65536K    8388608     118.59         DRAM
  131072K   16777216     122.06         DRAM

这张表值得停下来读一会儿。它讲了一个非常清晰的故事:

4K–16K:全在 L1,~1.2 ns。 这就是「热缓存」的样子,数据就贴着计算单元。注意 1.2 ns ÷ 4 周期 ≈ 3.3 GHz,正好是 5800H 的基频运行点,跟 Agner 给的 L1 = 4 周期严丝合缝对上了。
32K:开始抬头(2.5 ns)。 工作集正好等于 L1d 容量(32 KB),装不下了,部分访问被挤到 L2。这就是 cache「溢出」的临界点。
64K–512K:进 L2,3–9 ns。 干净的 L2 区,但延迟随工作集增大往上爬,因为工作集越接近 L2 容量,冲突/容量 miss 越多。
1M–16M:进 L3,11–60 ns。 注意 16M 那一行 96 ns,L3 颠簸区的典型表现(工作集 = L3 容量,疯狂互相驱逐)。
32M 以上:DRAM,~120 ns。 阶梯到此彻底跌到底。

L1 的 1.2 ns 和 DRAM 的 120 ns,正好差 100 倍。这不是教科书上的比喻,是你手上这台机器的物理事实。

笔者这里要提醒一句:我跑这台机器是 WSL2(虚拟机),CPU 频率被宿主管着,读不到 governor,绝对 ns 会有百分之几的抖动。但各级之间的比例关系(L1≈1、L2≈几个、L3≈几十、DRAM≈上百 ns)是硬件决定的,稳得很。性能文章里真正可信的是比例,不是某个绝对数。

memory mountain:把局部性画成一座山

延迟阶梯只回答了「访问延迟随工作集怎么变」这一个维度。CSAPP 第 6 章那个著名的**memory mountain(内存山)**多加了一个维度,步长(stride),于是空间局部性和时间局部性被同时摊在一张表上,信息密度更高。

它的做法是:固定一个工作集 size,以不同 stride 顺序环形读数组,测吞吐(GB/s)。stride 越小,相邻两次访问越可能落在同一缓存行(空间局部性);size 越小,数据越可能还在 cache 里(时间局部性)。本机实测:

text

===== A. memory mountain: 读吞吐 (GB/s) =====
size\stride(B)    8B    16B    32B    64B   128B   256B   512B
      1K        16.9   17.0   17.0   16.7   16.1   16.5   15.3
      8K        16.9   16.6   17.0   17.2   17.1   17.0   17.1
     32K        16.8   16.9   16.9   16.9   16.8   17.2   16.5   ← L1d 边界
     64K        16.7   16.9   17.2   16.7   16.8   16.6    7.3
    256K        17.2   17.2   17.2   16.6   16.6   16.7    7.6   ← L2 区
    512K        16.7   16.8   16.6   14.3   11.3   11.6    5.3   ← L2 边界
   1024K        16.7   16.6   16.2   12.9    8.7   11.1    4.5
   4096K        16.5   16.9   16.3   12.9    8.1   10.1    4.4   ← L3 区
  16384K        13.0   10.5    7.7    3.8    3.1    3.1    2.9   ← L3 边界,跌了
  32768K        14.5   11.0    6.7    3.8    2.7    2.6    2.1   ← 进 DRAM

怎么读这张山?盯住两个方向:

沿「左列」往下看(stride = 8B,顺序连续访问):哪怕工作集已经 32 MB(远超 L3),吞吐还有 14.5 GB/s,跟 1 KB 时几乎一样。这是**硬件预取器(prefetcher)**的功劳:它检测到「你在按固定步长顺序扫内存」,就提前把后面的缓存行拉进 cache。换句话说,顺序访问哪怕在 DRAM 上也能逼近 L1 的吞吐,因为预取器把延迟藏起来了。这是「顺序遍历快」的真正机制,下面会展开。

沿「右下角」看(stride = 512B,工作集 32 MB):吞吐崩到 2.1 GB/s,比左上角的 17 GB/s 差了 8 倍。stride 512B 意味着每次访问踩一个新缓存行、而且步长太大预取器追不上(它一般只能预取有限条流),于是每次访问都是一次近乎随机的 DRAM 取数。这才是 DRAM 的真面目:顺序起来很快,随机起来极慢。

把这张山和前面的延迟阶梯合起来看,结论是同一组:存储层次的快慢同时取决于「数据在不在 cache 里」(时间局部性)和「访问是不是连续的」(空间局部性)。前者由工作集大小决定,后者由访问模式决定。两者都好,跑出 L1 的速度;两者都差,跌到 DRAM 的零头。

回到 C++:这些数字在告诉我们什么

硬件知识不为炫技,为的是指导写代码。从这张阶梯里能直接翻译出几条 C++ 布局原则,我们一条条对应:

1. 数据连续存放,优先用连续容器。 这是最直接受益于空间局部性的一条。std::vector / std::array 把元素紧凑排在一块连续内存,遍历时一个缓存行(64 字节)能装好几个元素,预取器还帮你提前拉,这就是 vector 遍历快的根因。反过来,std::list / std::set 的节点各自 new 出来、散落在堆各处,指针追逐就是上面延迟阶梯里那条最慢的曲线。复杂度相同,布局不同,性能差一个数量级。 这条 ch00-01 已经用 vector 二分 vs set 查找实测过,这里补上了它的物理根据。

边界提醒:vector 内部「三指针、扩容策略(2 倍增长)、insert/erase 的元素搬移成本」这些设计层面的内容归 vol3 讲(它回答「vector 为什么这么设计」)。vol6 只回答「在硬件上跑时,连续布局为什么快」,就是我们这张延迟阶梯。

2. 把热数据集控制在 L3 以内。 延迟阶梯显示,工作集一旦超过 cache 容量,延迟就从纳秒级跳到几十上百纳秒。一个很实际的推论:经常被反复扫描的数据,要让它「装得进 cache」。比如一个被高频查询的表,如果 20 MB,5800H 的 L3 只有 16 MB,每次查询都在颠簸;如果能压到 12 MB 以内,性能可能直接翻几倍。这不是玄学,是表上 16M 那一行(96 ns)和 4M 那一行(22 ns)的差距。

3. 随机访问场景,换能降低访存次数的结构。 链表/平衡树每次跳一个节点就是一次潜在 cache miss(节点分散)。工程上常见的折中是把树拍扁:用 B-tree / B+ tree 替代二叉平衡树,每个节点存几十上百个键(塞满一两个缓存行),树高骤降,miss 次数随之骤降。这就是为什么数据库索引、文件系统全用 B+ 树而不是红黑树,不是为了省指针,是为了省 cache miss。std::set 在数据量大、查询密集的场景被 B-tree 花式吊打,根因就在这。

4. 容量先 reserve,别让扩容打散布局。 这条偏 C++ 工程实践:vector 反复 push_back 触发扩容,会把整块数据搬到新内存,旧 cache 全失效,而且搬本身就是一次大开销。提前 reserve(估计容量) 能避免这件事。具体的扩容机制(为什么是 2 倍、搬一次的成本)归 vol3,这里只记结论:热路径上的 vector,提前 reserve。

留给下一篇的线头

这一篇我们用指针追逐画出本机的延迟阶梯(L1 ~1 ns、L2 ~几个 ns、L3 ~几十 ns、DRAM ~120 ns,逐级 100 倍鸿沟),用 memory mountain 看清空间局部性(stride)和时间局部性(size)怎么共同决定吞吐。由此翻译出的 C++ 原则,用连续容器、控热数据集、随机访问换 B-tree、reserve,都是这套数字的直接推论。

但有两个细节我们刻意绕过去了:那个反复出现的「64 字节」到底怎么算出来的(为什么 L1 表里 32K 是边界?为什么 stride 64B 是个坎?),以及「缓存行」作为 cache 最小单位带来的那些反直觉代价(比如两个不相关的变量挤在同一行会互相踢)。这正是下一篇的主题。

还有一件大事留在更后面:这一章只讲了「数据在哪里慢」,没讲「计算为什么会停」。流水线、指令级并行、分支预测,这些是 ch02-03 的内容,它们和存储层次一起,构成了 vol6 后面所有「按瓶颈部位优化」的硬件底座。

参考资源

Agner Fog《The microarchitecture of Intel, AMD and VIA CPUs》§23 AMD Zen 3:Zen 3 的缓存延迟表(L1=4、L2=14、L3=47 周期)、流水线宽度、分支吞吐。本地:.claude/drafts/books/optimazation_in_cpp/microarchitecture.md
Bakhvalov, D.《Performance Analysis and Tuning on Modern CPUs》第 3 章 CPU Microarchitecture:存储层次与延迟数字的工程视角
Bryant & O'Hallaron《Computer Systems: A Programmer's Perspective》(CSAPP)第 6 章 The Memory Hierarchy:memory mountain 实验的出处,以及「空间/时间局部性」的形式化定义
本篇实测代码:code/volumn_codes/vol6-performance/ch02/memory_mountain.cpp

存储层次与延迟阶梯:为什么顺序访问快 100 倍 ​

一个让人不舒服的事实:你的 CPU 大部分时间在等内存 ​

存储层次:一层快但小,下一层慢但大 ​

上手跑一跑:本机实测延迟阶梯 ​

memory mountain:把局部性画成一座山 ​

回到 C++:这些数字在告诉我们什么 ​

留给下一篇的线头 ​

参考资源 ​