Static search trees: 40x faster than binary search (2024)
4 hours ago
- #performance-optimization
- #SIMD
- #static-search-tree
- 该帖子实现了一种优化的静态搜索树（S+树），用于对已排序的32位无符号整数进行高吞吐量搜索，重点关注以每秒查询数为衡量标准的吞吐量。
- 关键优化包括使用SIMD指令进行节点搜索、批处理查询以并行化内存访问、预取数据以减少延迟，以及通过指针算术简化操作。
- 探索了分支因子为16或17的S+树等树形结构，结合交错查询来平衡CPU和内存受限的工作负载，对于4GB数据，实现了从1150纳秒/查询到27纳秒/查询的超过40倍加速。
- 尝试了按高位进行前缀分区的方法，但增加了复杂性且速度提升有限，特别是在人类基因组k-mers等倾斜的真实数据上，使得该方法不如交错查询实用。
- 未来工作建议包括针对可变迭代次数的分支搜索、通过插值搜索减少RAM访问、将数据打包到16位、支持范围查询、对查询进行排序以实现缓存重用，以及应用于后缀数组搜索。