What Every Programmer Should Know About Memory

缓存的基本原理

在开始深入缓存的细节之前，让我们先回到一个令人不安的历史事实：过去四十年里，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、缓存优化——的坚实基础。

地址翻译与页表

如果说缓存是硬件工程师给程序员的礼物，那么虚拟内存就是操作系统给程序员的礼物——而且是一份更宏大、影响更深远的礼物。想象一下没有虚拟内存的世界：每个程序必须知道自己被加载到物理内存的哪个位置，所有指针都是物理地址；两个程序不能同时使用同一块内存区域，除非小心翼翼地手工划分；一个野指针可以直接改写操作系统的内核数据，整个系统随之崩溃。1960 年代的程序员确实生活在这个世界里，那时的「内存冲突」是系统崩溃的头号原因。虚拟内存的构想诞生于 1965 年前后的 Multics 项目——这个由 MIT、贝尔实验室和通用电气联合开发的雄心勃勃的系统，虽然商业上失败了，却留下了两项改变计算历史的遗产：分时系统和虚拟内存。1969 年的 GE 645 机器第一次在硬件层面支持了按页的虚拟内存，此后这一机制被 Unix、Windows 和所有现代操作系统继承。 | 翻译组件 | 位置 | 容量 | 命中延迟 | 未命中代价 | 作用 | |---------|------|------|---------|-----------|------| | TLB (L1) | CPU 内部 | 64-128 条目 | 0 周期 (命中) | 查 L2 TLB | 缓存最近翻译 | | TLB (L2) | CPU 内部 | 1024-2048 条目 | ~5 周期 | 遍历页表 | L1 未命中后备 | | 一级页表 (PGD) | 主存 | 512 条目/页 | ~300 周期 | - | 指向 PUD | | 二级页表 (PUD) | 主存 | 512 条目/页 | ~300 周期 | - | 指向 PMD (或 1GB 大页) | | 三级页表 (PMD) | 主存 | 512 条目/页 | ~300 周期 | - | 指向 PTE (或 2MB 大页) | | 四级页表 (PTE) | 主存 | 512 条目/页 | ~300 周期 | - | 指向物理页帧 | | 完整页表遍历 | 主存 | 4 级 | ~1200 周期 | TLB 未命中时 | 最坏情况翻译 | 虚拟内存的核心思想出奇地简单：在程序和物理内存之间插入一个「翻译层」。程序看到的每个地址都是虚拟地址，CPU 中的 MMU（内存管理单元）在每次访问时把虚拟地址翻译成物理地址。这个看似简单的机制带来了四大革命性优势。第一是隔离：每个进程拥有独立的地址空间，进程 A 的指针 0x1000 和进程 B 的指针 0x1000 映射到完全不同的物理页，一个进程的越界访问不可能伤害另一个进程——这是现代操作系统安全模型的基石。第二是共享：需要共享时，操作系统可以让多个进程的虚拟页映射到同一个物理页，共享库的代码段就是这样被上百个进程共享而只占一份内存的。第三是抽象：程序员看到一个连续的、从固定地址开始的巨大地址空间，不需要关心物理内存的碎片化和实际布局，链接器也因此可以假设固定的加载地址。第四是按需分配：程序可以申请远超物理内存的虚拟空间，页面只在第一次真正访问时才分配物理内存（缺页异常），这使得内存使用率大幅提升，也让「分配 1GB 数组但只用前 1MB」这样的操作几乎零成本。 但天下没有免费的午餐。每次内存访问都要翻译地址，如果翻译本身需要访问内存中的页表，那么一次数据访问就变成了两次甚至五次内存访问，性能将不可接受。硬件和操作系统为此发展出了一整套精密的加速机制：多级页表把翻译结构组织成按需分配的树，TLB 把最近的翻译结果缓存在 CPU 里，大页把翻译的粒度从 4KB 提升到 2MB 甚至 1GB。Drepper 在论文中特别强调，TLB 是程序员最容易忽视又最容易踩坑的组件——一个在缓存层面表现完美的程序，可能因为 TLB 未命中率过高而性能腰斩。本章将沿着「地址空间布局 → 页与页表 → 翻译过程 → TLB → 缺页异常 → mmap 与 COW → 交换空间」的线索，把虚拟内存的完整图景展开在你面前。

