转载说明：本文译自 Gabriel Menezes 于 2025-01-13 发布的文章 Using the most unhinged AVX-512 instruction to make the fastest phrase search algo。本站版本保留原文完整正文，规范化了 Markdown 结构，并将源站图片导入本地资源。用最离谱的 AVX-512 指令做出最快的短语搜索算法开始之前先说几句对于不想读完整篇 / 没那么在意细节的人，结果 先放这里。我希望你看完结果后会愿意继续读下去。TL;DR： 我用 AVX-512 写了一个快得离谱的短语搜索算法，性能最高做到 Meilisearch 的 1600 倍。源码在这里，对应的 crate 在这里。这篇博客的内容受到 Doug Turnbull 关于 Roaringish 系列博客里那个绝妙点子的启发。本文会把这些想法一路推到极致，从聪明的算法一直讲到赤裸裸的性能优化。我强烈建议先去读一遍 Roaringish 原文；不过如果你不想读，后面我也会回顾它是怎么工作的。这个项目前后做了将近 7 个月，代码写了又推翻、推翻又重写，成千上万行，所以如果我听起来有点疯，请多包涵。写这篇文章的时候，仓库里大约有 2.7k LOC，但我累计提交过大概 17k LOC（.lock 文件可以扣掉几千行）（等文章发出来时这个数字大概还会继续增加），也就是说，这个项目差不多被我重写了快 6 次。 一开始我并没打算写博客，但我在这件事上投入了太多时间，而且最后的结果确实很酷，我觉得值得写一篇。我最早写过一个版本，但不喜欢它的发展方向，于是干脆改了路子，这才有了现在这篇。我的计划是展示项目当前的状态，并尽量回忆和解释为什么事情会变成今天这样。期间做了大量 benchmark 和微调，所以几乎不可能把每个细节都记得一清二楚。有些地方我会回到更早的时候，解释某个优化为什么被选中；也有些地方我可能只会解释它是怎么工作的。这篇会很长，先去拿点水 / 茶 / 咖啡吧。再说一次，你接下来看到的每一段代码我都重写过很多次，我不是一拍脑袋就直接得到这个解法的。文中会出现很多 unsafe，别害怕。本文不会展开讲：多线程。因为这种工作负载天然就能按分片做并行化，做起来其实不难，而且扩展性基本接近线性；如果你只是想知道它在 N 个线程上会怎么样，拿最终数字除以 N 就差不多了。代码之外那些“让它更快”的东西，比如开启 Huge Pages。重点会放在搜索阶段，因此索引阶段不会成为主角，只在必要时带到。Benchmark 方法：我们优化的是纯延迟，越低越好。我随机挑了一批查询（每个查询的瓶颈画像都不同），观察每次改动对性能的影响。每个查询先跑 20 次给 CPU 热身，然后再用同一个查询额外跑 1000 次，记录整体耗时以及每个关键步骤的耗时，于是就能算出每次迭代的时间。如果有人要说这不是好 benchmark、我应该上 criterion 搭配统计分析之类的……我只能说，我这两套系统（后面会提）都相当可复现，单次迭代的波动大概能控制在 10 微秒以内。我跑代码的那个核心在我的 isolcpus 列表里（物理核和对应的超线程核都隔离出来了），每次都用 taskset 绑定；采样期间系统里没有别的任务在跑。所以在 CPU 热起来以后，每次迭代的时间都非常稳定，这也是为什么我认为这样的 benchmark 已经足够。使用的数据集和 Doug 一样，是 MS MARCO，包含 320 万篇文档，总数据量大约 22GB。它由链接、问题和长答案组成，这里我只索引答案部分（所以实际索引的是 20/22GB 数据）（Doug 原文只用了 100 万篇文档，而我这里把它全吃进来了）。文章接近结尾时，我会给出一些和 Meilisearch 的 benchmark 与对比（它是一个面向生产的搜索引擎，以性能不错著称）。我做全部 benchmark 的两套机器配置：笔记本（大部分开发都在这台上做）：i5-1135G7 - 16GB台式机（最终结果跑在这台上）：9700x - 64GB（先剧透一下）文中会放很多源码，给真正感兴趣的人看；不必要的部分我会折叠起来，如果你不在意可以直接跳过。还要特别感谢所有一路帮过我的人，尤其是 Gamozo 的 Discord 里那些特别友善的人。过去这一年里，他们不得不看着我为了各种 intersection 算法越来越疯。我为什么要做这件事？ 因为我喜欢，而且我就想把一些人拉进这个坑里。我们到底在做什么？为什么这事值得关心？ 你应该见过这样的场景：去你最喜欢的搜索引擎里，用双引号搜索一段书里的句子 / 一段文章原文 / 某个非常具体的表达。这就叫短语搜索（有时也叫精确搜索）。你是在告诉搜索引擎：我想…