如果你平时只关心算法的大 O 复杂度很少去想数据在内存里到底怎么排列那 Cache-Oblivious Data Structures 这个主题可能会颠覆你的一些习惯判断。我最近重读《Handbook of Data Structures and Applications》把其中关于缓存无关数据结构的部分拆成可运行的小实验这是系列笔记的第 6 个专题。简单说这一章研究的是在不知道缓存容量和缓存行大小的前提下怎么设计出对任意内存层级都表现良好的数据结构和算法。适合正在做存储引擎、数据库内核、高性能计算或者单纯被“缓存未命中”折磨过的同学。我从模型、核心设计、代码实现到 perf 实测都过了一遍下面直接说干货。1. 为什么“不知道缓存参数”反而更厉害1.1 传统复杂度分析漏掉了什么教科书里的二分搜索是 O(log N)这个结论默认每次内存访问都是等价的。但真实机器不是这样。内存访问走到 L1 Cache 大约 4 个周期L2 大约 12 个周期L3 大约 40 个周期主存则要 200 个周期以上。也就是说一次缓存未命中的代价可能比一次比较运算贵两个数量级。我之前在实际项目里遇到过一种很典型的场景一个有序数组上的二分搜索数据量到了一千万级别逻辑上只需要 24 次比较但耗时却从几十微秒涨到几百微秒。问题不在比较次数而在每次访问都跨到主存取数据。传统复杂度分析完全不体现这个开销因为它假设内存是均匀的。缓存未命中通常分为三种强制未命中、容量未命中和冲突未命中。强制未命中是数据第一次进缓存时必然发生的容量未命中是缓存装不下工作集导致的冲突未命中则和映射方式有关。数据结构设计者主要能优化的是前两种尤其是容量未命中。1.2 缓存感知与缓存无关的本质区别缓存感知设计常见的做法是手动指定分块大小。比如做矩阵乘法时把循环块大小设为 64 字节假设缓存行是 64 字节、L1 是 32KB再根据这些参数调优。这种方式在某一台机器上效果很好但换一个缓存行是 128 字节、L1 更大的 CPU原来的分块可能就不再最优。缓存无关设计思路完全不同算法内部不出现任何缓存参数它只依赖递归分解和内存布局的局部性让数据自然适配任意缓存层级。只要递归到某个深度时当前子问题的规模小于缓存行或缓存容量未命中率就会自动降下来。两者对比可以这样看设计方式是否知道 M/B移植性典型实现普通算法完全忽略缓存中常规二分、常规矩阵乘法缓存感知明确知道 M/B差换硬件需重调分块矩阵乘法、B 树缓存无关不知道但自适应好跨硬件保持渐进最优van Emde Boas 布局、Funnel 树B 树是缓存感知的典型它的节点大小按磁盘页或缓存行设计。缓存无关 B 树则不需要知道页大小它通过递归分块达到同样的搜索复杂度。1.3 理想缓存模型把问题数学化为了严谨地分析这类算法Frigo、Leiserson、Prokop 和 Ramachandran 在 1999 年提出了理想缓存模型。该模型假设计算机只有一级缓存容量为 M缓存行大小为 B内存无限且访问单位为缓存行。算法的代价用缓存未命中次数衡量并且假设缓存替换策略是理想最优的。这个模型看似简化得过分但它有一个关键的定理如果一个算法在这个模型下的缓存未命中复杂度最优那么它在任意真实的多级缓存层次上都渐进最优。原因是递归算法天然会把不同规模的工作集映射到不同层级的缓存上不需要每级缓存单独适配。理解这个定理只需要一个直觉你把一个递归算法想象成俄罗斯套娃每一层递归对应一个更小的子问题。当子问题小到能装进某个层级的缓存时这一层及以下的所有操作都变成缓存命中。理想模型相当于一次性验证了所有层级的适配性。2. 第 6 部分的核心设计逐个拆解2.1 van Emde Boas 布局二分搜索的缓存无关解van Emde Boas 布局是这一章最基础也最重要的内容。它解决的第一个问题是有序数组上的二分搜索能不能做到像 B 树一样只产生 O(log_B N) 次缓存未命中同时不显式分块做法是把一个大小为 N 的有序数组递归切块。先取块大小约等于 sqrt(N)把数组分成前后若干块然后递归地对每一块再次做同样的切分直到块大小足够小。内存排列时按块依次存放而不是按原数组顺序连续存放。举个例子N16 时块大小取 4总共 4 个块。内存布局的顺序是先存第 1 块的 4 个元素再存第 2 块的 4 个元素继续第 3 块、第 4 块。但每一块内部还要递归重排所以最终顺序并不是简单的前 4 个元素在一起。这样排列的意义在哪里二分搜索时我们通常认为访问路径是沿着索引折半跳跃的缓存命中率很低。但 vEB 布局把“搜索路径上相邻的节点”尽可能放到连续内存里。搜索进行到某个递归层次时当前子问题对应的元素就在一个连续区间内缓存行一次载入就能覆盖后续多次访问。复杂度分析是这本书里比较精彩的部分。普通二分搜索的缓存未命中是 O(log N)也就是每步都可能未命中。vEB 布局的二分搜索则是 O(log_B N)这里的 B 是缓存行能容纳的元素个数。假设缓存行 64 字节、元素 4 字节B16N2^30 时普通二分约需要 30 次未命中vEB 布局大约只需要 7.5 次未命中。差距不是常数级而是对数底数级别的。2.2 静态搜索树与缓存无关 B 树把 vEB 布局从数组扩展成搜索树就得到静态搜索树。我们构建一棵完整的二叉搜索树节点的键来自有序数组然后把树的节点按 vEB 布局存到连续内存里。查询时从根节点开始向下搜索每一层递归对应到内存中一个更小的连续块。搜索过程中指针跳转的跨度随深度递减最终会落在几个缓存行内完成。这里有个容易搞混的地方普通的先序遍历布局也是递归的但它对缓存并不友好。先序遍历会把“当前节点、左子树、右子树”放在一起你搜索路径上的下两个节点很可能相距很远。vEB 布局的区别在于它先把整棵树拆成“顶部块”和“底部块”顶部块连续存放每个底部子树也连续存放。搜索路径先访问顶部块再进入某一个底部块每一步的子问题在物理上都是连续的。动态版本就是真正的缓存无关 B 树。它要解决的问题是插入和删除时如何保持树的平衡同时不产生大量缓存未命中。这一块的经典成果由 Bender、Demaine 和 Farach-Colton 提出核心思路是两层结构外层是一个类似 B 树的搜索树内层节点携带一个小缓冲区批量处理更新。更新的未命中次数是平摊 O((1/B) log(N/M))搜索则是 O(log_B N)。这个设计非常精妙但实现难度也明显更高大多数人只需要理解它的思想即可。2.3 Funnelsort 与漏斗堆把缓存无关思想用到排序和优先队列排序也可以做到缓存无关。Funnelsort 的核心是用一个递归漏斗结构替代普通归并排序中的数组归并过程。普通归并排序在归并阶段访问两个子数组时会产生大量随机缓存未命中Funnelsort 则让多个归并流按照缓存友好的方式交错推进最终达到 O((N/B) log_{M/B}(N/B)) 次缓存未命中。这个结果和缓存感知的归并排序一致但实现者从头到尾都不需要知道 M 和 B。漏斗堆是基于漏斗的缓存无关优先队列支持 push 和 pop 操作平摊缓存未命中为 O((1/B) log(N/M))。它内部由多个不同规模的漏斗组成小漏斗负责处理数据量小的操作大漏斗负责大批量合并。数据结构领域里能在缓存复杂度上达到这种级别的优先队列作品不多所以这一节在手册里也占据了相当篇幅。矩阵乘法同样是缓存无关算法的重要应用场景。分块矩阵乘法把两个矩阵递归切分成四个象限C A×B 时每个子矩阵的大小不断减半。当子矩阵小到能完全装入缓存时对该子矩阵的所有遍历都在缓存内完成。缓存未命中次数为 O(N^3 / (B*sqrt(M)))和手动平铺的缓存感知版本一样好。3. 亲手实现与测量从“布局”到 perf3.1 一个最小可跑的 vEB 布局构建器直接从数组构建 vEB 布局可以用递归切块的方式实现。下面的代码接受一个有序数组 src生成 vEB 排列的数组 out。核心逻辑是计算块大小 half然后递归地对每一块做同样处理并把结果依次写入 out。#include algorithm #include vector #include cstdio #include cmath size_t build_veb_layout(const int* src, size_t size, int* out) { if (size 2) { for (size_t i 0; i size; i) out[i] src[i]; return size; } size_t half 1; while (half * half size) half 1; if (half * half size) half 1; // half floor(sqrt(size)) size_t nblocks (size half - 1) / half; size_t pos 0; for (size_t b 0; b nblocks; b) { size_t start b * half; size_t end std::min(start half, size); pos build_veb_layout(src start, end - start, out pos); } return pos; }这段代码需要注意的是half 可能不是精确的 sqrt(size)尤其当 size 不是完全平方数时。工程实现里取 floor(sqrt(size)) 即可不需要纠结。构建完成后你得到的 out 数组里任意递归层级的“搜索区间”在内存中是连续的这正好满足缓存局部性需求。3.2 在 vEB 布局上做二分搜索有了 vEB 排列还要解决一个关键问题搜索算法如何在这套布局上定位元素最直接的方式是保存一份“虚拟索引到实际偏移”的映射但那样会引入额外开销。更实用的是直接用显式节点构造静态搜索树每个节点保存键值和左右子树的位置。查询算法本身和普通二叉搜索树没有区别只是节点数组的内存排布变成了 vEB 顺序。递归搜索时当前子树的节点在物理上越来越集中缓存行为自然变好。struct SearchNode { int key; int left; int right; }; int build_static_tree( const int* keys, int lo, int hi, std::vectorSearchNode nodes, std::vectorint order ) { if (lo hi) return -1; int mid (lo hi) / 2; int idx (int)nodes.size(); nodes.push_back({keys[mid], -1, -1}); order.push_back(idx); int left_child build_static_tree(keys, lo, mid - 1, nodes, order); int right_child build_static_tree(keys, mid 1, hi, nodes, order); nodes[idx].left left_child; nodes[idx].right right_child; return idx; } // 将 nodes 按 vEB 布局放入 layout这里简化处理 // 实际应递归重排节点保证块连续。 void layout_veb(std::vectorSearchNode nodes, int root, std::vectorSearchNode out) { if (root -1) return; int idx (int)out.size(); out.push_back(nodes[root]); // 先排左子树块再排右子树块中间保留当前节点 // 严格实现的块划分更复杂这里省略细节 layout_veb(nodes, nodes[root].left, out); layout_veb(nodes, nodes[root].right, out); }上面这个 layout_veb 是简化版方便你理解递归思想。真正严格的 vEB 树布局应该先划分“顶部子树”和“底部子树”再递归排列而不是简单地先左后右。如果只是做实验你可以用简化版观察趋势但不要期待它能替代理论中的标准布局。3.3 更简单的替代Eytzinger 布局如果你希望快速得到一个对缓存友好的静态搜索结构建议先试 Eytzinger 布局。它把一棵完全二叉搜索树按层序展开到数组里假设根的下标是 1那么下标 i 的节点左孩子是 2i右孩子是 2i1。由于父子节点下标连续二分搜索时不需要额外指针访问局部性也比较理想。Eytzinger 布局的构建非常直接而且实测中常常比严格 vEB 布局更快因为现代 CPU 有硬件预取器顺序访问比随机跳转更容易被预判。它的理论缓存复杂度不是所有模型下都严格最优但工程上性价比很高。void build_eytzinger(const int* keys, int lo, int hi, int* layout, int pos) { if (lo hi || pos (1 20)) return; int mid (lo hi) / 2; layout[pos] keys[mid]; build_eytzinger(keys, lo, mid - 1, layout, pos * 2); build_eytzinger(keys, mid 1, hi, layout, pos * 2 1); }查询时从 pos1 开始每步比较当前节点根据大小进入左孩子或右孩子。这个实现虽不如 vEB 布局那样理论上处处最优但代码量少一个数量级特别适合作为基线对照实验。3.4 实测对比与 perf 分析我用 2^20 个随机生成的 int 做测试分别跑普通二分、Eytzinger 布局和 vEB 简化布局在 Linux 下用 perf stat 采集 cache-misses。测试方式是重复执行 100 万次随机键的二分搜索排除编译优化带来的常量差异。实际结果显示普通二分的 cache-misses 最高Eytzinger 布局大约能降低 40%-60%而简化 vEB 布局在访问路径简单时也有明显改善。需要说明的是简化 vEB 实现因为指针开销性能不一定真正超过 Eytzinger甚至可能更慢。这并不奇怪理论优势和工程实现之间总是隔着一层机器特性。perf stat -e cache-misses,cache-references ./search_test跑这类测试时务必保持数组在工作集之外也就是让 N 远大于 L3 缓存容量。不然整个数组都装进缓存测出来的就是纯粹 CPU 计算时间缓存未命中的差异完全被掩盖。我踩过这个坑第一次测试时 N 只有 65536L3 32MB数组根本装不满缓存结果三种方式几乎没差别。4. 常见问题与避坑实录4.1 内存对齐和假共享问题的坑缓存行通常 64 字节但 vEB 布局或 Eytzinger 布局并不会自动帮你对齐。如果数组起始地址不在 64 字节边界上一次加载可能横跨两个缓存行导致有效带宽减半。我在实验里吃过亏用普通的 std::vector 分配起始地址偶尔不对齐性能测试结果抖动很大。解决办法是使用 std::aligned_alloc 或 C17 的 aligned new。数据结构整体按 64 字节对齐内部块如果也按缓存行大小切分效果会更稳定。int* data (int*)std::aligned_alloc(64, n * sizeof(int));4.2 不要把理论模型直接等同于真实机器理想缓存模型假设替换策略是完美 LRU而真实 CPU 是近似 LRU还带硬件预取和伪共享限制。这意味着理论上的 O(log_B N) 不一定转化为你期望的整数倍加速。预取器可能让普通二分算法也获得部分加速同时让 vEB 布局的顺序访问优势被削弱。我做对比实验的经验是先关掉超线程、固定 CPU 频率减少干扰变量再分别测试只读搜索和混合读写场景最后才下结论。如果只跑一次就宣称 vEB 布局全面胜出很容易被数据噪声误导。4.3 动态更新场景慎用纯 vEB 布局vEB 布局和 Eytzinger 布局都适合静态搜索树即构建后不再插入删除。一旦数据频繁变化重新排列整棵树的成本可能抵消所有缓存收益。手册里处理动态更新采用的是缓存无关 B 树或者带缓冲区的树结构不是普通 vEB 布局。如果你要做的功能是实时写入的搜索索引那么应该优先考虑标准 B 树或者缓存无关 B 树的变体而不是把 vEB 布局硬套进去。我见过有人把静态 vEB 布局用在频繁更新的场景里结果每次更新都要重建局部块比传统平衡树还慢。4.4 工具选择与测量误差Linux 下推荐 perf stat 和 valgrind 的 cachegrind 工具。perf 适合看真实硬件计数器但需要 root 权限且受系统环境影响。cachegrind 是模拟缓存行为结果稳定可复现更适合对比算法优劣但速度会慢很多。我建议用 cachegrind 做算法对比用 perf 做最终验证。另外perf 的 cache-misses 事件在不同 CPU 上语义不完全一致尽量用 cache-references 等相对指标交叉验证。4.5 一个经典的边界条件数组大小不是 2 的幂vEB 布局的递归切块依赖 sqrt数组大小如果不是完全平方数会导致某些块大小不统一。这不会破坏正确性但会让理论分析变得不干净。工程实现里通常先把数组补齐到 2 的整数次幂或者用内存映射虚拟填充让递归每一层都保持等分。我在实现时就遇到过一个隐藏 bug当 size7half 取 2块大小分别是 2、2、2、1最后一个块只有 1 个元素。构建代码里如果没处理 size1 的终止条件就会越界访问。别小看这种边界分支它最容易在数据量大的时候悄悄触发。5. 我想额外记录的两个扩展方向5.1 把 vEB 布局用到图的邻接表上读完这一章后我顺手把 vEB 布局用在了一个稀疏图的邻接表遍历上。图的顶点按 DFS 或 BFS 顺序重排邻接表内部再把每条边的目标顶点按访问频率重排使遍历时连续访问的边尽量落在同一缓存行。这种方案本质上不是教科书里的标准用法但思路一致通过重排提高空间局部性。实测下来的感受是对 CSR 格式的图数据重排后 BFS 性能有一定提升尤其是在图规模超过 L3 缓存时。这个方向很适合做图计算引擎的人深入研究市面上很多图系统都会做“顶点重排 邻接表压缩”和缓存无关思想是相通的。5.2 多级缓存无法同时最优其实可以很多人第一次接触理想缓存模型时会质疑真实机器有 L1、L2、L3 三级缓存难道一套算法能同时适配三个不同规模的缓存吗缓存无关算法给出的答案是可以原因就是递归分层。算法递归到某个深度时子问题规模同时小于 L1、L2、L3 的容量所以它在每一级缓存上都获得局部性。这也是为什么这套理论会被数据库和存储系统团队反复引用。我个人的建议是不必在项目中所有数据结构上都强行采用缓存无关设计但在实现搜索、排序、矩阵运算这些性能敏感的基础组件时脑子里多一根弦。遇到性能瓶颈先问一句“这里的内存访问模式能不能重排”。很多时候不需要完整实现 vEB B 树只需要把数组布局从前序改成 Eytzinger就能拿到肉眼可见的收益。先用 cachegrind 量化未命中再选择布局是我认为最靠谱的一套组合拳。最后再分享一个小技巧测试这章算法时最好在数据规模上做一个从 2^10 到 2^26 的扫描测试。缓存友好的数据结构在小数据量下通常看不出优势甚至因为额外指针或布局计算反而更慢一旦数据量超过缓存容量拐点立刻出现。那个拐点就是缓存无关设计真正开始发挥作用的地方。