多处理器系统的内存架构

让我们把时钟拨回 1980 年代。那时的多处理器系统采用一种叫 UMA（Uniform Memory Access，一致性内存访问）的架构：所有 CPU 通过一条共享总线连接到同一块内存。总线的仲裁机制保证每个 CPU 访问内存的延迟相同——听起来很公平，但这条总线很快成了整个系统的瓶颈。想象一条单车道公路连接着一个拥有 32 户人家的小区：无论每户的出行需求多小，所有车辆都必须排队通过这条唯一的道路。CPU 数量翻倍，总线争用不是翻倍而是平方级恶化，4 路以上的 UMA 系统几乎无法扩展。1980 年代的 SGI、Sequent、Encore 等公司给出了激进的替代方案：NUMA（Non-Uniform Memory Access，非一致性内存访问）——把内存分散到各个 CPU 旁边，每个 CPU 访问「自己」的内存很快，访问「别人」的内存要经过互连网络，慢一些但可行。SGI 的 Challenge/Origin 系列是 NUMA 的巅峰之作，Origin 3000 可以扩展到 1024 个处理器，在 1990 年代末的超级计算机领域独领风骚。 | 架构类型 | 内存访问延迟 | 可扩展性 | 编程复杂度 | 典型规模 | 代表系统 | |---------|------------|---------|-----------|---------|---------| | UMA (共享总线) | 一致 (~100ns) | 差 (总线瓶颈) | 低 (透明) | 1-4 路 | 早期 SMP | | NUMA (互连网络) | 本地 80-100ns / 远程 120-200ns | 优 (线性扩展) | 高 (需感知) | 8-1024 路 | 现代服务器 | | cc-NUMA (缓存一致) | 本地 ~80ns / 远程 ~150ns | 良 | 中 (硬件辅助) | 8-64 路 | AMD EPYC | | 分布式 (无共享) | 本地 ~80ns / 网络 ~us 级 | 极好 | 高 (显式通信) | 数千节点 | 集群/MPI | 历史绕了一个有趣的圈。2000 年代中期，随着多核处理器的普及，NUMA 以另一种形式回归主流：每个 CPU 插槽（Socket）拥有自己的内存控制器和直连的内存条，插槽之间通过 Intel 的 QPI/UPI 或 AMD 的 Infinity Fabric 互连——这本质上就是一个 2 路、4 路或 8 路的 NUMA 系统。今天你购买的任何一台双路服务器都是 NUMA 机器；AMD EPYC 处理器甚至在单个插槽内部就划分出多个 NUMA 节点（每个 CCD 或每个内存通道组一个节点）；ARM 服务器芯片如 Ampere Altra、鲲鹏 920 同样是 NUMA 架构。换句话说，NUMA 不再是超算专属的 exotic 技术，而是每个后端工程师的线上服务器正在运行的现实。Drepper 在 2007 年写这篇论文时，NUMA 编程还属于小众技能；今天，不理解 NUMA 的工程师已经无法解释「为什么同一个服务在两台配置相同的机器上性能差 40%」这类问题——答案往往是进程被调度器迁移到了远程节点，或者内存被分配在了错误的节点上。 NUMA 的性能差异有多大？典型的双路服务器上，访问本地内存的延迟约 80-100 纳秒，访问远程内存约 120-200 纳秒，比值 1.5 到 2.5 倍；带宽差异更悬殊，远程带宽通常只有本地的 50%-70%，因为互连链路比内存总线窄。对于内存密集型应用——数据库、缓存、大数据处理、科学计算——这意味着错误的内存放置可以让性能损失 30%-50%。更麻烦的是，NUMA 问题是「隐形」的：程序逻辑完全正确，功能测试全部通过，只有性能悄悄劣化，而且劣化程度随负载和调度时机波动，极难复现。本章将讲解 NUMA 的硬件原理、Linux 内核的 NUMA 支持（内存策略、第一触及、自动均衡）、numactl 等用户态工具，以及数据库系统的真实优化案例，帮助你建立「NUMA 感知」的编程思维。

