这是一篇关于优化静态搜索树（S+树）用于高效搜索排序数据的论文总结：

• 引言：介绍项目目标是实现用于高吞吐量搜索排序数据的静态搜索树，以加速后缀数组搜索，代码和基准测试在github:RagnarGrootKoerkamp/suffix-array-searching，相关讨论在多个平台。

• 优化find函数：

  • 线性查找效率低，改进为计数小于查询值的数量，可自动向量化为SIMD指令，速度提升两倍多。
  • 手动实现SIMD，通过直接处理16位比较结果的位掩码，避免不必要的指令，进一步提升性能。

• 优化搜索：

  • 批处理（batching）：一次处理多个查询，利用CPU并行处理能力，显著提高性能，饱和时批大小为128。
  • 预取（prefetching）：在处理节点后预取下一个节点，在数据超出L2缓存时效果显著。
  • 指针算术优化：提前展开splat操作、使用字节指针替代数组索引、手动合并除法和乘法等操作，减少指令数量，提高性能。
  • 交错（interleave）：交错处理不同批次的查询，平均不同层级的工作负载，提高总吞吐量，但代码较复杂。

• 优化树布局：

  • 左树（left-tree）：内部节点存储左子树的最大值，在搜索中间值时更高效，可降低运行时间。
  • 内存布局：尝试反向存储层和存储完整数组，虽未提高性能但提供了其他思路。
  • 节点大小(B = 15)：存储15个值的节点，降低乘法复杂度，但在不同数据规模下表现不同。

• 前缀分区（prefix partitioning）：

  • 全布局（full layout）：按高位分区构建独立搜索树，减少搜索层数，但空间开销较大。
  • 紧凑子树（compact subtrees）：连接压缩的子树，减少内存使用，但查询稍慢。
  • 紧凑第一层（compact first level）：结合前两种方法，减少空间开销，查询速度与全布局相当。
  • 重叠树（overlapping trees）：共享相邻树的存储，减少内存使用，查询速度与紧凑第一层相当。
  • 前缀映射（prefix map）：存储指向每个分区的第一个子树的索引，处理不平衡分区大小，但查询稍慢。
• 多线程比较：使用6线程时，运行时间从27ns降至7ns，表明已受总RAM吞吐量限制。
• 结论：通过批处理、预取、交错等优化，从二进制搜索的1150ns/query提升至优化后的S树的27ns/query，超过40倍的速度提升。分区方法在倾斜数据上效果不佳，未来可探索分支搜索、插值搜索、更紧凑的数据存储等方法。

总体而言，该研究通过多种优化技术提高了静态搜索树的性能，为高效搜索排序数据提供了有效的解决方案。