在处理已排序数组的查找问题时，二分查找几乎是所有工程师的第一选择。这种算法以对数时间 O (log n) 完成单次查询，在理论上已经相当高效。然而，来自加拿大麦克马斯特大学的计算机科学家 Daniel Lemire 在近期的工作中提出了一种令人耳目一新的改进思路 ——SIMD Quad 算法，能够在特定场景下将查询速度提升一倍以上。这一突破并非依赖硬件层面的激进向量化，而是将算法层面的四分插值搜索与 SIMD 并行检查巧妙融合，形成了一套完整的层次化查找策略。
二分查找的性能瓶颈分析
传统二分查找的核心机制是将搜索区间不断对折，每次比较仅检查中间位置的单个元素。对于长度为 n 的数组，最多需要 floor (log₂ n) + 1 次比较才能确定目标值是否存在。这种算法在计算复杂度上已经达到了理论最优，但实际执行时存在两个常被忽视的性能瓶颈：分支预测失败与内存访问效率。
现代超标量处理器拥有强大的指令级并行能力，但二分查找中的条件分支会导致指令流水线频繁停顿。当搜索路径随机分布时，分支预测器的准确率会显著下降，每次预测失败都意味着数十个时钟周期的惩罚。更重要的是，二分查找每次只访问一个数据元素，无法充分利用处理器的内存级并行特性 —— 现代 CPU 可以在等待上一次内存访问完成的同时发起下一次加载请求，而单一元素访问模式显然无法激发这种能力。
SIMD Quad 算法的核心设计
Daniel Lemire 提出的 SIMD Quad 算法针对上述两个瓶颈给出了优雅的解决方案。该算法专为固定宽度数据（如 16 位无符号整数）设计，特别适用于 Roaring Bitmap 等压缩数据格式中的成员查询场景。其核心思想包含两个层面：首先是四分插值搜索替代传统二分搜索，其次是利用 SIMD 指令并行检查目标块中的全部元素。
算法的第一步是将数组划分为固定大小的块，每块包含 16 个元素（选择 16 是因为这恰好对应 128 位 SIMD 寄存器的容量，可同时容纳 8 个 16 位整数）。在查询时，算法不再逐个比较中间元素，而是利用每个块的最后一个元素作为插值键，快速定位目标最可能所在的块。这种四分插值搜索在每一步将搜索范围划分为四等份，通过比较目标值与三个四分点元素的大小关系，可以一次性排除四分之三的候选块。
定位到具体块之后，算法切换到 SIMD 模式进行并行检查。以 x64 架构为例，使用 SSE2 指令集的 _mm_cmpeq_epi16 可以在单条指令内将目标值与块中的 16 个元素同时比较，生成一个 16 位掩码表示匹配位置。随后通过 _mm_movemask_epi8 提取掩码，非零结果即表示查找成功。这种向量化检查方式将原本需要最多 16 次比较的操作压缩为 2 至 3 条 SIMD 指令，极大地提升了吞吐量。
计算复杂度与常数因子的双重优化
从渐近复杂度角度看，四分插值搜索与二分查找同属对数级别，但由于每次迭代排除的比例更大，实际比较次数明显减少。对于长度为 n 的数组，二分查找需要约 log₂ n 次比较，而四分搜索仅需 log₄ n 次，理论上减少近一半的迭代轮数。这一优势在大规模数据集上尤为显著 —— 当数组规模达到 4096 个元素时，二分查找最多需要 12 次比较，而四分搜索仅需 6 次。
然而，真正带来质变的是常数因子的优化。SIMD Quad 算法通过两种方式降低了每轮迭代的开销：其一，四分搜索每次迭代处理 3 个比较操作（对应 3 个四分点），而非二分搜索的 1 个，但总迭代次数的减少使得整体比较次数反而下降；其二，SIMD 并行检查将目标块内的线性扫描转换为向量化操作，尽管增加了数据预取的开销，但相对于逐元素比较而言，SIMD 指令的吞吐量优势足以弥补这一成本。
性能实测数据与平台差异
Daniel Lemire 在其博客中公布了详尽的基准测试结果。测试环境包括 Intel Emerald Rapids 处理器（GCC 编译）和 Apple M4 芯片（LLVM 编译），数据集为 2 至 4096 个 16 位无符号整数的已排序数组。测试分为冷缓存（每次查询访问不同数组，模拟缓存未命中的最坏情况）和暖缓存（同一数组被连续查询 100 次，模拟缓存命中）两种模式。
在 Intel 平台上，SIMD Quad 算法相比标准二分查找在暖缓存模式下实现了超过两倍的性能提升，平均查询时间从约 8 纳秒降至 3.5 纳秒。冷缓存场景下的加速比稍低，但仍达到约 1.5 倍，原因在于内存带宽成为主要瓶颈后，SIMD 并行化带来的收益被部分稀释。有趣的是，四分搜索策略对 Intel 平台的冷缓存场景帮助尤为明显 —— 这表明四分搜索更好地激发了处理器的内存级并行能力，使得预取机制能够更高效地工作。
在 Apple M4 平台上，结果呈现出截然不同的模式：SIMD Quad 在冷缓存模式下加速超过两倍，而在暖缓存模式下的优势则相对有限。Lemire 解释称，Apple 芯片的专用内存控制器和更大的缓存结构使得暖缓存场景下两种算法的差异本来就很小，反而是冷缓存场景更能体现 SIMD 并行检查的价值。值得注意的是，无论在哪种平台和缓存状态下，SIMD Quad 的性能都始终优于传统二分查找，这证明了该算法的鲁棒性。
工程实现的关键参数与监控要点
将 SIMD Quad 算法投入生产环境需要关注几个关键实现细节。首先是块大小的选择 ——16 元素是一个经验最优值，过小的块会增加四分搜索的迭代次数，过大的块则会增加 SIMD 检查的未命中风险。对于不同宽度的数据元素，块大小应相应调整：32 位整数宜采用 8 元素块以匹配 256 位 AVX 寄存器，64 位整数则应使用 4 元素块。
其次是边界情况的处理。当数组元素总数不是 16 的倍数时，需要对尾部 remainder 元素进行线性扫描。实现时应确保 remainder 检查在 SIMD 块检查失败后才执行，避免不必要的计算开销。此外，当数组规模小于一个完整块时，应直接退化为线性搜索 —— 对于极小数据集，算法切换的开销可能超过其收益。
在监控层面，建议跟踪以下指标：查询延迟的 p50、p95、p99 分位数以评估尾部延迟；缓存命中率以判断算法是否运行在预期模式；SIMD 指令占比以确认向量化已生效。对于延迟敏感型应用，冷缓存场景下的性能表现往往更具参考价值，因为它更接近真实的首次查询场景。
与其他优化策略的协同可能
SIMD Quad 算法代表了一种算法层面的创新，但它完全可以与硬件层面的其他优化手段共存。例如，可以将四分搜索的分支逻辑改写为无分支形式，进一步消除分支预测失败的开销；或者在 SIMD 检查阶段引入更激进的预取策略，提前将下一个可能访问的块加载至缓存。此外，该算法的思想也可以推广到其他固定宽度数据场景，如 IPv4 地址查找、指纹匹配等。
从系统工程的角度看，选择哪种查找策略应当基于具体 workload 的特征：数据规模、元素宽度、访问模式、硬件平台。对于典型规模的已排序数组，二分查找仍然是一个安全且高效的默认选择；但当性能成为关键瓶颈，且数据特征符合 SIMD Quad 算法的适用条件时，这种四分插值与 SIMD 并行检查的组合拳值得考虑。
资料来源：Daniel Lemire, "You can beat the binary search", LinkedIn, 2026 年 4 月 27 日。