第1章 CPU 缓存层次结构

缓存的基本原理

章节导读

在开始深入缓存的细节之前，让我们先回到一个令人不安的历史事实：过去四十年里，CPU 的处理速度按照摩尔定律一路狂奔，而主存 DRAM 的访问延迟却几乎在原地踏步。1980 年代初，一次主存访问大约需要 200 纳秒，而今天的 DRAM 访问延迟仍然是 60 到 100 纳秒左右——四十多年只改善了两三倍。与此同时，CPU 的主频从几 MHz 提升到了几 GHz，单条指令的执行时间从数百纳秒缩短到不足一纳秒。这意味着什么呢？在 1980 年，CPU 等待一次内存访问相当于等待几十个时钟周期；而在今天，同样的内存访问需要等待两三百个时钟周期。如果把 CPU 的一条指令想象成一个人眨一次眼，那么一次主存访问就相当于这个人静静地坐在那里等待十几分钟。这就是著名的「处理器-内存鸿沟」（Processor-Memory Gap），它是现代计算机体系结构中最核心的矛盾之一。

存储层	典型延迟	CPU 周期数 (@4GHz)	典型容量	带宽	缓存未命中代价
L1 数据缓存	~1 ns	3-4 周期	32-48 KB	~2 TB/s	- (基准)
L2 缓存	~3 ns	10-14 周期	256 KB-1 MB	~1 TB/s	~10 周期惩罚
L3 缓存	~12 ns	40-70 周期	4-32 MB	~500 GB/s	~50 周期惩罚
主存 DDR4	~60 ns	200-300 周期	8-256 GB	~50 GB/s	~250 周期惩罚
主存 DDR5	~50 ns	180-250 周期	16-512 GB	~80 GB/s	~200 周期惩罚
NVMe SSD	~10 us	~40,000 周期	256 GB-4 TB	~7 GB/s	需 OS 介入

缓存（Cache）就是为了弥合这道鸿沟而发明的。它的基本思想可以用一个生活中的类比来理解：假设你是一位厨师，你的菜谱存放在图书馆里（主存），而你的操作台就在厨房（CPU）。每次做菜都要跑一趟图书馆显然效率极低，于是你在厨房里放了一个小书架（L1 缓存），把最近常用的几本菜谱放在上面；书架放不下，你又在厨房门口放了一个柜子（L2 缓存）；柜子也放不下，你在楼下储藏室再放一批（L3 缓存）。当你需要某本菜谱时，先看小书架，没有再看柜子，再看储藏室，最后才不得不跑图书馆。绝大多数时候，你要用的菜谱就在手边——因为人的行为具有「局部性」：刚用过的菜谱马上还会用（时间局部性），同一系列的菜谱往往一起用（空间局部性）。

缓存之所以有效，正是建立在程序行为的局部性原理之上。Drepper 在论文中强调，缓存对程序员来说不是「透明的硬件细节」，而是必须主动理解和配合的系统组件。一个不了解缓存的程序员写出的代码，与一个深谙缓存之道的程序员写出的代码，性能差距可以达到十倍甚至数十倍，而它们的功能完全相同。本章将从缓存的物理实现（SRAM 与 DRAM 的本质区别）讲起，逐步展开缓存行、缓存层次、命中与未命中的分类、替换策略、写策略，最后引入两个强大的性能分析工具：AMAT（平均内存访问时间）公式和 CSAPP 提出的「存储器山」模型。掌握这些内容，你就拥有了理解后续所有章节——虚拟内存、NUMA、缓存优化——的坚实基础。

核心概念

缓存行
L1/L2/L3 缓存
缓存未命中
局部性

要点精析

处理器-内存鸿沟是缓存存在的根本原因。从 1980 年到今天，CPU 性能提升了约一万倍，而 DRAM 延迟只改善了约两三倍。以一颗 3GHz 的处理器为例，一个时钟周期只有 0.33 纳秒，而一次主存访问需要约 80 纳秒，相当于 240 个时钟周期。如果 CPU 每次取数据都直接访问主存，那么它 99% 以上的时间都在等待，昂贵的晶体管资源将被彻底浪费。更糟糕的是，随着多核时代的到来，多个核心同时争抢内存总线带宽，「内存墙」问题愈发严重。缓存通过在小而快的存储器中保存主存内容的副本，让 CPU 大部分访问都能在几个周期内完成，从而把鸿沟「填平」。理解这一点至关重要：缓存不是锦上添花的优化，而是现代计算机能够正常工作的必要前提。

