玻尔百科在对计算速度不懈的追求中，处理器已经变得惊人地快，每秒能够执行数十亿条指令。然而，这一进步造成了一种根本性的不平衡：主存（RAM）的速度未能跟上，从而产生了一道被称为“内存墙”的鸿沟。处理器频繁发现自己处于空闲状态，等待数据到达，这严重制约了应用程序的性能。本文旨在揭开高性能计算中最重要的概念之一——缓存局部性——的神秘面纱，以应对这一关键瓶颈。
为了在理论与实践之间架起一座桥梁，我们将开启一段分为两部分的旅程。首先，在“原理与机制”部分，我们将探讨局部性的基本定律，以及它们如何支配CPU、缓存和主存之间的相互作用。我们将剖析为什么某些数据结构（如数组）天生就快，而另一些（如链表）则可能慢得令人痛苦。其次，在“应用与跨学科联系”部分，我们将看到这些原理在实践中的应用，考察缓存感知编程如何在从科学计算、视频压缩到前沿人工智能等各个领域改变性能。读完本文，您将不仅理解理论，还能获得一种实践直觉，从而编写出与硬件和谐共存的代码，释放其真正的潜力。
想象一下，你是一位在一个巨大、 sprawling 的厨房里工作的大厨。你的灶台是所有烹饪活动发生的地方，它就是CPU——速度快得令人难以置信，每秒能执行数十亿次操作。然而，你的食材储存在大楼另一端的一个巨大储藏室里——这就是主存，即RAM。要做任何菜，你都必须先去取食材。问题就在这里：去储藏室的路程慢得令人痛苦。虽然你，这位大厨，可以在一瞬间切好一个蔬菜，但往返储藏室一趟在厨房时间里可能需要几分钟。如果每一样食材都需要一次单独、漫长的步行，你几乎所有的时间都会花在走路而不是做饭上。
这就是现代计算的核心挑战：处理器和主存之间的巨大速度差距。解决方案是什么？一个紧挨着灶台的小操作台，称为缓存。与储藏室相比，这个操作台很小，但访问速度快如闪电。通过巧妙地将你正在使用以及预计很快会需要的食材放在这个操作台上，你就可以避免大部分那些漫长而缓慢的步行。在很多方面，高性能计算的全部博弈可以归结为一件事：有效地使用这个操作台。支配其有效使用的原则被称为引用局部性。
缓存没有水晶球，它怎么“知道”该把什么放在操作台上呢？它并不知道；它靠的是概率。它基于在几乎所有程序中观察到的两种基本倾向进行押注，这就是局部性的两大定律。
时间局部性（重用法则）： 如果你现在使用了一个食材，你很可能在不久的将来再次使用它。想想盐瓶。你不会用一次就把它放回储藏室；你会把它留在操作台上，因为你还会再需要它。缓存会保留最近访问过的数据，押注它会被再次需要。
空间局部性（邻近法则）： 如果你使用了一个食材，你很可能会使用储藏在它旁边的其他食材。如果你从一袋胡萝卜里拿了一根，你很可能需要同一袋里的另一根。硬件在这个原则上做出了一个强有力的押注。当CPU请求内存中的一个字节数据时，内存系统不会只发送那一个字节。它会发送一个连续的数据块，通常是64字节，称为一个缓存行。
缓存行的概念或许是理解性能最重要的单一概念。如果你的数据由8字节的数字组成，那么一次内存访问就能带回八个数字，并摆在你的操作台上。如果你的程序接下来请求序列中的下一个数字，它已经在那儿了——这就是一次“缓存命中”——其访问速度比需要再次前往储藏室的“缓存未命中”快数百倍。作为一名有性能意识的程序员，你的工作就是编写代码，让硬件在空间局部性上的押注尽可能频繁地获胜。
那么，我们该如何安排数据来赢得这场赌局呢？这个问题将我们引向数据结构世界的一个巨大分水岭，它根据数据在内存中的存储方式将它们区分开来。
一边是连续数据结构，如数组。数组就像储藏室里一个组织完美的架子，所有某种香料的罐子都排成一排。当你访问其中一个时，整排（或至少一部分）都会被带到你的操作台上。遍历数组就像用手滑过那个架子——你下一个需要的每样东西都在那里。这是空间局部性的缩影。
另一边是基于指针的或分散的数据结构。想想链表、树和哈希表。在这些结构中，每个元素（一个“节点”）都是一个可以存储在储藏室任何地方的独立项。每个节点都包含一张纸条，告诉你去哪里找下一个。遍历链表不是平滑的滑动；它是一场寻宝游戏。你到一个地方，拿起一个食材和一条线索，然后冲向储藏室一个完全不同且可能很远的地方去取下一个。每一次“跳跃”都可能是一次缓存未命中。这种“指针追逐”是高性能的天敌。
这种差异并非微不足道。考虑一个简单的队列，可以用连续的循环数组或链表来实现。在稳定状态下，基于数组的队列数据可以很好地放入缓存中。操作很快，因为队列的头部和尾部总是在操作台上“热”着。然而，基于链表的队列每次入队都会从堆中分配一个新节点。这个新节点很可能位于内存中一个全新的、“冷”的区域。入队和出队操作几乎都保证会发生缓存未命中，可能导致处理器为每个操作停顿数百个周期。
我们甚至可以量化这场灾难。想象一个链表，由于内存分配的方式，每个节点恰好与下一个节点相距128字节。如果我们的缓存行大小是64字节，那么物理上就不可能让两个连续的节点位于同一个缓存行中。遍历这个链表的每一步都将导致一次缓存未命中。然而，一个简单地读取相同数据的连续数组的程序，每个缓存行可能获取8个元素，导致每八次访问才发生一次未命中。链表不仅仅是差一点；它可能产生8倍的缓存未命中[@problem_o_id:3255658]。这就是糟糕的空间局部性所带来的实实在在的、惩罚性的代价。
一旦你开始将内存看作不是一个抽象的变量集合，而是一个物理的缓存行序列，你就能解锁巨大的性能提升。这种思维方式催生了几种强大的设计模式。
想象一本书，它的文本不是按行存储，而是按列存储。要阅读它，你必须先读页面上每一行的第一个字母，然后是每一行的第二个字母，以此类推。这会慢得离谱。这正是我们在以错误的顺序访问多维数组时所做的事情。
在像C++、Python（使用NumPy）和Java这样的大多数语言中，一个二维数组A是以行主序存储的：第0行完整地排列，然后是第1行，以此类推。现在考虑这段对元素求和的简单代码：
for i = 0 to N-1: for j = 0 to M-1: sum += A[j][i]
在这里，内层循环保持列i不变，并在行j之间跳跃。在内存中，这意味着访问A[0][i]，然后跳过一整行字节的距离到达A[1][i]，然后再跳一整行到达A[2][i]。这被称为大步幅，它彻底破坏了空间局部性。解决方法简单而深刻：循环交换。
for j = 0 to M-1: for i = 0 to N-1: sum += A[j][i]
通过交换循环，内层循环现在对固定的行j遍历列i。它访问A[j][0], A[j][1], A[j][2], ... 这些元素在内存中都是紧挨着的。这是一种单位步幅访问，是可能的最缓存友好的模式。这不是微优化；它可以使代码运行速度提高十倍。一个花费大部分时间扫描棋盘行（rank）的现实世界国际象棋引擎，必须使用行主序布局才能具有竞争力，因为这使得行扫描成为单位步幅操作。
通常，我们的数据对象包含多个字段，但某个特定算法只需要其中一两个。假设我们正在管理一个二叉堆，每个元素都有一个小的key和一个非常大的payload。sift-down操作对堆的性能至关重要，但它只需要比较key。
如果我们将数据存储为struct { key; big_payload; }的数组，这种模式称为结构体数组（AoS），我们就会遇到问题。缓存行被巨大而无用的payload数据填满。我们需要比较的下一个节点的key被推到内存中很远的地方，很可能在另一个缓存行中。我们正在用我们不使用的食材污染宝贵的操作台空间。
解决方案是一种称为数组结构体（SoA）的模式。我们不使用一个大的结构体数组，而是使用多个数组：一个只存放key的数组，另一个只存放payload的数组。现在，sift-down操作在key数组上进行，这是一个紧凑、连续的数据块，只包含它需要的数据。这极大地改善了空间局部性，并减少了交换期间移动的数据量。性能增益可能是巨大的，特别是当payload很大时。
从缓存局部性中学到的最重要的一课是，你在算法课上学到的抽象复杂度（大O表示法）并不总是能说明全部问题。它是在一个理想化的“随机存取机器”模型下运作的，该模型中所有内存访问的成本都相同。在现实世界中，这是危险的错误观念。
一个经典的例子出现在动态规划中。对于一个具有密集、矩形子问题集的问题，你可以将计算结果（记忆化）存储在哈希表或简单的二维数组中。理论上，哈希表提供平均情况下的查找。听起来很棒，对吧？但是哈希函数在设计上会将逻辑上相邻的键（如和）分散到内存中的伪随机位置。每次查找都是一次跳跃——一次潜在的缓存未命中。
另一方面，二维数组将这些状态连续存储。一个自底向上、通过迭代数组来制表的解决方案将具有优美、顺序的访问模式。它充分利用了空间局部性，对于自动获取即将到来的缓存行的硬件预取器来说简直是梦想。结果呢？“更慢”的数组访问可以完胜“”的哈希表，有时其优势因子等于一个缓存行中的元素数量——在典型情况下是8倍。抽象模型撒了谎；机器的物理现实占据了主导地位。
从缓存到数据布局模式的这段旅程揭示了一个深刻的真理：我们组织数据的方式不仅仅是一个实现细节。它是与硬件的一次根本性对话。算法及其数据结构不是分离的东西；它们是一对，必须与机器的物理现实和谐地设计。
这并不意味着我们抛弃其他一切。一个具有更好算术复杂度的算法，比如用于多项式求值的霍纳方案，仍然会比朴素方法更快，即使两者对其系数都有相同且缓存友好的访问模式。目标是将算术高效的逻辑与尊重局部性的数据组织方式结合起来。
理解内存层次结构并不要求你成为一名硬件工程师。它要求你有点像物理学家，能够看到你的代码和它所接触的数据之间的“超距作用”。通过看清你的程序所造成的无形寻宝游戏和浪费的操作台空间，你可以改造它们。你可以编写出不仅能运行，而且能与硅片协同流动的代码，实现一种感觉不像是工程学，而更像是优雅的性能。
我们已经学习了计算机处理器与其内存之间那场奇妙而怪异的游戏规则。我们了解了微小而快如闪电的缓存——CPU的私人作坊，以及广阔而迟缓的主存平原——一个需要永恒时间才能访问的仓库。我们理解了局部性原理——时间局部性和空间局部性——这是确保处理器作坊在正确的时间备有正确材料的秘诀。
但是，了解规则是一回事；玩好这场游戏则是另一回事。一个笨拙、缓慢的算法与一个优雅、快速的算法之间的区别，通常不在于它执行的计算次数，而在于它如何出色地编排数据在内存和处理器之间那场无形的舞蹈。现在，让我们踏上一段穿越科学与工程世界的旅程，看看这一个深远的思想——局部性原理——如何无处不在地显现，从你屏幕上的像素到人工智能的前沿。
或许，玩好缓存游戏最简单却最强大的方法，是确保我们访问数据的顺序与它被存储的顺序相匹配。这听起来微不足道，但其后果却绝非如此。
想象一下，你正在使用著名的Floyd-Warshall算法计算地图上所有城市之间的最短路径。该算法涉及三个嵌套循环，通常遍历名为、和的索引。你可能会认为嵌套这些循环的顺序——例如k,i,j或k,j,i——只要最内层的计算是正确的，就只是个品味问题。但你就错了！如果你的地图数据（一个矩阵）在内存中是“逐行”存储的（一种称为行主序的布局，在C/C++和Python等语言中很常见），那么k,i,j的循环顺序要优越得多。在最内层循环中，它沿着一行扫描，访问在内存中连续排列的数据。每次缓存获取一行的一部分时，它都免费获得了一整块相邻的数据，从而带来了优美的空间局部性。相比之下，k,j,i的顺序迫使最内层循环每一步都向下跳一列。在行主序布局中，这意味着在内存中跨越巨大的间隙，几乎每一步都会导致缓存未命中。算法执行了相同数量的计算，但其性能却灾难性地差，完全是因为它未能尊重其数据的布局。
循环顺序和数据布局之间的这种“双人舞”出现在无数的科学代码中。例如，在执行LU分解时，两个流行的变体，Doolittle算法和Crout算法，具有微妙不同的访问模式。一个本质上是面向行的，另一个是面向列的。在使用行主序存储的系统上，Doolittle算法自然会表现得更好；在具有列主序存储的系统上（如Fortran使用的那些），Crout算法将占有优势。算法的正确选择不仅取决于数学，还取决于数字在内存中排列方式的平凡现实。
我们在一个更熟悉的领域看到了这一原则的实际应用：视频压缩。当视频编解码器执行运动补偿时，它通常需要从前一帧复制一个小的像素块，比如说。如果帧是按行主序存储的，并且复制循环逐行迭代，那么数据是顺序读取的。这对缓存来说是梦寐以求的。对于一个的块，它可能只需要16次缓存行获取。但如果同一帧是按列主序存储的，循环就必须跳过整个帧的高度（例如，像素）才能从一行中的一个像素到达下一个。这种步幅访问模式对缓存来说是一场噩梦，可能导致同一操作产生次缓存未命中。流畅的视频流和卡顿的画面之间的差异，可能就归结于访问模式和内存布局之间的这种简单对齐。
简单的重排序能让我们走得很远，但一个更深刻的策略是主动将我们的问题重构成缓存大小的块。这种技术，称为分块或瓦片化（tiling/blocking），是利用时间局部性的大师级课程。
典型的例子是矩阵乘法。一个朴素的算法可能会将矩阵的一整行与矩阵的一整列相乘。如果矩阵很大，这些行和列将不断地从缓存中被驱逐和重新获取。这就像试图通过先铺设一整行瓷砖，然后再铺设一整列瓷砖来铺设一个巨大的地板，并试图记住它们都在哪里相遇。你会把所有时间都花在来回走动上。
分块算法要聪明得多。它就像一个专业的瓦工，把一小堆瓷砖和砂浆带到地板的一小块区域。该算法将一个的小方块“瓦片”和一个对应的的瓦片加载到缓存中。这些瓦片的大小被选择得恰好足够小，以便与一个的结果瓦片一起舒适地放入缓存。然后，它执行这些小瓦片之间的所有可能乘法，尽可能多次地重用位于快速缓存中的数据，然后再丢弃它。然后，也只有到那时，它才会移动到下一块区域。这种策略极大地减少了访问慢速主存的次数。我们甚至可以根据缓存大小推导出最佳瓦片大小的表达式：它的大小要确保我们的三个工作瓦片正好能装下，从而最大化重用。
这种“分块”的思想不仅仅适用于抽象的矩阵。在计算化学中，分子动力学（MD）模拟涉及计算数百万个原子之间的力。一个关键的优化是将模拟盒子划分为一个单元格网格。代码不是逐一遍历每个原子及其邻居（这会导致分散的内存访问），而是可以被构造成处理相邻单元格对。它将两个相邻单元格的所有原子加载到缓存中，并一次性计算它们之间的所有相互作用。这在移动到下一个单元格对之前，最大化了原子数据的时间局部性。这本质上是在物理空间中的分块。
到目前为止，我们一直在调整算法以适应数据。但如果我们能够调整我们的数据以适应算法呢？我们选择表示信息的方式对缓存局部性有着直接而巨大的影响。
考虑快速傅里叶变换（FFT），数字信号处理的基石。经典的Cooley-Tukey算法有一个奇特的特性。在其早期阶段，它组合了彼此靠近的数据元素，表现出极好的局部性。但随着算法的进行，它需要访问的元素之间的“步幅”在每个阶段都会加倍。它开始以越来越大的幅度在内存中跳跃，破坏了空间局部性并导致一连串的缓存未命中。该算法所需的臭名昭著的“位反转”置换步骤更糟，它似乎随机地分散了内存访问。这种糟糕的缓存行为促使科学家们发明了替代方案，如Stockham自动排序FFT，它将计算重构为一系列对数据的顺序、流式处理，避免了混乱的访问模式并显著提高了性能。
在涉及稀疏矩阵——即大部分元素为零的矩阵——的科学计算中，分散数据的问题更为尖锐。这些矩阵可能源于现实世界网络的模型，如电网或社交网络。代表实际连接的非零元素可能散布在内存各处。试图操作这个矩阵的算法会像跳蚤一样跳来跳去，缓存性能极差。解决方案不是改变算法，而是重新组织数据本身。像Reverse Cuthill-McKee（RCM）这样的算法会智能地重新编号网络的节点。这种重新编号会对矩阵的行和列进行置换，以将非零元素紧密地聚集在主对角线周围，从而减少矩阵的“带宽”。结果呢？当算法访问一个元素及其邻居时，这些邻居现在在物理内存中也彼此靠近。这种对数据结构的“整理”可以使迭代求解器，如共轭梯度法，速度提高几个数量级。类似的想法也用于分子动力学，其中沿着“空间填充曲线”重新排序原子，将其3D空间邻近性映射到1D内存邻近性，再次显著提高了力计算期间的缓存性能。
即使是自适应排序算法Timsort（在Python和Java中默认使用），也暗地里是局部性的大师。它知道插入排序虽然对大数组很慢，但在能完全放入缓存的小数组上却快得令人难以置信。因此，Timsort的第一步是创建最小长度为min_run的已排序小“片段”。这个参数被调整为一个大小（如32或64个元素），这个大小是非常缓存友好的。它在一个特定的上下文中使用了“坏”算法，而在这个上下文中，由于局部性，它变得非常出色。
局部性原理在人工智能的前沿领域比任何地方都更为关键。驱动像ChatGPT这样的模型的Transformer架构，是建立在一种称为“缩放点积注意力”的机制之上的。在其朴素形式中，该机制需要创建一个巨大的“注意力矩阵”，其中是输入序列的长度。即使对于中等长度的文本，这个矩阵也过于庞大，无法装入任何GPU的内存中，从而造成了严重的性能瓶颈。
解决方案是一个完全依赖于局部性的、令人惊叹的算法巧思。聪明的实现并不会完全计算和存储这个巨大的中间矩阵，而是将整个操作流水线——分数计算、softmax和加权求和——融合成一个单一的分块内核。该内核以块的方式流式处理输入数据，计算最终结果的一部分，并丢弃中间值，从而根本不将完整的注意力矩阵写入内存。这是分块和时间局部性的终极体现，这一技术现在以FlashAttention等系统中的实现而闻名。毫不夸张地说，没有这种深刻的、感知局部性的洞察，今天的大型语言模型在计算上将是不可行的。
这个原理甚至延伸到更抽象的计算机科学概念，如持久化数据结构，它允许你在进行更新时保留数据结构的旧版本。如果你的访问模式表现出时间局部性——也就是说，你倾向于查询最近的版本——那么构成这些最近版本的节点将保持在缓存中“热”的状态。一个操作的成本于是变得与结构的总体复杂度无关，而只与你需要获取的数据的“冷”部分成正比，从而提供了强大的性能提升。
我们已经快速浏览了计算领域的全景，无论我们看向何处，都能发现相同而深刻的节奏。从视频编解码器中循环的结构化行进，到矩阵乘法的分块之舞；从模拟中原子的重新排序，到驱动AI的融合流式内核。这个教训是深刻而普适的：计算的结构必须尊重机器的结构。
局部性原理不是什么可以忽略的深奥硬件细节。它是现代计算中最基本的设计原则之一。任何领域的下一个伟大算法突破，很可能不仅仅来自一个新的数学思想，而是来自对这种优雅、本质且美妙的数据之舞的更深直觉。