传统二分查找是计算机科学中最经典的算法之一，在有序数组中查找目标值的时间复杂度仅为 O (log n)。然而，现代处理器拥有强大的数据并行能力（SIMD 指令）和内存级并行性，传统二分查找逐个比较元素的模式未能充分利用这些硬件特性。Daniel Lemire 提出了一种名为 SIMD Quad 的算法，通过结合四路插值搜索与 SIMD 向量化比较，在 16 位无符号整数有序数组的成员查询场景中实现了显著的性能提升。本文深入分析该算法的核心策略、工程实现参数以及实测性能数据，为高性能查找场景提供可落地的优化参考。
传统二分查找的性能瓶颈
二分查找的核心逻辑是每轮将搜索区间折半，通过比较目标值与中点元素的大小关系来决定保留上半部分还是下半部分。这一算法在理论上是优雅的，但在现代处理器上存在几个关键瓶颈。首先是分支预测压力：每次比较都产生一个条件分支，在高频场景下分支预测失败会带来可观的延迟惩罚。其次是数据并行性的浪费：处理器每次只能比较一个元素，而现代 x64 和 ARM 处理器均支持单条指令并行比较多个数据 ——x64 的 SSE2/AVX 指令集可以同时比较 8 个或 16 个 16 位整数，ARM NEON 同样具备 8 路并行能力。最后是内存级并行性的局限：二分查找的访问模式是跳跃式的，每轮访问不同的内存区域，这种不可预测的访问模式会降低预取器的效率。
针对 Roaring Bitmap 格式中 16 位整数数组成员查询的需求，Lemire 意识到传统二分查找并未为现代硬件优化，这促使他探索硬件感知的算法设计。
SIMD Quad 核心策略：分层搜索与向量化并行
SIMD Quad 算法的核心思想是分层搜索：首先使用粗粒度的插值搜索定位目标元素所在的块，然后在块内使用 SIMD 指令并行比较所有元素。这种设计充分发挥了两个层面的并行性 —— 内存级并行性（四路插值搜索更好地利用处理器的并行加载能力）和数据并行性（SIMD 在块内并行比较）。
算法的第一步是将有序数组划分为固定大小的块。块大小选择为 16 个元素，这一数值基于以下考量：16 是 SIMD 寄存器宽度的整数倍（x64 的 128 位寄存器可容纳 8 个 16 位整数，两个寄存器即可覆盖 16 个元素；ARM NEON 的 128 位寄存器同样可容纳 8 个），同时 16 也是缓存行友好的大小，能够保证良好的空间局部性。
在块划分完成后，算法使用每个块的最后一个元素作为插值键。搜索过程采用四路插值而非传统的二路折半：每轮将当前搜索区间划分为四等分，通过比较目标值与三个分割点的键值来确定目标所在的大致区域。这种四路搜索方式每轮产生更多的比较操作，但能够更好地触发处理器的内存级并行性 —— 处理器可以同时发起多个非依赖的内存加载请求，从而隐藏内存延迟。在搜索区间缩小到足够小（小于等于块数量）后，算法加载目标块的全部 16 个元素到 SIMD 寄存器，使用向量化指令并行比较这 16 个元素与目标值。
工程实现参数与 intrinsics 代码
从工程实现的角度看，SIMD Quad 算法的关键参数包括块大小、SIMD 指令集选择以及分支消除策略。根据 Lemire 在代码中给出的实现，以下参数和实现细节值得关注。
块大小固定为 16，这一数值是经验最优值，既能保证 SIMD 指令的利用效率，又不会导致缓存污染。对于元素数量小于 16 的数组，直接使用朴素线性搜索即可，避免插值搜索的开销。搜索过程中当剩余块数量大于 3 时采用四路插值，每轮计算三个分割点的键值并更新搜索基址；当剩余块数量减少到 3 以下时切换为标准的二路折半，这种自适应策略能够在保持搜索效率的同时减少小规模场景下的指令数。
SIMD 比较部分的代码展示了跨平台的 intrinsics 使用模式。在 ARM NEON 平台上，使用 uint16x8_t 类型和 vceqq_u16 指令进行向量等值比较，通过 vorrq_u16 合并两个 8 元素向量的比较结果，最后用 vmaxvq_u16 检查是否有任何元素匹配。在 x64 平台上，使用 __m128i 类型和 _mm_cmpeq_epi16 指令进行比较，通过 _mm_or_si128 合并结果，用 _mm_movemask_epi8 检查匹配位。需要注意的是，x64 代码中使用 _mm_loadu_si128 而非对齐加载，这是因为目标块的位置是由搜索动态确定的，无法保证 16 字节对齐，但在大多数情况下性能损失微乎其微。
分支消除是另一个关键优化点。四路插值搜索中的比较操作使用条件表达式而非分支语句：c1 = (k1 < pos) 等操作产生掩码信息，用于后续的基址计算。这种分支 less 设计使得编译器能够更好地向量化代码，同时减少分支预测失败带来的性能惩罚。
性能实测数据与平台差异
Lemire 在两种不同平台上进行了基准测试：Intel Emerald Rapids 处理器（使用 GCC 编译）和 Apple M4 处理器（使用 Apple LLVM 编译）。测试场景分为冷缓存（每次查询搜索不同的数组，模拟缓存未命中）和热缓存（同一数组被连续查询 100 次，模拟缓存命中）。
在 Intel 平台上，SIMD Quad 算法相比传统二分查找在热缓存场景下实现了超过 2 倍的性能提升，冷缓存场景下的优势相对较小但仍然显著。这一现象符合预期：热缓存场景下，SIMD 并行比较带来的收益完全体现在计算阶段，而冷缓存场景下内存访问延迟仍然是主要瓶颈。在 Apple M4 平台上，结果呈现有趣的逆转：SIMD Quad 在冷缓存场景下优势更为明显（超过 2 倍），热缓存场景下的优势相对较小。Lemire 推测这与 Apple 芯片的架构特性有关 ——M4 的内存级并行性可能不如 Intel 服务器处理器，但 SIMD 单元的效率非常高。
关于四路插值搜索的贡献，Lemire 对比了仅使用 SIMD 优化但保留传统二路折半搜索的变体。结果表明，在 Apple 平台上四路与二路差异不大，但在 Intel 平台上对于大规模数组的冷缓存场景，四路搜索能够更好地利用内存级并行性，带来可观的额外收益。
落地应用的关键考量
将 SIMD Quad 算法应用于实际项目时，有几个关键因素需要考量。首先是数据类型的限制：当前实现针对 16 位无符号整数优化，对于其他数据类型（如 32 位整数、浮点数）需要调整 SIMD 指令和块大小参数。块大小 16 意味着 SIMD 寄存器恰好能容纳两个向量，但对于更大的数据类型，需要相应减小块大小或采用不同的向量组织方式。其次是数据分布的影响：插值搜索假设数据分布相对均匀，如果数据存在严重的倾斜或重复值模式，插值搜索的效率可能下降，此时可能需要回退到纯二分搜索或调整块划分策略。第三是查询模式的匹配度：该算法最适合的场景是同一有序数组上进行大量成员查询，如果查询次数较少或每次查询针对不同的数组，SIMD 初始化和数据加载的开销可能抵消并行带来的收益。
从监控系统建设的角度，生产环境部署时可以采集以下指标：查询延迟的分位数分布（特别是 P99）、缓存命中率、CPU 微架构事件（如分支预测失败次数、SIMD 指令吞吐量）。如果发现冷缓存场景下的延迟显著高于热缓存，说明内存带宽可能成为瓶颈，此时可以结合预取策略或调整块大小来优化。
结论
SIMD Quad 算法展示了硬件感知算法设计的强大威力：通过充分利用 SIMD 数据并行性和内存级并行性，在成员查询场景中实现了超越传统二分查找 2 倍以上的性能提升。核心工程参数可总结为：块大小 16、四路插值切换阈值 3、SIMD 向量宽度 8 元素（对于 16 位整数）、无条件分支消除策略。不同平台（Intel vs. Apple）的性能表现差异提醒我们，优化策略需要结合具体硬件特性进行调整，不能一概而论。随着 AVX-512 等更宽向量指令集的普及，更大粒度的向量化搜索有望带来更显著的性能提升，这仍然是值得探索的优化方向。
参考来源
- Daniel Lemire, "You can beat the binary search", LinkedIn, 2026 年 4 月 27 日（https://www.linkedin.com/pulse/you-can-beat-binary-search-daniel-lemire-igv1e）