缓存的物理实现是 SRAM，主存的物理实现是 DRAM，两者的差异决定了整个存储层次的形态。SRAM（静态随机访问存储器）用 6 个晶体管组成的双稳态触发器存储一个比特，只要供电数据就保持不变，读写速度极快（1-2 纳秒），但面积大、成本高、功耗大，因此只能做成几 MB 的小容量，并且必须和 CPU 封装在一起。DRAM（动态随机访问存储器）用一个晶体管加一个电容存储一个比特，电容会漏电，需要每隔几毫秒刷新一次，读写延迟在 50-100 纳秒量级，但结构极其紧凑、成本低，因此可以做成几十 GB 的大容量。SRAM 每 GB 的成本大约是 DRAM 的一百倍以上。这种「速度-容量-成本」的三角矛盾，注定了存储系统必须组织成金字塔形的层次结构：越靠近 CPU 的层级越快、越小、越贵。

缓存行（Cache Line）是缓存与主存之间数据交换的基本单位，在 x86 架构上固定为 64 字节。CPU 从来不会只从内存中取一个字节或一个整数——即使你只读一个 4 字节的 int，硬件也会把它所在的整个 64 字节缓存行加载进缓存。这个设计是空间局部性的直接体现：既然程序访问了某个地址，那么它附近的地址很可能马上也会被访问，一次性搬运 64 字节的边际成本远低于分八次各搬 8 字节。缓存行规则带来一系列重要的实践推论：第一，顺序遍历数组几乎免费，因为每 16 个 int 才产生一次真正的内存访问；第二，跨越缓存行边界的访问需要加载两个缓存行，代价翻倍；第三，两个线程修改同一个缓存行内的不同变量会引发伪共享，这是多线程性能的头号杀手；第四，数据结构按 64 字节对齐可以避免不必要的行分裂。

局部性原理是缓存有效性的理论基石，分为时间局部性和空间局部性两种。时间局部性指「被访问过的数据很可能在不久的将来再次被访问」，典型例子是循环中的循环变量、热点函数的指令、频繁使用的配置项。空间局部性指「被访问数据附近的数据很可能在不久的将来被访问」，典型例子是顺序遍历数组、读取文件的连续字节、执行顺序排列的指令流。良好的程序应该同时具备两种局部性：内层循环反复使用同一批数据（时间局部性），而这批数据在内存中连续存放（空间局部性）。反过来，随机访问一个巨大的哈希表、跳跃式遍历链表、以大步长扫描数组，都是局部性极差的模式。Drepper 特别指出，局部性不是编译器能自动解决的问题，它本质上由算法和数据结构的选择决定，程序员必须在设计阶段就把它纳入考量。

现代 CPU 的缓存是多层结构，以 Intel Core 系列为典型代表：L1 缓存每个核心私有，通常 32KB 指令缓存加 32KB 数据缓存，访问延迟约 4-5 个时钟周期，采用 8 路组相联；L2 缓存每核心私有（或两个核心共享），通常 256KB 到 1MB，延迟约 12-14 个周期；L3 缓存整个处理器共享，通常 8MB 到 32MB 甚至更大，延迟约 40-50 个周期；主存延迟则在 200 个周期以上。这种层次设计的逻辑是：L1 追求极致速度，容量必须很小；L3 追求覆盖大部分工作集，速度可以妥协。一个有用的经验法则是：如果你的热数据能装进 L1，程序会飞快；如果溢出到 L2，性能下降约三倍；溢出到 L3，再降三倍；溢出到主存，再降五倍。理解自己程序的「工作集大小」与各级缓存容量的关系，是性能调优的第一步。

缓存未命中分为三种经典类型，理解它们的成因才能对症下药。第一种是强制性未命中（Compulsory Miss，又称冷未命中）：数据第一次被访问，缓存中必然没有，任何缓存设计都无法避免，只能通过预取来隐藏延迟。第二种是容量未命中（Capacity Miss）：程序的工作集超过了缓存容量，数据被逐出后又被访问，解决办法是减小工作集（如循环分块）或使用更大的缓存。第三种是冲突未命中（Conflict Miss）：缓存还有空闲空间，但由于组相联的映射规则，多个频繁访问的地址恰好映射到同一组，互相驱逐，解决办法是调整数据布局或填充对齐。在实际测量中，一个矩阵乘法程序可能表现出 5% 的强制性未命中、10% 的容量未命中和高达 30% 的冲突未命中——最后这部分通过分块技术几乎可以完全消除，这正是 Cache Lab 中矩阵转置优化的核心思路。

