Static search trees: 40x faster than binary search · CuriousCodingTable of Contents<br>1 Introduction1.1 Problem statement<br>1.2 Motivation<br>1.3 Recommended reading<br>1.4 Binary search and Eytzinger layout<br>1.5 Hugepages<br>1.6 A note on benchmarking<br>1.7 Cache lines<br>1.8 S-trees and B-trees
2 Optimizing find2.1 Linear<br>2.2 Auto-vectorization<br>2.3 Trailing zeros<br>2.4 Popcount<br>2.5 Manual SIMD
3 Optimizing the search3.1 Batching<br>3.2 Prefetching<br>3.3 Pointer arithmetic3.3.1 Up-front splat<br>3.3.2 Byte-based pointers<br>3.3.3 The final version
3.4 Skip prefetch<br>3.5 Interleave
4 Optimizing the tree layout4.1 Left-tree<br>4.2 Memory layouts<br>4.3 Node size \(B=15\)4.3.1 Data structure size
4.4 Summary
5 Prefix partitioning5.1 Full layout<br>5.2 Compact subtrees<br>5.3 The best of both: compact first level<br>5.4 Overlapping trees<br>5.5 Human data<br>5.6 Prefix map<br>5.7 Summary
6 Multi-threaded comparison<br>7 Conclusion7.1 Future work7.1.1 Branchy search<br>7.1.2 Interpolation search<br>7.1.3 Packing data smaller<br>7.1.4 Returning indices in original data<br>7.1.5 Range queries<br>7.1.6 Sorting queries<br>7.1.7 Suffix array searching
In this post, we will implement a static search tree (S+ tree) for<br>high-throughput searching of sorted data, as introduced on Algorithmica.<br>We’ll mostly take the code presented there as a starting point, and optimize it<br>to its limits. For a large part, I’m simply taking the ‘future work’ ideas of that post<br>and implementing them. And then there will be a bunch of looking at assembly<br>code to shave off all the instructions we can.<br>Lastly, there will be one big addition to optimize throughput: batching.<br>All source code , including benchmarks and plotting code, is at github:RagnarGrootKoerkamp/static-search-tree.<br>Discuss on r/programming, hacker news, twitter, bsky, or youtube.<br>1 Introduction
Link to heading<br>1.1 Problem statement
Link to heading<br>Input. A sorted list of \(n\) 32bit unsigned integers vals: Vec.<br>Output. A data structure that supports queries \(q\), returning the smallest<br>element of vals that is at least \(q\), or u32::MAX if no such element exists.<br>Optionally, the index of this element may also be returned.<br>Metric. We optimize throughput. That is, the number of (independent) queries<br>that can be answered per second. The typical case is where we have a<br>sufficiently long queries: &[u32] as input, and return a corresponding answers: Vec.1<br>Note that we’ll usually report reciprocal throughput as ns/query (or just<br>ns), instead of queries/s. You can think of this as amortized (not average) time spent per query.<br>Benchmarking setup. For now, we will assume that both the input and queries<br>are simply uniform random sampled 31bit integers2.<br>Code.<br>In code, this can be modelled like this:
trait SearchIndex {<br>/// Two functions with default implementations in terms of each other.<br>fn query_one(&self, query: u32) -> u32 {<br>Self::query(&[query])[0]<br>fn query(&self, queries: &[u32]) -> Vecu32> {<br>queries.iter().map(|&q| Self::query_one(q)).collect()
Code Snippet 1:<br>Trait that our solution should implement.<br>1.2 Motivation
Link to heading<br>Aside from doing this project just for the fun of it, there is some higher<br>goal.<br>One of the big goals of bioinformatics is to make efficient datastructures to<br>index DNA, say a single human genome (3 billion basepairs/characters) or even a<br>bunch of them. One such datastructure is the suffix array (wikipedia), that<br>sorts the suffixes of the input string. Classically, one can then find the<br>locations where a string occurs by binary searching the suffix array.<br>This project is a first step towards speeding up the suffix array search.<br>Also note that we indeed assume that the input data is static, since usually<br>we use a fixed reference genome.<br>1.3 Recommended reading
Link to heading<br>The classical solution to this problem is binary search , which we will briefly<br>visit in the next section. A great paper on this and other search layouts is<br>“Array Layouts for Comparison-Based Searching” by Khuong and Morin (2017).<br>Algorithmica also has a case study based on that paper.<br>This post will focus on S+ trees , as introduced on Algorithmica in the<br>followup post, static B-trees. In the interest of my time, I will mostly assume<br>that you are familiar with that post.<br>I also recommend reading my work-in-progress introduction to CPU performance,<br>which contains some benchmarks pushing the CPU to its limits. We will use the<br>metrics obtained there as baseline to understand our optimization attempts.<br>Also helpful is the Intel Intrinsics Guide when looking into SIMD instructions.<br>Note that we’ll only be using AVX2 instructions here, as in, we’re assuming<br>intel. And we’re not assuming less available AVX512 instructions (in<br>particular, since my laptop doesn’t have them).<br>1.4 Binary search and Eytzinger layout
Link to heading<br>As a baseline, we will use the Rust standard library binary search implementation.
10<br>pub struct SortedVec {<br>vals: Vecu32>,
impl SortedVec {<br>pub fn...