数据局部性优化

前三章我们一直在「理解」内存系统：缓存如何工作、虚拟内存如何翻译、NUMA 如何分布。现在到了收获的季节——这一章回答全书最实用的问题：作为一个程序员，我到底能做什么？Drepper 在论文的第 6 章给出了一个振聋发聩的观点：在摩尔定律红利逐渐消退、主频停止增长的时代，软件性能的提升越来越依赖于「让代码适配硬件」，而其中最大的一块红利就藏在缓存里。同一台机器上，缓存友好与缓存敌对的代码之间，性能差距 routinely 达到 10 倍——这相当于免费获得了一台快十倍的机器，唯一的代价是程序员的知识。 | 优化技术 | 原理 | 适用场景 | 典型加速比 | 实现难度 | |---------|------|---------|-----------|---------| | AoS→SoA 转换 | 消除缓存行中的冷数据 | 批量同字段更新 | 3-7x | 中 | | 热冷数据分离 | 高频字段紧凑打包 | 混合访问模式 | 2-4x | 低 | | 循环分块 (Tiling) | 工作集适配缓存容量 | 矩阵运算 | 2-10x | 中 | | 行优先遍历 | 匹配内存连续布局 | 多维数组 | 5-50x | 低 | | 伪共享消除 | alignas(64) 隔离 | 多线程计数器 | 5-10x | 低 | | 软件预取 | __builtin_prefetch | 可预测访问模式 | 1.5-3x | 中 | | 大页 (Huge Pages) | 减少 TLB 未命中 | 大内存应用 | 1.2-2x | 低 | | 链表→数组 | 消除指针追逐 | 遍历密集型 | 10-100x | 中 | 让我们先建立一个正确的心智模型：优化缓存不是零散的技巧堆砌，而是一套有层次的方法论。最底层是数据结构的选择——数组的缓存效率天然碾压链表，这个决策的影响超过之后所有微观优化的总和。中间层是访问模式的组织——行优先还是列优先遍历、循环嵌套的顺序、分块的大小，这些决定了缓存行和 TLB 的利用率。最上层是多线程的数据布局——每个线程的私有数据是否独占缓存行、共享数据的一致性流量有多大，这决定了并行扩展性。伪共享（False Sharing）是最高层问题的典型代表：两个线程各自修改自己的变量，逻辑上毫无共享，却因为变量恰好落在同一个 64 字节缓存行内，导致该行在两个核心的缓存之间被 MESI 协议反复无效化和搬运，性能可能劣化 5-10 倍。这个问题如此隐蔽——代码看起来完全正确，profiler 的 CPU 占用也正常，只有 cache-to-cache 传输计数器能揭露真相——以至于它成为多线程性能调优的「必查项」。 本章还将介绍一些更高级的武器。循环分块（Loop Tiling）通过把大循环切成能装进缓存的小块，同时榨取时间局部性和空间局部性，是矩阵运算优化的基石；缓存无关（Cache-Oblivious）算法用递归分治的方式自动适配所有层级的缓存，无需知道任何硬件参数，Strassen 矩阵乘法和递归矩阵转置是其代表；软件预取指令让程序显式告诉硬件「我马上要用这块数据」，把未命中延迟隐藏在当前计算之后；alignas 和对齐分配则确保关键数据结构不会跨缓存行分裂。最后，我们会系统介绍测量工具链——perf、cachegrind、VTune——因为 Drepper 和所有性能工程师都同意一条铁律：没有测量就没有优化。凭直觉优化缓存几乎总是错的，现代处理器的预取器、乱序执行和缓存层次复杂到超出任何人的直觉。这一章的目标，是让你带着「局部性思维」和「测量习惯」两样工具，回到日常编程中去。