正常
内存访问慢 100 倍是真的:缓存层级与缓存行
上一篇咱们看到了缓存局部性怎么让 O(n) 的 vector 在小数据量下碾压 O(1) 的 unordered_set,但当时只用了结论,没讲机制。这一篇把机制补齐:为什么内存访问这么慢、缓存怎么救场、它按什么单位搬数据、各级缓存差多少。搞清楚这些,你才能主动设计缓存友好的代码。
先建立一个量级直觉:计算比内存快 100 倍
笔者先甩一个让很多人意外的对比。一颗当代 CPU 的计算能力,粗略估算是每秒能处理上万 GB 的数据量(以浮点吞吐算);而它跟主存(DRAM)之间的带宽,每秒也就几十到一百多 GB。两者差了大约两个数量级。换一个角度更直观:L1 缓存访问大约 1 纳秒,主存访问大约 70 到 100 纳秒——差 100 倍。
100 倍是什么概念?如果你的代码每次要用一个数据都老老实实去主存取,那不管你的 CPU 多快,实际表现都被内存拖慢到百分之一的水平。CPU 在等数据的那 100 纳秒里,什么活都干不了,纯干坐。这就是为什么缓存这件事生死攸关。
缓存怎么救场:局部性原理
好在现实里,内存访问不是完全随机的。程序运行有两个普遍特征,合起来叫局部性原理:
- 时间局部性:刚访问过的数据,很可能马上还要再用。循环里的计数器、累加器,一拍内被读写好几次。
- 空间局部性:访问了某个地址,它附近的地址很可能马上也要访问。遍历数组就是最典型的空间局部性。
硬件工程师利用这两条,在 CPU 核心内部、紧挨着计算单元的地方,放了几层更小但极快的存储,就是缓存(L1/L2/L3)。你访问过的数据会在缓存里留一份,下次再用时直接从缓存拿,不用碰慢吞吞的主存。
缓存层级:越来越大,也越来越慢
本机这颗 AMD Ryzen 7 9700X(Zen 5)的缓存层级是这样的:
text
$ lscpu | grep -iE "L1d|L2|L3 cache"
L1d cache: 384 KiB (8 instances) ← 每核 48 KiB, 私有
L1i cache: 256 KiB (8 instances)
L2 cache: 8 MiB (8 instances) ← 每核 1 MiB, 私有
L3 cache: 32 MiB (1 instance) ← 8 核共享L1 最快最小,每个核心独享;L2 稍大稍慢,也是每核私有;L3 最大最慢(相对前两级),所有核心共享。再往下就是主存,几十 GB 但访问要 100 纳秒。
各级的典型访问延迟(x86 桌面级的大致量级,不同代际有差异):
| 层级 | 容量(本机) | 典型延迟 | 大约几个时钟周期 |
|---|---|---|---|
| L1d | 48 KiB/核 | ~1 ns | 4 |
| L2 | 1 MiB/核 | ~4 ns | 14 |
| L3 | 32 MiB | ~12 ns | 40-50 |
| 主存 | 几十 GB | ~70-100 ns | 200+ |
这张表是后面所有讨论的锚点。注意从 L1 到主存,延迟涨了将近 100 倍,而容量涨了几千倍——这就是缓存的根本权衡:越快的层级越小,你没法把所有数据都塞进最快的 L1。
为什么不做一个大一点的 L1?物理规律不让。SRAM 阵列越大,信号走线越长、地址解码越复杂,访问就越慢。如果把 L1 做到几 MB,它的访问延迟会从 1 纳秒涨到好几纳秒,对那些本来能命中小缓存的代码反而是倒退。所以只能分层:先查 L1,没有就查 L2,再没有查 L3,最后才碰主存。
缓存行:数据是按 64 字节整块搬的
这是理解缓存行为的最关键的一条事实:CPU 搬数据不是按单个字节、甚至不是按单个 int 搬的,而是按缓存行(cache line)整块搬,一条缓存行通常 64 字节。
你读 data[5] 这一个 int(4 字节),CPU 不是只把这 4 字节拿过来。它发现这 4 字节所在的整条 64 字节缓存行不在缓存里,于是把整行 64 字节都从主存拉进来,顺手放进 L1。接下来如果你读 data[6]、data[7]……它们都落在这条已经进缓存的行里,直接命中,零代价。
这就是空间局部性能带来巨大收益的物理原因:你访问一个元素,等于把它周围 16 个 int(64 字节 / 4 字节)都免费请进了缓存。顺序遍历数组时,每 16 个元素才付一次主存访问的代价,剩下 15 个全是白赚。
反过来,这也是随机访问慢的根本原因:你东取一个西取一个,每取一个都可能是全新的缓存行,每次都付全额主存延迟。
承重实验:顺序 vs 随机,差 17 倍
光说结论没意思,咱们跑一个。准备一个 800 万元素(约 32 MB,远超 L3)的 int 数组,然后分别用顺序索引和打乱过的随机索引去累加它的每个元素:
cpp
constexpr int N = 8'000'000; // 32MB, 远超 L3
std::vector<int> data(N);
std::iota(data.begin(), data.end(), 0);
std::vector<int> seq_idx(N);
std::iota(seq_idx.begin(), seq_idx.end(), 0); // 顺序
std::vector<int> rand_idx = seq_idx;
std::shuffle(rand_idx.begin(), rand_idx.end(), rng); // 随机打乱
// 分别用 seq_idx 和 rand_idx 遍历 data, 累加本机结果:
text
顺序访问 8000000 元素: 2.1 ms (0.27 ns/elem)
随机访问 8000000 元素: 36.4 ms (4.55 ns/elem)随机访问比顺序访问慢了 17 倍。同样的数据、同样的计算量(都是把 800 万个数加一遍),唯一的区别是访问顺序。顺序访问时,硬件预取器发现你按地址递增读,提前把后面的缓存行拉进 L1,你几乎永远命中;随机访问时,预取器抓不到规律,每次跳转都可能是新缓存行,大量 cache miss,每个元素平均要付 4.55 纳秒(接近 L3 到主存之间的延迟)。
17 倍。这就是缓存行的力量。你写代码时,是按行遍历一个二维数组还是按列遍历,是用连续内存的 vector 还是节点散落的 list,在数据量稍大时,差距就是这个量级。
缓存驱逐与缓存颠簸
缓存容量有限,装不下所有数据,这就引出了缓存行为的另一面:驱逐(eviction)。当缓存满了,你要加载新数据,硬件就得挑一个旧条目踢出去腾位置。L1 才 48 KiB,装不下多少,所以驱逐几乎每时每刻都在发生。
驱逐本身不可怕,可怕的是踢错人。如果硬件踢掉的那个条目,恰好是你下一步马上要用的,你就得重新去主存取一次。更糟的是,这次取回来的新数据可能又把另一个马上要用的挤走,于是反复踢人、反复 miss,命中率趋近于零。这种现象有个专门的名字:缓存颠簸(cache thrashing)。
一旦进入颠簸状态,虽然有缓存,表现得跟没有一样,程序退化到"每次都走主存"的 100 倍慢。笔者以前写过一个对大数组按某种固定步长访问的程序,算法怎么调都没用,后来一看 cache miss 率高得离谱——访问步长恰好和缓存组的映射方式冲突,每次加载都在踢掉下一步要用的数据。改了一下数据布局,算法一行没动,性能翻了十几倍。这就是"内存墙"三个字的分量。
理解了驱逐,你就能解释一个常见现象:为什么基准测试里"工作集大小 vs 访问延迟"的曲线是阶梯状下滑的,而不是断崖。当工作集小于 L1 时,全命中,延迟最低;工作集超过 L1 但还在 L2 内,L1 开始有 miss,延迟缓慢上升;超过 L2 进 L3 范围,又多一层 miss 来源,延迟继续涨;超过 L3,大量访问打到主存,延迟飙到顶。每一级缓存被撑爆,都多一种 miss 来源,所以曲线是一段一段的下滑斜坡,不是一刀切的台阶。
写入呢:写透 vs 写回
前面讲的都是读取。写入时,如果你往一个已在缓存里的地址写数据,底层有两种硬件模型。
写透(write-through):每次写同时更新缓存副本和主存原始值。简单,一致性天然保证,但每次写都要额外跑一趟主存,写性能被拖垮。
写回(write-back):写的时候只更新缓存里的副本,主存不管。只有当这条缓存行要被驱逐时,才把脏数据(被改过的缓存行)写回主存。
现代 CPU 几乎全用写回——你连续写同一缓存行 8 次,写透要跑 8 趟主存,写回只要在驱逐时跑 1 趟,优势太大。但写回在多线程下会引发缓存一致性问题(线程 A 在自己缓存里改了值,主存还是旧的,线程 B 从主存读到过期数据),硬件靠 MESI 这类协议处理,代价是真实存在的。这个话题留到以后讲并发缓存一致性时展开,这一篇先守住单线程的直觉。
这一层的边界
到这儿,缓存的机制讲完了:它为什么存在(计算比内存快 100 倍)、怎么救场(局部性原理)、按什么单位搬数据(64 字节缓存行)、各级差多少(L1 到主存 100 倍)、为什么会颠簸(驱逐踢错人)。有了这套直觉,你再看上一篇的 vector vs unordered_set,每一个现象都能对上号。
但缓存友好还有一条不那么直观的途径,藏在你的数据类型选择里。把 int 换成 uint8_t 看似省了 4 倍缓存空间,应该更快对吧?下一篇咱们就跑一个实验,看看这件事是不是真的。