有一个小实验,代码只有几十行,却能让很多人第一次直观看到缓存的台阶:造一个数组,用随机顺序把每个元素串成一条链,然后从第一个元素开始,一个接一个地跟着指针走。每次只依赖上一次的结果,CPU 没法提前算,也没有连续地址可供预取。
数组从 4KB 调到 64MB,循环的次数不变、指令不变、编译参数不变,但每次访问的平均耗时能从一纳秒出头爬到二十几纳秒,中间还有几个明显的台阶。台阶出现的位置,不是程序写错了,而是工作集刚好超出了某一级缓存。
这篇要做两件事:把 L1、L2、L3 各自装什么、谁私有谁共享讲清楚;然后给你一段能编译、能真跑、能自己复现的代码,用实测数字说话。具体 CPU 型号不影响结论,台阶的位置取决于你自己机器上的缓存大小,所以结论要落到本机,而不是背别人的表。
先说一个术语。缓存行(cache line)是 CPU 和内存之间搬运数据的最小单位,典型 64 字节。你读一个 4 字节的整数,内存和缓存之间搬的是一整行。这个规则是后面所有现象的根。
先看实测:台阶长什么样
下面这段程序,就是开头说的指针追逐。先用随机置换把数组下标打乱,再按置换顺序把每个位置指向下一个位置,形成一条覆盖整个数组的环;然后从 0 号位开始连续跳几百万次,用高精度计时器量总时间,除以访问次数。
为什么非要用「跟着指针走」这种写法?因为只有下一次地址依赖上一次的结果,CPU 才没法提前把后面的访问都发出去。如果是顺序遍历,处理器可以同时挂起很多个独立的读请求,延迟被并行掩盖,你量到的就不是单次延迟,而是吞吐。指针追逐把每次访问串成一条链,链上任何一环缺失,后面全得等,这样量出来的数字才代表真实的单次代价。
循环前面那段预热也有用。第一次访问一个页面时,除了缓存是冷的,还可能触发缺页、TLB 未命中和内存分配器的懒加载。先空跑两遍,把这些一次性的开销摊掉,剩下的才是稳态。
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
static double now_ns(void) {
LARGE_INTEGER f, c;
QueryPerformanceFrequency(&f);
QueryPerformanceCounter(&c);
return (double)c.QuadPart * 1e9 / (double)f.QuadPart;
}
static void run(size_t bytes) {
size_t n = bytes / sizeof(size_t);
size_t *a = malloc(n * sizeof(size_t));
size_t *perm = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) perm[i] = i;
srand(12345);
for (size_t i = n - 1; i > 0; i--) {
size_t j = (size_t)(rand() % (int)(i + 1));
size_t t = perm[i]; perm[i] = perm[j]; perm[j] = t;
}
for (size_t i = 0; i < n; i++) a[perm[i]] = perm[(i + 1) % n];
volatile size_t idx = 0;
for (size_t i = 0; i < n * 2; i++) idx = a[idx]; /* 预热 */
size_t total = 4000000, steps = total / n;
if (steps < 2) steps = 2;
double t0 = now_ns();
for (size_t s = 0; s < steps; s++)
for (size_t i = 0; i < n; i++) idx = a[idx];
double t1 = now_ns();
printf("%8.0f KB %8.2f ns/access\n",
(double)bytes / 1024.0, (t1 - t0) / (double)(steps * n));
free(a); free(perm);
}
int main(void) {
size_t sizes[] = { 4<<10, 8<<10, 16<<10, 32<<10, 64<<10,
128<<10, 256<<10, 512<<10, 1<<20, 2<<20,
4<<20, 8<<20, 16<<20, 32<<20, 64<<20 };
for (size_t i = 0; i < sizeof(sizes)/sizeof(sizes[0]); i++) run(sizes[i]);
return 0;
}
编译用 gcc,开优化,单线程跑,不绑核:
gcc -O2 chase.c -o chase.exe
.\chase.exe
本机实际输出(Windows 11,gcc 16.2,8 核 12 线程的 x86 笔记本,系统报告 L2 合计 7MB、L3 12MB;单次运行,未绑核):
pointer chase, stride = one cache line, random order
4 KB 1.38 ns/access
8 KB 1.10 ns/access
16 KB 1.14 ns/access
32 KB 1.10 ns/access
64 KB 1.82 ns/access
128 KB 3.03 ns/access
256 KB 3.10 ns/access
512 KB 3.99 ns/access
1024 KB 5.13 ns/access
2048 KB 10.26 ns/access
4096 KB 19.31 ns/access
8192 KB 19.97 ns/access
16384 KB 17.93 ns/access
32768 KB 19.70 ns/access
65536 KB 23.29 ns/access
这不是跑分,也不该拿去和别人比。它只说明一件事:同一段代码,工作集大小不同,平均访问延迟差二十倍。这个差距全部来自数据落在哪一级存储上。
L1:每核私有,装最热的那几十 KB
L1 是离核心最近的一级缓存,通常分成两块:指令缓存和数据缓存。数据部分在现在的 x86 上一般是 32KB 到 48KB,每核私有,延迟在四个到五个时钟周期。它装的是当前循环和函数反复碰的那些数据。
私有意味着每个核心都有自己的 L1,两个核心改了同一块数据,各自的 L1 里就是两份,需要靠一致性协议同步。也意味着 L1 不会因为别的核心在跑重活而被挤掉,代价是同样的容量要重复八份、十二份。
L1 的容量停在几十 KB 不是工艺限制,而是权衡。阵列越大,译码和布线的延迟越长,命中率提升却越来越慢。把 L1 做到 1MB,延迟可能翻倍,而多出来的命中率补不回这部分损失,所以工程师把它停在几十 KB,再往上加一层 L2。
L2 与 L3:私有的大缓存和共享的更大缓存
L2 一般也是每核私有,容量在几百 KB 到几 MB 之间,延迟比 L1 高一个档次。它装的是「最近用过、但没那么热」的数据,也是 L1 的后备。很多现代 CPU 的 L2 已经到 1MB 甚至 2MB 每核,所以从 L1 掉到 L2 的那一级台阶,位置比十年前高了不少。
L3 通常是整个 CPU 共享的,容量在几 MB 到几十 MB,延迟再高一层。共享的好处是省面积、省成本,一个核心用不完的缓存别人还能用;坏处是所有核心抢同一块资源,一个正在跑大数组的程序,能把别的核心热数据挤出去。
这三层加起来的容量,决定了你程序的「工作集」能不能装进去。工作集是程序在一段时间内真正反复访问的那部分数据,不是整个数据集。一个 4GB 的数据库,如果热点只有 20MB,它照样能跑得很快;反过来,一个 64MB 的数组,只要你是随机访问,就一定在内存里打转。
命中、缺失和缓存行:速度差在哪一步
一次访问先查 L1。地址被分成标记、组号、块内偏移三部分,按组号找到对应的组,再比标记。比中了叫命中,直接拿数据;比不中叫缺失,往下一层找,找到后把整行搬上来,同时可能挤掉一行旧数据。
组相联说的是每组里能放几个候选行。直接映射每组只有一行,冲突多但简单;全相联随便放,命中率高但比较电路贵。实际 CPU 用四路、八路、十六路这种折中,所以你会看到「缓存冲突」这种缺失:明明总容量还空着,但某个地址只能落在固定的几个位置,被挤掉了。
缓存行 64 字节的规则,带来两个方向相反的效应。好的方向是空间局部性:你读数组的第 0 个元素,第 1 到第 15 个也一起进了缓存,接下来顺序访问全是命中。坏的方向是伪共享:两个核心分别修改同一行里的两个不同变量,硬件看到的是同一行被两边写,于是来回同步,性能塌方。
预取器是另一层机制。它会根据你最近的访问模式,猜你接下来要哪几行,提前搬进缓存。顺序扫描时预取非常有效,能把内存延迟藏起来;但链表、树、哈希表这类跳来跳去的访问,预取器猜不中,还可能白搬一堆用不上的行,占掉带宽。
替换策略也得提一句。缓存满了要挤掉一行,硬件不会真的记录每一行的使用时间,那样太贵;实际用的是近似 LRU,也就是「最近用过的优先留下」。这在循环刚好比缓存大一点时最难受:每一轮都把上一轮的行挤出去,下一轮又从头开始缺失,命中率接近零。这种访问模式叫缓存抖动,加大缓存不一定救得了,改变循环分块才行。
顺序访问和随机访问,差的是同一件事
把同样的数据量,用两种方式走一遍,结果差得很远。原因不是「随机访问更费指令」,而是每一行数据被用到的次数不同:顺序访问一行能用满 64 字节,随机访问可能只用 4 字节就丢掉,剩下的 60 字节白搬。
顺序访问
一行 64 字节里的 16 个整数都会被用到,预取器能提前搬下一行,实际延迟被流水掩盖。代价是必须按地址递增,数据结构要连续存放。
随机访问
每次跳到新地址,几乎必然缺失,一行只用到几个字节,预取也帮不上。延迟全额暴露,等效带宽可能只有顺序访问的十分之一。
所以优化访存的第一原则,往往不是「换个更快的库」,而是把访问改成连续的。数组结构体改结构体数组、把链表的节点按访问顺序重排、把哈希表改成开放寻址,这些做法的共同点都是让一次缺失搬回来的 64 字节被尽量用满。
这里要分清延迟和带宽两件事。延迟是一次访问要等多久,带宽是单位时间能搬多少数据。顺序访问把多个请求并行发出去,延迟被掩盖,所以你看到的是带宽;随机访问每次都要等上一环,延迟全额暴露,带宽反而用不满。很多程序「内存带宽只用了三成,却慢得不行」,问题就在延迟不在带宽。
把实测数字读一遍
回到上面那张输出。4KB 到 32KB 都在 1.1 到 1.4 纳秒,这一段是 L1 命中。64KB 爬到 1.82,128KB 跳到 3.03,这里出现了第一级台阶:工作集超过了 L1 数据缓存,开始吃 L2。
128KB 到 512KB 在 3 到 4 纳秒,是 L2 的主力区间。1MB 到 5.13,2MB 到 10.26,说明 L2 也装不下了。4MB 直接跳到 19.31 纳秒,这是第二级大台阶:数据落到 L3。之后 4MB 到 32MB 都在 18 到 20 纳秒的平台,因为这台机器的 L3 有 12MB,共享缓存本身延迟就有十几纳秒,L3 命中和 L3 溢出到内存的差别被平台本身的高延迟盖住了一部分。64MB 到 23.29,才明显是内存。
为什么没有教科书上那种四级整齐的台阶?两个原因。一是这台机器的 L2 已经到 MB 级别,L2 和 L3 的延迟差不像老机器那么夸张;二是单次运行、没绑核、系统后台还在动,频率调节和调度迁移都会把台阶磨平。想看得更干净,可以每个尺寸跑五遍取中位数,再把进程绑到一个核上。
还有个细节:4KB 那一行反而比 8KB 慢一点。这个量级的数组小到整块都能放进 L1,差别主要来自循环次数和计时开销,不是缓存行为,属于测量噪声,不用过度解读。真正有意义的转折点是台阶,不是每个数字的小数位。
现象对照:这些卡顿先查哪儿
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 数组扩大一倍,耗时不按比例涨,而是突然翻几倍 | 工作集跨过了某一级缓存边界,命中率断崖式下降 | 量实际工作集大小,对照 CPU 各级缓存容量,看台阶落在哪 |
| 两个线程各改各的变量,却互相拖慢 | 两个变量落在同一缓存行,触发伪共享和一致性流量 | 看两个变量的地址差,必要时按缓存行对齐并加填充 |
| 顺序遍历很快,换成链表就慢十倍 | 节点不连续,每次访问都是新行,预取猜不中 | 看数据结构的布局和单次缺失搬运的字节利用率 |
| 多核一起跑,单核性能反而下降 | 共享 L3 被其他核心挤占,带宽和容量都在争 | 对比单线程与多线程的单次访问延迟和 L3 缺失率 |
| 加了预取指令却没有变快 | 预取距离不对,或者访问本来就不规则,预取的行用不上 | 确认访问模式是否可预测,检查预取距离是否覆盖真实延迟 |
| 同一份代码在开发机和服务器上台阶位置不同 | 两级机器的缓存容量和共享方式不同,不能照搬结论 | 分别查两台的 L1/L2/L3 大小与核心数,各自测一遍 |
| 程序跑一会快一会慢 | 频率调节、后台进程、NUMA 或调度迁移导致环境不稳定 | 绑核、关掉无关进程、固定性能模式后重测 |
边界与代价
第一,缓存一致性不是免费的。多核共享数据时,硬件要保证一个核心写的值别人能看见,这靠一套一致性协议,代价是监听、失效和同步流量。核心越多,共享写得越频繁,这部分开销越明显。所谓「多核跑不满」,很多时候不是算力不够,是数据在核间来回搬。
第二,L3 共享带来争用。一个跑大数组的程序,能把别的核心的热数据从 L3 里挤出去,导致对方明明没改代码却变慢。这种事在容器和云主机上尤其难查,因为你看不到邻居在干什么。
第三,预取会浪费带宽。预取器猜错时,搬进来的行占着缓存和带宽,还可能把有用的行挤掉。对随机访问密集的负载,激进预取有时反而更慢。
第四,测量本身有噪声。频率调节、超线程、后台更新、电源策略,都能让同一段代码在两次运行之间差出百分之二三十。所以做这类实验,重要的不是绝对数字,而是台阶的位置和趋势;单次数据只能当参考。
最后,缓存不是万能的。工作集天生就大、访问天生就随机的负载,比如全表扫描、图遍历、大矩阵转置,再怎么调也躲不开内存。这时候该换的是算法和数据结构,而不是继续在缓存参数上打转。
还要记住,缓存是硬件自动管理的,你能控制的只有数据的布局和访问顺序。同一个算法,数组存和指针链存,可能差出五倍;按行遍历和按列遍历,可能差出一个数量级。先把访问模式理顺,再谈指令级优化,顺序反过来的收益通常很小。
今天就能验证的五个练习
- 把上面的代码编译出来,跑一遍,记下你自己机器上的台阶位置。别抄本文的数字,那是我这台机器的。
- 把数组大小改成非 2 的幂,比如 96KB、1.5MB、24MB,看台阶是变平滑还是出现新的抖动,想想为什么。
- 用 Windows 的
start /affinity或任务管理器把进程绑到一个核心,再跑一次,对比绑核前后的数字。 - 用系统信息或厂商工具查自己 CPU 的 L1、L2、L3 容量,和你测出的台阶位置对照,看是否吻合。
- 如果你有 Linux 环境,用
perf stat看cache-misses和LLC-load-misses;本机是 Windows,没有 perf,这一项未在本机实测,只做方法说明。
收束:缓存是分层的,访问模式决定命运
L1 私有、最小、最快,装当前最热的数据;L2 私有、更大、慢一档,做 L1 的后备;L3 共享、再大、再慢一档,是核心之间交换数据的地方;再往下才是内存。容量每往下一层就大一个量级,延迟也跟着涨,这就是为什么工作集一旦越界,性能会掉一个台阶而不是慢慢变差。
这套逻辑不只适用于内存。往下走到机械硬盘,同样的问题会以另一种形式出现:数据不在缓存里,就得去物理介质上找。下一篇讲机械硬盘,看看寻道和旋转是怎么把「随机访问」的代价放大到毫秒级的。