缓存替换策略决定了当一组缓存行装满时驱逐哪一行。理论上最优的是 Belady 算法——驱逐未来最久不会被使用的行，但它需要预知未来，只能作为离线基准。实际硬件普遍采用近似 LRU（Least Recently Used，最近最少使用）的策略：真正的 LRU 在 16 路组相联下需要维护每路的完整访问序，硬件成本太高，所以现代 CPU 使用「树状伪 LRU」或「插入-提升」等简化变体，只记录大致的使用顺序。此外还有 FIFO（先进先出）和 Random（随机）策略。有趣的是，研究表明随机替换在多数工作负载下与伪 LRU 的差距不到 5%，而且完全避免了病态访问模式（如循环扫描一个略大于缓存的数组）下 LRU 的抖动问题——在这种模式下 LRU 的命中率会退化到接近零，而随机替换仍能保持一定命中率。这也是为什么一些嵌入式处理器直接采用随机替换。

缓存写策略分为直写（Write-through）和写回（Write-back）两种。直写策略下，每次写操作都同时更新缓存行和下一级存储，实现简单、一致性好维护，但会产生大量总线流量——即使一个变量在循环中被写了一千次，也要向内存发送一千次写请求。写回策略下，写操作只更新缓存行并设置「脏位」（Dirty Bit），只有当脏行被替换时才写回内存，多次写同一行只需一次内存传输，大幅降低带宽压力，现代 CPU 的 L1/L2/L3 几乎全部采用写回。写回带来的复杂性是一致性维护：多核系统中，一个核心修改了缓存行，其他核心缓存中的副本就过期了，必须依靠 MESI 等缓存一致性协议来侦测和失效。Drepper 在论文中详细讨论了这一点，并指出写缓冲区（Write Buffer）和写合并（Write Combining）机制如何进一步隐藏写延迟，以及非临时存储指令（如 movnti）如何绕过缓存直接写入内存，用于流式写大数据的场景。

AMAT（Average Memory Access Time，平均内存访问时间）是量化存储层次性能的黄金公式：AMAT = L1 命中时间 + L1 未命中率 ×（L2 命中时间 + L2 未命中率 ×（L3 命中时间 + L3 未命中率 × 主存访问时间））。举一个具体例子：假设 L1 命中时间 1 周期、命中率 95%，L2 命中时间 10 周期、命中率 80%，L3 命中时间 40 周期、命中率 70%，主存 200 周期。则 AMAT = 1 + 0.05 × (10 + 0.20 × (40 + 0.30 × 200)) = 1 + 0.05 × (10 + 0.20 × 100) = 1 + 0.05 × 30 = 2.5 周期。注意这个计算的深刻含义：虽然主存慢 200 倍，但由于层层过滤，平均每次访问只花 2.5 周期。反过来，如果 L1 命中率从 95% 降到 90%，AMAT 会升到 3.5 周期，性能下降 40%——命中率的小幅变化会被逐级放大。这就是为什么性能优化要死磕每一个百分点的命中率。

存储器山（Memory Mountain）是 CSAPP 提出的理解缓存性能的经典可视化模型。想象一座山：横轴有两个维度——时间局部性（用工作集大小表示，从几百字节到几百 MB）和空间局部性（用访问步长表示，从 1 字节到 64 字节以上），纵轴是实测的读吞吐量（GB/s）。当你用一个固定大小的数组反复做求和扫描时，工作集小于 L1 容量的区域吞吐量最高（山顶），随着工作集跨过 L1、L2、L3 的容量边界，吞吐量出现三级陡降（山脊），最终落到主存的平原上；而增大步长会削弱空间局部性，让整座山的高度整体下降。存储器山的价值在于它把抽象的缓存参数变成了可以亲手测量的地形图：通过自己绘制这座山，你可以精确地知道目标机器的 L1/L2/L3 容量、各级带宽以及缓存行大小，这比查手册更可靠，因为实际性能还受预取器、TLB 等因素影响。

代码示例

下面这段代码演示了访问模式对缓存命中率的决定性影响。两个循环做的事情完全相同——把 N×N 矩阵清零——但性能可能相差十倍以上。第一个版本按列优先顺序访问行优先存储的数组，每次内层迭代跳跃 N×4 字节，几乎每次访问都落在不同的缓存行甚至不同的页上，空间局部性为零；第二个版本按行优先顺序访问，相邻迭代访问相邻内存，每个缓存行被完整利用后才切换到下一行。当 N=4096 时，矩阵共 64MB，远超 L3 容量，列优先版本的未命中率接近 100%，而行优先版本每 16 个 int 才有一次真正的内存访问。用 perf stat 测量，两者的 cache-misses 数量相差一个数量级，运行时间通常相差 5-15 倍。这个例子说明：在缓存主导性能的世界里，「怎么访问」比「访问什么」更重要。
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        a[i][j] = 0;

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        a[i][j] = 0;

