玻尔百科在计算世界中，一场与时间的战斗从未停息。处理器（CPU）的速度已变得惊人地快，但它们却常常需要等待数据从速度慢得多的主存储器（RAM）中送达。硬件缓存——一个小型、高速的存储缓冲区——是这场战斗中的主要武器，它将频繁使用的数据存储在靠近CPU的地方。当CPU在缓存中找到所需数据时，即为“缓存命中”，工作得以全速进行。而当找不到时，即为“缓存未命中”，这是一次代价高昂的停顿，会降低性能。然而，并非所有的未命中都是相同的。解锁卓越性能的关键在于诊断未命中发生的原因。
本文旨在弥合“仅仅知道发生了一次未命中”与“理解其根本原因”之间的关键知识鸿沟。通过剖析缓存未命中，我们可以将性能调优从一场猜谜游戏转变为一门科学。我们将探讨缓存未命中的“3C”基础模型，这是计算机体系结构的基石。首先，在“原理与机制”一章中，我们将定义并区分三种主要的未命中类型：强制性（Compulsory）、容量性（Capacity）和冲突性（Conflict）。我们将揭示系统如何巧妙地诊断一次未命中属于哪一类别。随后，“应用与跨学科联系”一章将揭示这些知识如何成为程序员、编译器设计者和系统架构师的强大工具，从而实现从代码结构到操作系统内存管理的一系列优化。
要理解什么是强制性未命中，我们必须首先踏上一段小小的旅程，进入计算机的核心，探寻处理器与其内存之间永恒的舞蹈。想象一位技艺精湛的工匠——我们的CPU——以令人难以置信的速度工作。这位工匠需要工具和材料，这些都存放在一个巨大而杂乱的仓库里——即计算机的主存或RAM。问题在于，仓库距离遥远且存取缓慢。每一次去仓库都意味着代价高昂的延迟，迫使我们手速飞快的工匠停下来等待。
为了解决这个问题，我们在工匠旁边放置了一个小巧、井井有条的工作台。这就是缓存。工作台存放着少量最常用的工具和材料。当工匠需要某样东西时，他们首先检查工作台。如果东西在上面——即缓存命中——工作便能不间断地继续。如果不在——即缓存未命中——工匠就必须叹口气，停下工作，长途跋涉去仓库取回，并将其带回工作台以备将来使用。
每一次未命中都是一次性能损失。但所有的未命中都生而平等吗？它们都讲述着同样的故事吗？计算机架构师的卓越洞见在于，它们并非如此。通过诊断未命中的原因，我们可以理解我们的程序和机器更深层次的行为。这引出了一个强大的诊断框架，即缓存未命中的“3C”模型：强制性（Compulsory）、容量性（Capacity）和冲突性（Conflict）。
让我们回到那位工匠和他的工作台。通过分析为什么需要的工具不在工作台上，我们可以发现三种罪魁祸首之一。
想象一下，我们的工匠开始一个新项目。工作台完全是空的。当他第一次需要一把特定的锤子时，它显然不在工作台上。他必须去仓库取。这就是一次强制性未命中。它是对一块数据（一个内存“块”）进行第一次引用时不可避免的未命中。这是一种“冷启动”开销。
无论工作台有多大或设计得多么巧妙，对一个独一无二物品的首次访问总是会导致未命中。因此，一个程序所经历的强制性未命中总数是固定的，等于它首次接触的唯一数据块的数量。这个数量代表了未命中次数的一个基本下限；这是使用新数据的入场费。
考虑一个程序，它首次读取一系列全新的数据块，比如块[0, 4, 8, 12, ...]。当最初为空的缓存遇到每个块时，它别无选择，只能从内存中获取它。这些初始访问中的每一次都会导致一次强制性未命中，从而逐块填充缓存。
现在，想象我们的工匠正在处理一项复杂的任务，需要许多不同的工具——比如5种不同类型的扳手。但是工作台，也就是我们的缓存，一次只能放4个工具。工匠取来了扳手1、2、3和4，工作台满了。为了取扳手5，他必须把其中一个放回去。假设他放回了扳手1。片刻之后，他又需要扳手1。它已经不在了！他必须再回仓库去取。这是一次容量性未命中。
容量性未命中的发生是因为程序正在活跃使用的数据集——即其“工作集”——大于缓存的总容量。缓存实在太小，无法同时容纳处理器需要的所有东西，迫使它不断地驱逐那些很快又会需要的数据。容量性未命中的一个关键特征是，即使缓存组织得再完美，即“全相联”缓存，这种未命中仍然会发生。问题不在于组织方式，而在于根本性的空间不足。
这是最微妙，也常常是最令人沮丧的一种未命中。假设我们的工作台不只是一个大平面，而是一个抽屉柜，每个抽屉都指定用于存放特定类型的工具。有一个“锤子”抽屉，一个“螺丝刀”抽屉，等等。这种按“组”进行的组织方式是大多数现实世界缓存的工作原理。内存中的一个地址并不会被放入缓存的任意位置，而是映射到一个特定的组。
现在，假设工匠需要5种不同的螺丝刀来完成一项工作，但螺丝刀抽屉（即那个组）只有2个槽位。他取来了前两把。当他需要第三把螺丝刀时，他必须从那个抽屉里驱逐前两把中的一把，即使锤子抽屉完全是空的。片刻之后，他又需要那把被驱逐的螺丝刀。又是一次未命中！这就是一次冲突性未命中。
当缓存有足够的总空闲空间来容纳数据，但数据必须放置的特定组已经满了时，就会发生冲突性未命中。这是由地址到组的不幸映射引起的冲突。一个反复访问少数几个恰好都映射到同一组的内存地址的程序，可能会遭受冲突性未命中的风暴，这种现象被称为“抖动”，即使总数据量很小且缓存大部分是空的。冲突性未命中的决定性特征是，如果缓存是全相联的——一个任何工具都可以放在任何地方的、巨大的、无组织的抽屉——那么这次未命中本应是一次命中。
理解这些未命中类型是一回事，测量它们则是另一回事。系统如何知道一次未命中是由于容量小还是冲突导致的？这正是计算机工程精妙之处的体现。标准方法涉及一个巧妙的思想实验，通常通过称为幽灵缓存或影子缓存的模拟工具来实现。
想象一下，在我们的真实硬件缓存旁边，我们运行一个“完美”缓存的模拟。这个理想缓存是全相联的（一个大抽屉，没有冲突），并且总容量与我们的真实缓存完全相同。现在，当真实缓存发生未命中时，我们可以进行一个简单的诊断：
首先，我们检查一个我们曾见过的所有块的主列表。如果未命中的块不在这个列表上，说明这是我们第一次接触它。诊断很简单：强制性未命中。
如果我们以前见过这个块，我们接着查询我们理想的、全相联的幽灵缓存。
这个优雅的算法提供了一个明确的分类。当然也存在其他巧妙的技术。例如，可以分析一个程序的内存访问轨迹，然后在随机打乱内存地址后重复分析。这种打乱破坏了导致结构化冲突的地址模式。打乱后消失的未命中次数，给出了冲突性未命中数量的一个有力估计，揭示了它们是结构性问题的产物。通过设计有针对性的微基准测试——那些流式处理新数据、或重用大于缓存的数据、或在单个组上产生抖动的小程序——工程师可以分离并测量每种未命中类型对整体性能的影响。
3C模型为单个缓存提供了一个极其清晰的框架。但真实的系统很少如此简单。它们具有缓存层级结构——一个微小、快如闪电的1级（L1）缓存，由一个更大、较慢的2级（L2）缓存支持，依此类推。在这样的系统中，新的、有趣的现象可能会出现。
许多系统强制执行包含策略：任何存在于L1缓存中的数据也必须存在于L2缓存中。这带来了一个奇怪的副作用。想象一个数据块愉快地驻留在L1和L2中。现在，对其他数据的大量访问导致了较大L2缓存中的容量性未命中，迫使我们的数据块从L2中被驱逐。由于包含规则，这次L2驱逐会向L1缓存发送一个命令：“使你那份数据块的副本无效！”
之后，当处理器再次请求那个数据块时，它发现该块已从L1中消失。这是一次未命中。但这是哪种未命中？它不是强制性的，因为我们以前见过它。从L1的角度看，它不是容量性未命中，因为L1可能还有大量空闲空间。它也不是冲突性未命中。它是一种新物种，诞生于缓存级别之间的交互：一次包含诱导的未命中（inclusion-induced miss）。
这揭示了科学和工程模型的真正本质。3C模型是一个强大且必不可少的工具。但随着我们构建更复杂的系统，我们必须准备好观察新现象，并完善我们的模型以解释更丰富的现实。从一次简单的强制性未命中到多级缓存层级中错综复杂的舞蹈，这段旅程完美地诠释了这种对理解永无止境、不断深化的追求。
在我们迄今的旅程中，我们已经见识了缓存性能这出戏剧中的各个角色：不可避免的强制性未命中、不幸的容量性未命中和令人沮丧的冲突性未命中。人们很容易将强制性未命中——即我们首次接触一块数据时发生的未命中——视为一种不可避免的“入场费”而不予理会。毕竟，如果数据不在缓存中，就必须去获取它。还有什么可说的呢？
事实证明，还有很多可说的。理解计算机系统的真正魔力不在于消除所有未命中——因为强制性未命中确实是一项基本成本——而在于将可避免的未命中转变为不可避免的未命中的艺术。通过区分未命中的性质，我们就能掌握诊断性能问题的知识，并在许多情况下设计出优雅的解决方案。在这种视角下，强制性未命中成为我们的基线，是我们希望对数据的每一次后续访问都能达到的理想状态。这一视角将带领我们进行一次跨越计算机科学领域的奇妙之旅，从我们编写代码的方式，到操作系统如何指挥整台机器。
让我们从程序员的世界开始。你可能认为代码的性能取决于算法的精妙程度，但仅仅是你在内存中组织数据的方式，就可能产生惊人的后果。
想象你正在管理一个记录列表，每个记录都有几个字段——比如位置 、速度 和加速度 。一种自然的结构化方式是“结构数组”（Array of Structures, AoS），其中数组的每个元素都是一个包含 的完整记录。当你的代码处理第 个粒子时，它会访问 ，然后是 ，再然后是 。由于这些字段在内存中紧密相邻，它们几乎肯定会落入同一个缓存行。对 的第一次访问会触发一次强制性未命中以加载该行。但随后，对 和 的后续访问将是闪电般的命中！你为每行支付了一次“入场费”，并 reaping了其好处。
但如果你将数据组织成“数组结构”（Structure of Arrays, SoA）会怎样？在这种情况下，你将有三个独立的大数组：一个用于所有位置 ，一个用于所有速度 ，一个用于所有加速度 。要处理第 个粒子，你的代码现在从数组 中的一个地址跳转到数组 中的一个地址，然后再跳转到数组 中的一个地址。如果命运弄人（或者更可能的是，仅仅由于内存分配的机制），、 和 的内存位置恰好都映射到缓存中的同一个组，你就制造了一场灾难。如果该缓存组无法同时容纳这三个缓存行，你将先为 遭遇一次强制性未命中，然后是 （它会驱逐 ），接着是 （它会驱逐 ），如此循环，陷入一场无情的冲突性未命中风暴。你的数据结构将一次愉快的内存漫步变成了一场交通堵塞。
这个原则不仅适用于数据，也适用于构成你程序的指令本身。CPU的指令缓存和数据缓存的行为一样。考虑一个庞大的switch-case语句。当你第一次跳转到一个case分支时，你需要支付一次强制性未命中来加载该分支的代码。但是，当你在源文件中相距甚远的case分支之间跳转时会发生什么？如果编译器将它们的机器码放在了恰好会在指令缓存中发生冲突的地址上，你就可能制造出与数据抖动相同的问题[@problemid:3625381]。这揭示了一个深刻的真理：编译器或链接器在布局代码时的工作，不仅仅关乎正确性，更关乎性能考古学，即合理安排程序的各个部分，使它们能与将要运行的硬件和谐共处。
如果程序员和编译器可以玩这个游戏，那么系统架构师也可以。通过理解未命中的类型，他们可以创造出新的规则，给予软件更多的控制权。
一个绝佳的例子是“非临时性”或“流式”存储指令。想象一个程序，它读取一个需要重用的数据块（我们称之为数组 ），然后写出一个巨大的日志文件或视频流（数组 ），而这个程序再也不会读取数组 。一个采用“写分配”策略的标准缓存，在看到对数组 的第一次写入时，会说：“啊哈，一次强制性未命中！”，然后尽职地将对应的（但毫无用处的，因为我们即将覆盖它）内存行从内存加载到缓存中。随着这个过程的继续，缓存被数组 的行填满。当程序最终循环回来重新读取数组 中的宝贵数据时，它发现 已经被为 腾出空间而驱逐了，导致一连串的容量性未命中。
一条非临时性存储指令优雅地回避了这个问题。它告诉硬件：“我知道这个数据没有时间局部性。不要费心把它放进缓存；直接把它写入主内存。”从缓存的角度看，与写入 相关的强制性未命中就此消失了。通过有意识地为流式数据选择“绕过”缓存，我们为数组 中的数据保留了缓存有限的空间，将原本代价高昂的容量性未命中转化为了命中。这是一个基于对不同未命中类型清晰理解而做出的精妙权衡。
这引出了一个更微妙的观点：我们的定义本身可能与游戏规则相关。在一个采用“非写分配”策略的缓存中会发生什么？在写未命中时，数据被发送到内存，但对应的行不会被带入缓存。在这里，对一个块的第一次写入仍然是一次强制性未命中——这是第一次引用。但对同一个块的第二次写入呢？它同样会未命中，不是因为冲突或容量问题，而仅仅是因为缓存的策略禁止它存在于缓存中。我们信赖的指南——3C模型，突然发现自己进入了一个它未曾设计的领域，这表明我们的模型的好坏取决于它们所基于的假设。
如果我们将此推向逻辑的极致，给予程序员完全的控制权会怎样？这就是软件管理的便签式存储器（scratchpad memory）的世界，它常见于许多数字信号处理器和GPU中。程序员不是让硬件缓存自动猜测要保留哪些数据，而是显式地发出命令（如DMA传输）将数据块从主内存移动到这个快速的本地便签式存储器中。在这个世界里，冲突和容量性未中的概念都消失了。每一次数据传输都是一次深思熟虑的、由程序员发起的行为，类似于一次强制性未命中。通过精心编排这些传输，程序员可以保证零命中率是不可能的，通过手动管理其工作集来获得可预测的高性能[@problemid:3625359]。这凸显了自动硬件缓存的便利性与显式软件控制的原始、可预测能力之间的基本设计权衡。
到目前为止，我们已经看到了程序员、编译器和架构师如何努力管理未命中。但在这首交响曲中，最强大的演奏者或许是操作系统（OS）。
操作系统处在一个独特的制高点：它管理着虚拟内存（程序所看到的）到物理内存（硬件所看到的）的映射。这种能力允许一种极其聪明的优化，称为页着色（page coloring）。正如我们所见，当不同的数据块映射到同一个缓存组时，就会产生冲突性未命中。但是什么决定了组呢？是物理地址。而又是什么决定了物理地址？是操作系统！
想象一个程序，就像我们的SoA例子一样，访问八个不同的数组，而它们恰好都映射到同一个4路缓存组，导致了严重的冲突性未命中。操作系统能够看到这一点（或者被设计成可以预防它）。当程序请求第五个数组的内存时，操作系统可以不给它另一个相同“颜色”的物理页（即，其地址映射到相同缓存组的页），而是选择一个不同颜色的页。通过将八个数组中的每一个都分配给不同颜色的页，操作系统可以确保它们都映射到不同的缓存组。冲突就这样神奇地消失了。在第一轮八次不可避免的强制性未命中之后，每一次后续访问都变成了命中。这是一个令人惊叹的跨层优化范例，其中操作系统扮演着一位仁慈的指挥家，通过编排内存布局来帮助硬件发挥最佳性能。
这种以缓存为中心的世界观所具有的统一力量是显著的。完全相同的原则不仅适用于数据和指令，也适用于内存地址转换本身。转译后备缓冲器（Translation Lookaside Buffer, TLB）本质上就是一个用于虚拟到物理页地址转换的缓存。当一个程序第一次接触一个新的内存页时，它会遭受一次强制性的TLB未命中。是的，一个不幸的虚拟页访问序列也可能在TLB中引起冲突性未命中，就像我们在数据缓存中看到的那样。从数据到代码再到地址本身，这种模式不断重复。
最后，我们将视野拓宽到多核处理器的现代现实中。在这里，一个新角色登上了舞台：一致性未命中（coherence miss）。一个核心可能在其私有缓存中拥有一个数据行，却发现它消失了。它不是因为容量不足或冲突而被驱逐；它是被无效化了，因为另一个核心需要写入同一行。这为我们的模型引入了“第四个C”，并且是并行编程的核心挑战。这种一致性的舞蹈通常始于每个核心支付自己的强制性未命中以获取数据的本地副本。接下来发生的是一个关于共享、所有权和无效化的复杂协议，它决定了未来的命中与未命中。有时，无效化是出于正当理由（“真共享”，即核心协作处理相同数据）。而其他时候，它是不良数据布局的产物（“伪共享”，即不相关的数据项恰好共享一个缓存行），这与我们那位老朋友——AoS与SoA的问题——遥相呼应，但现在的后果要严重得多。
最后，我们回到了起点，但带着全新的眼光。强制性未命中不仅仅是一个需要记忆的定义。它是对系统性能进行深入而实用理解的锚点。它是入场的成本，是第一次将数据带入计算之光的代价。构建快速软件和硬件的艺术，就是尽可能确保这第一次成本是唯一的成本，将一个充满冲突和限制的混乱世界转变为一条可预测的发现之流的艺术。