Manticore 加速 KNN 搜索：2-pass HNSW、批量距离计算与 AVX-512 深度解读

背景

Manticore 的 KNN（K-Nearest Neighbors，K近邻）搜索功能基于开源的 hnswlib 实现。在过去，Manticore 团队在 KNN 优化上的工作主要集中在自定义距离函数（例如用于二进制量化的函数）以及添加预过滤（如 ACORN-1）和提前终止（early termination）等功能上。然而，核心的搜索循环逻辑并未发生根本性改变：hnswlib 依然以相同的方式遍历邻居、计算距离并维护候选集。

此次更新打破了这一局面，直接修改了 hnswlib 的核心搜索循环。这次优化旨在解决三个主要的性能瓶颈：低效的内存访问模式、冗余的数据加载以及间接函数调用的开销。通过重构邻居遍历方式、距离函数调用机制以及与 CPU 内存层级的交互，并结合列式库中新的 AVX-512 距离实现，Manticore 在不改变 API、无需重建索引、无需额外配置的前提下，显著提升了搜索速度。

核心内容

本次性能提升主要源于以下四项核心技术改进：

1. 编译时距离函数特化 (Compile-time distance function specialization)

问题： 在旧版本中，距离函数是一个存储在 HNSW 索引中的运行时函数指针，每次查询都会为每个候选点调用该指针。对于大搜索预算（large search budgets），这意味着每次查询会产生大量的间接调用。间接调用会阻止编译器将距离函数内联到搜索循环中，并引入分支预测开销。

解决方案： 新代码利用 C++ 模板在编译时解析距离函数。当搜索开始时，通过一个单一的 switch 语句根据距离度量标准和量化设置选择正确的模板特化。此后，整个内层循环（包括邻居遍历、距离计算和候选集更新）作为一个单一的单体函数运行，距离计算被完全内联。这使得编译器可以在距离计算边界之外优化寄存器分配、指令调度和循环展开。

2. 两遍邻居处理 (2-pass neighbor processing)

问题： 原始 HNSW 实现采用单遍处理邻居：检查是否已访问、获取向量数据、计算距离、更新候选集。这种模式下，内存预取提示（prefetch hints）在数据被需要之前几乎没有时间生效。

解决方案： 新实现将处理分为两遍：

• 第一遍： 遍历当前节点的所有邻居，跳过已访问的节点，将未访问的邻居收集到一个小的批次数组中。每添加一个邻居到批次时，就为其向量数据发出预取提示。
• 第二遍： 遍历批次并计算距离。当第二遍处理到每个向量时，第一遍发出的预取指令已有足够时间将数据带入缓存。

此外，第二遍遍历的是紧凑的连续候选 ID 数组，而非图结构本身。虽然底层向量加载仍然是分散的，但数据已提前预取。对于无过滤条件的查询（即没有 WHERE 子句），新代码还采用了一条快速路径，完全消除了针对每个候选者的过滤检查。

3. 批量距离计算 (Batched distance computation)

原理： 两遍结构不仅为预取争取了更多时间，还使得批量计算成为可能。一旦第二遍获得了紧凑的候选列表，它就可以成对（每次两个）而不是逐个地对候选者进行评分。

优势： 在计算两个候选者的距离时，查询向量在每个 SIMD 迭代中只加载一次，并复用于两次距离计算，从而消除了冗余加载。这减少了查询侧的重复加载，并允许评分循环成对处理候选者（对于奇数余数有回退机制）。目前提供了针对内积（inner product）、L2 距离及其二进制量化变体的 Batch-2 函数。

4. AVX-512 支持

技术细节： 新的 AVX-512 距离代码每迭代处理 16 个浮点数，而 AVX2 仅处理 8 个。

• 对于内积和 L2 距离，核心循环使用融合乘加指令（_mm512_fmadd_ps），将乘法和累加合并为单条指令。
• 对于二进制量化向量，AVX-512 的 VPOPCNTDQ 扩展加速了距离计算中使用的位计数操作。

自动适配： Manticore 现在提供三种库变体：基准构建版、AVX2 构建版和 AVX-512 构建版。启动时，Manticore 会自动检测 CPU 能力并加载相应的库，无需任何配置。

关键要点

• 性能提升显著： 在高 k 值下，KNN 吞吐量最高提升 29%；在并发负载下，提升超过 20%。
• 零配置升级： 无需更改 API，无需重建索引，无需修改配置。
• 算法与硬件协同： 优化结合了算法层面的改进（两遍处理、编译时特化）和硬件层面的加速（AVX-512、批量计算）。
• 测试环境基准：
  • 数据集： dbpedia-openai-1M-1536-angular（100 万向量，1536 维，余弦距离）。
  • 硬件： AMD Ryzen 7 9700X (Zen 5)，选择 Zen 5 是因为其原生支持 512 位数据路径，避免了旧款 Intel 处理器常见的 AVX-512 降频问题。
  • 量化： 使用 1-bit 二进制量化，禁用过采样（oversampling）和重评分（rescoring）以隔离优化效果。
• 单线程 vs 多线程表现：
  • 算法改进 alone (AVX2 vs 旧 AVX2)： 单线程下，随着 k 值从 10 增加到 1000，增益从 +3% 增至 +24%。多线程下，由于内存带宽竞争，增益缩小（4-8 线程时 +9-10%，16 线程时 +2-5%）。
  • SIMD 宽度优势 (AVX-512 vs 新 AVX2)： 在低 k 值（如 k=10）时，AVX-512 略慢于 AVX2（约 -2%）；但在 k≥30 时，AVX-512 在所有线程数下均领先。且线程数越多，AVX-512 的优势越明显（16 线程时领先 6.5%）。
  • 综合改进 (AVX-512 + 新代码 vs 旧代码)： 单线程下，k=1000 时提升达 +29%；多线程下，k=1000 时所有线程数均达到 +22-24% 的提升。

意义与影响

此次更新标志着 Manticore 在向量搜索性能优化上从“功能增强”转向“底层核心重构”。

1. 消除内存与计算瓶颈： 通过两遍处理和批量计算，有效缓解了向量搜索中常见的内存带宽瓶颈和缓存未命中问题。预取提示的引入和成对处理策略，使得 CPU 能够更充分地利用缓存层级。
2. 最大化现代 CPU 性能： 编译时特化和 AVX-512 的充分利用，使得软件栈能够紧密贴合现代 CPU 的指令集特性（如 Zen 5 的原生 512 位路径），避免了运行时开销和指令解码延迟。
3. 无缝体验： 对于用户而言，最大的意义在于“无感升级”。无需修改应用代码或重新索引数据，即可获得显著的性能红利，这对于生产环境中的大规模向量数据库部署具有极高的实用价值。
4. 并发场景下的稳健性： 即使在多线程竞争内存带宽的情况下，优化后的代码仍能保持可观的性能增益（20%+），证明了其架构改进在复杂并发负载下的有效性。