这段代码用于测量缓存行大小和各级缓存的边界，是绘制存储器山的基础。外层控制工作集大小（数组字节数从 512B 倍增到 512MB），内层控制访问步长（从 1 字节到 256 字节），对每种组合反复扫描数组并计算有效读带宽。关键细节有三个：第一，扫描必须重复多轮（内层 r 循环），否则测到的是强制性未命中而非稳态性能；第二，数组要动态分配并按页对齐，避免栈上小数组的干扰；第三，计时要用 clock_gettime 而非 time，精度才够。运行后把结果画成三维图，你会清晰地看到：步长超过 64 字节后带宽骤降（证明缓存行是 64 字节）；工作集跨过 32KB、256KB、8MB 时出现三级台阶（对应 L1、L2、L3 容量）。亲手测出这些数字，比背诵手册上的参数深刻得多。
double measure(size_t working_set_bytes, size_t stride) {
    char *buf = aligned_alloc(4096, working_set_bytes);
    memset(buf, 1, working_set_bytes);
    long sum = 0;
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int r = 0; r < REPS; r++)
        for (size_t i = 0; i < working_set_bytes; i += stride)
            sum += buf[i];
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double secs = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    free(buf);
    return (double)working_set_bytes * REPS / secs / 1e9;
}

这个例子展示如何用 perf 工具验证缓存假设。程序对同一份数据分别做「热访问」（工作集 8KB，装得进 L1）和「冷访问」（工作集 32MB，只能放主存）两种模式的累加。编译后运行 perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./demo，你会看到热访问版本的 L1 未命中接近零，而冷访问版本的未命中率高达百分之几十。更进一步，perf record -e cache-misses -g ./demo 加 perf annotate 可以把未命中精确定位到具体的源代码行——你会惊讶地发现，未命中并不均匀分布，而是集中在少数几个「坏」的访问点上。Drepper 反复强调：不要凭直觉猜性能瓶颈，现代处理器的行为复杂到任何资深程序员都会猜错，测量是唯一可靠的方法。perf、valgrind 的 cachegrind、Intel VTune 都是免费的测量利器，养成「先测量后优化」的习惯。
#include <stdio.h>
#define HOT (8 * 1024)
#define COLD (32 * 1024 * 1024)

long scan(char *buf, size_t n) {
    long s = 0;
    for (size_t i = 0; i < n; i += 64)
        s += buf[i];
    return s;
}

这段代码演示缓存行对齐的实际应用。假设你在实现一个高性能队列，头指针被生产者线程频繁修改，尾指针被消费者线程频繁修改。如果两个指针在结构体中相邻存放（如左图），它们大概率落在同一个 64 字节缓存行内，两个核心的每次写操作都会触发 MESI 协议的一致性流量，缓存行在两个核心的 L1 之间来回「乒乓」，吞吐量可能下降十倍。解决方法是用 alignas(64) 强制两个指针各自独占一个缓存行（如右图），写操作互不干扰。C11 的 alignas 和 C++11 的 alignas 都可用于此目的，Linux 内核中对应的宏是 ____cacheline_aligned。注意验证方法：用 offsetof 打印两个字段在结构体中的偏移，确认它们相差至少 64 字节；再用 perf c2c（cache-to-cache）工具可以直接检测伪共享热点。
struct BadQueue {
    size_t head;
    size_t tail;
    char pad[48];
};

struct GoodQueue {
    alignas(64) size_t head;
    alignas(64) size_t tail;
};

实验笔记

本章配套的实践实验分为三个递进阶段。第一阶段「测量你的存储器山」：使用前面给出的 measure 函数，在工作集从 512B 到 512MB（每次乘以 2）、步长从 1 到 256 字节（每次乘以 2）的网格上测量读带宽，把结果输出为 CSV，用 Python 的 matplotlib 绘制三维曲面图。你需要回答：你的机器 L1/L2/L3 的实际容量和带宽各是多少？步长多大时空间局部性收益消失？为什么某些点的带宽反而高于相邻点（提示：硬件预取器）？第二阶段「实现缓存模拟器」：仿照 CSAPP Cache Lab 的 Part A，编写一个支持可配置容量、组相联度、缓存行大小的模拟器，读取 trace 文件（每行一个内存地址），统计命中、未命中、驱逐次数，并实现 LRU 替换。用几个手工构造的 trace 验证：全命中序列、抖动序列（循环访问略大于缓存的地址集）、步长序列。第三阶段「矩阵转置优化」：仿照 Cache Lab 的 Part B，为一个 256×256 的 int 矩阵实现转置函数，目标是最小化 L1（32KB，8 路）未命中数。朴素的逐元素转置会产生大量冲突未命中，你需要实验分块大小（8×8、16×16、32×32），处理对角线块的特殊情况，最终把未命中数降到理论下限附近。提交实验报告时，要求用 perf 或模拟器数据证明每一步优化的效果，并解释为什么某个分块大小最优——这个解释过程正是把缓存理论内化为工程直觉的关键。