有一个小实验,代码只有几十行,却能让很多人第一次直观看到缓存的台阶:造一个数组,用随机顺序把每个元素串成一条链,然后从第一个元素开始,一个接一个地跟着指针走。每次只依赖上一次的结果,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,延迟再高一层。共享的好处是省面积、省成本,一个核心用不完的缓存别人还能用;坏处是所有核心抢同一块资源,一个正在跑大数组的程序,能把别的核心热数据挤出去。

L1 数据缓存每核私有,典型几十 KB,延迟几个时钟周期。装当前循环最热的数据。
L2 缓存每核私有,典型几百 KB 到几 MB,延迟十几个周期。L1 的后备。
L3 缓存多核共享,典型几 MB 到几十 MB,延迟几十个周期。核心之间交换数据的落脚点。
DRAM 主存几十 GB,延迟几十到上百纳秒。装所有放不进缓存的数据。

这三层加起来的容量,决定了你程序的「工作集」能不能装进去。工作集是程序在一段时间内真正反复访问的那部分数据,不是整个数据集。一个 4GB 的数据库,如果热点只有 20MB,它照样能跑得很快;反过来,一个 64MB 的数组,只要你是随机访问,就一定在内存里打转。

命中、缺失和缓存行:速度差在哪一步

一次访问先查 L1。地址被分成标记、组号、块内偏移三部分,按组号找到对应的组,再比标记。比中了叫命中,直接拿数据;比不中叫缺失,往下一层找,找到后把整行搬上来,同时可能挤掉一行旧数据。

组相联说的是每组里能放几个候选行。直接映射每组只有一行,冲突多但简单;全相联随便放,命中率高但比较电路贵。实际 CPU 用四路、八路、十六路这种折中,所以你会看到「缓存冲突」这种缺失:明明总容量还空着,但某个地址只能落在固定的几个位置,被挤掉了。

缓存行 64 字节的规则,带来两个方向相反的效应。好的方向是空间局部性:你读数组的第 0 个元素,第 1 到第 15 个也一起进了缓存,接下来顺序访问全是命中。坏的方向是伪共享:两个核心分别修改同一行里的两个不同变量,硬件看到的是同一行被两边写,于是来回同步,性能塌方。

预取器是另一层机制。它会根据你最近的访问模式,猜你接下来要哪几行,提前搬进缓存。顺序扫描时预取非常有效,能把内存延迟藏起来;但链表、树、哈希表这类跳来跳去的访问,预取器猜不中,还可能白搬一堆用不上的行,占掉带宽。

替换策略也得提一句。缓存满了要挤掉一行,硬件不会真的记录每一行的使用时间,那样太贵;实际用的是近似 LRU,也就是「最近用过的优先留下」。这在循环刚好比缓存大一点时最难受:每一轮都把上一轮的行挤出去,下一轮又从头开始缺失,命中率接近零。这种访问模式叫缓存抖动,加大缓存不一定救得了,改变循环分块才行。

顺序访问和随机访问,差的是同一件事

把同样的数据量,用两种方式走一遍,结果差得很远。原因不是「随机访问更费指令」,而是每一行数据被用到的次数不同:顺序访问一行能用满 64 字节,随机访问可能只用 4 字节就丢掉,剩下的 60 字节白搬。

顺序访问

一行 64 字节里的 16 个整数都会被用到,预取器能提前搬下一行,实际延迟被流水掩盖。代价是必须按地址递增,数据结构要连续存放。

随机访问

每次跳到新地址,几乎必然缺失,一行只用到几个字节,预取也帮不上。延迟全额暴露,等效带宽可能只有顺序访问的十分之一。

所以优化访存的第一原则,往往不是「换个更快的库」,而是把访问改成连续的。数组结构体改结构体数组、把链表的节点按访问顺序重排、把哈希表改成开放寻址,这些做法的共同点都是让一次缺失搬回来的 64 字节被尽量用满。

这里要分清延迟和带宽两件事。延迟是一次访问要等多久,带宽是单位时间能搬多少数据。顺序访问把多个请求并行发出去,延迟被掩盖,所以你看到的是带宽;随机访问每次都要等上一环,延迟全额暴露,带宽反而用不满。很多程序「内存带宽只用了三成,却慢得不行」,问题就在延迟不在带宽。

缓存行大小在不同架构上不一样,x86 常见 64 字节,部分 ARM 芯片是 64 字节或 128 字节。写跨平台代码时不要硬编码 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 里挤出去,导致对方明明没改代码却变慢。这种事在容器和云主机上尤其难查,因为你看不到邻居在干什么。

第三,预取会浪费带宽。预取器猜错时,搬进来的行占着缓存和带宽,还可能把有用的行挤掉。对随机访问密集的负载,激进预取有时反而更慢。

第四,测量本身有噪声。频率调节、超线程、后台更新、电源策略,都能让同一段代码在两次运行之间差出百分之二三十。所以做这类实验,重要的不是绝对数字,而是台阶的位置和趋势;单次数据只能当参考。

最后,缓存不是万能的。工作集天生就大、访问天生就随机的负载,比如全表扫描、图遍历、大矩阵转置,再怎么调也躲不开内存。这时候该换的是算法和数据结构,而不是继续在缓存参数上打转。

还要记住,缓存是硬件自动管理的,你能控制的只有数据的布局和访问顺序。同一个算法,数组存和指针链存,可能差出五倍;按行遍历和按列遍历,可能差出一个数量级。先把访问模式理顺,再谈指令级优化,顺序反过来的收益通常很小。

今天就能验证的五个练习

  1. 把上面的代码编译出来,跑一遍,记下你自己机器上的台阶位置。别抄本文的数字,那是我这台机器的。
  2. 把数组大小改成非 2 的幂,比如 96KB、1.5MB、24MB,看台阶是变平滑还是出现新的抖动,想想为什么。
  3. 用 Windows 的 start /affinity 或任务管理器把进程绑到一个核心,再跑一次,对比绑核前后的数字。
  4. 用系统信息或厂商工具查自己 CPU 的 L1、L2、L3 容量,和你测出的台阶位置对照,看是否吻合。
  5. 如果你有 Linux 环境,用 perf stat 看 cache-misses 和 LLC-load-misses;本机是 Windows,没有 perf,这一项未在本机实测,只做方法说明。

收束:缓存是分层的,访问模式决定命运

L1 私有、最小、最快,装当前最热的数据;L2 私有、更大、慢一档,做 L1 的后备;L3 共享、再大、再慢一档,是核心之间交换数据的地方;再往下才是内存。容量每往下一层就大一个量级,延迟也跟着涨,这就是为什么工作集一旦越界,性能会掉一个台阶而不是慢慢变差。

这套逻辑不只适用于内存。往下走到机械硬盘,同样的问题会以另一种形式出现:数据不在缓存里,就得去物理介质上找。下一篇讲机械硬盘,看看寻道和旋转是怎么把「随机访问」的代价放大到毫秒级的。