目录 1 引言 1.1 问题陈述 1.2 动机 1.3 推荐阅读 1.4 二分搜索与 Eytzinger 布局 1.5 大页 1.6 基准测试说明 1.7 缓存行 1.8 S树与 B树 2 优化查找 2.1 线性 2.2 自动向量化 2.3 尾零 2.4 位计数 2.5 手动 SIMD 3 优化搜索 3.1 批处理 3.2 预取 3.3 指针运算 3.3.1 预先展开 3.3.2 基于字节的指针 3.3.3 最终版本 3.4 跳过预取 3.5 交错 4 优化树布局 4.1 左树 4.2 内存布局 4.3 节点大小 (B=15) 4.3.1 数据结构大小 4.4 摘要 5 前缀分区 5.1 完整布局 5.2 紧凑子树 5.3 两者的最佳组合：紧凑的第一层 5.4 重叠树 5.5 人类数据 5.6 前缀映射 5.7 摘要 6 多线程比较 7 结论 7.1 未来工作 7.1.1 分支搜索 7.1.2 插值搜索 7.1.3 更小的数据打包 7.1.4 返回原始数据中的索引 7.1.5 范围查询 7.1.6 排序查询 7.1.7 后缀数组搜索 在这篇文章中，我们将实现一个静态搜索树（S+树），用于高吞吐量的排序数据搜索，如 Algorithmica 上所介绍的。我们将主要以那里提供的代码为起点，并将其优化到极限。在很大程度上，我只是将该帖子的“未来工作”中的想法实现出来。然后，我们将会大量查看汇编代码，以尽可能去掉所有指令。最后，还会增加一个重大的补充来优化吞吐量：批处理。所有源代码，包括基准测试和绘图代码，均在 github:RagnarGrootKoerkamp/static-search-tree 中。请在 r/programming、hacker news、twitter、bsky 或 youtube 上讨论。 1 引言 链接到标题 1.1 问题陈述 链接到标题 输入：一个排序列表 n 个 32 位无符号整数 vals: Vec<u32>。 输出：一个支持查询的结构 q，返回 vals 中大于等于 q 的最小元素，若不存在则返回 u32::MAX。可选地，也可以返回该元素的索引。 指标：我们优化吞吐量，即每秒可以回答的（独立）查询的数量。典型情况下，我们的输入是足够长的查询： &[u32]，并返回相应的答案：Vec<u32>。注意，我们通常报告的倒数吞吐量是 ns/query（或仅 ns），而不是 queries/s。你可以将其视为每个查询的摊销（而非平均）时间。 基准测试设置。目前，我们假设输入和查询随机均匀地采样为 31 位整型。代码。在代码中，可以这样建模： 1 2 3 4 5 6 7 8 9 特征 SearchIndex { /// 两个相互之间具有默认实现的函数。 fn query_one (& self, query : u32) -> u32 { Self::query(&[query])[0] } fn query (& self, queries : &[u32]) -> Vec<u32> { queries.iter().map(|&q| Self::query_one(q)).collect() } } 代码片段 1：我们解决方案应实现的特征。 1.2 动机 链接到标题 除了仅仅为了好玩而做这个项目之外，还有一个更高的目标。生物信息学的一个重要目标是创建高效的数据结构来索引 DNA，比如一个人类基因组（30 亿个碱基对/字符）或甚至多个基因组。其中一种数据结构是后缀数组（维基百科），它对输入字符串的后缀进行排序。经典方法中，可以通过对后缀数组进行二分搜索来找到字符串出现的位置。这个项目是加速后缀数组搜索的第一步。同时，请注意我们确实假设输入数据是静态的，因为我们通常使用固定的参考基因组。 1.3 推荐阅读 链接到标题 解决此问题的经典方法是二分搜索，我们将在下一节中简要探讨。关于这种搜索布局的优秀论文是 Khuong 和 Morin（2017 年）的《基于比较的搜索的数组布局》。Algorithmica 还基于该论文进行了一项案例研究。本文将重点介绍 S+ 树，正如 Algorithmica 后续文章中介绍的静态 B 树。为了节省时间，我将假设你熟悉该文章。我还建议阅读我正在进行的 CPU 性能介绍，其中包含一些将 CPU 性能推向极限的基准测试。我们将使用那里获得的指标作为理解我们优化尝试的基线。此外，在查看 SIMD 指令时，英特尔函数指南也很有帮助。请注意，我们将仅在这里使用 AVX2 指令，即假设是英特尔的。我们也不假设有可用的 AVX512 指令（尤其是因为我的笔记本电脑没有这些）。 1.4 二分搜索与 Eytzinger 布局 链接到标题 作为基线，我们将使用 Rust 标准库的二分搜索实现。 1 2 3 4 5 6 7 8 9 10 pub struct SortedVec { vals: Vec<u32>, } impl SortedVec { pub fn binary_search_std(&self,