GoKawiilIn this post, we will implement a static search tree (S+ tree) for high-throughput searching of sorted data, as introduced on Algorithmica. We’ll mostly take the code presented there as a starting point, and optimize it to its limits. For a large part, I’m simply taking the ‘future work’ ideas of that post and implementing them. And then there will be a bunch of looking at assembly code to shave off all the instructions we can. Lastly, there will be one big addition to optimize throughput: batching.
All source code, including benchmarks and plotting code, is at github:RagnarGrootKoerkamp/static-search-tree.
Discuss on r/programming, hacker news, twitter, bsky, or youtube.
1 Introduction Link to heading
1.1 Problem statement Link to heading
Input. A sorted list of \(n\) 32bit unsigned integers vals: Vec<u32> .
Output. A data structure that supports queries \(q\), returning the smallest element of vals that is at least \(q\), or u32::MAX if no such element exists. Optionally, the index of this element may also be returned.
Metric. We optimize throughput. That is, the number of (independent) queries that can be answered per second. The typical case is where we have a sufficiently long queries: &[u32] as input, and return a corresponding answers: Vec<u32> .
Note that we’ll usually report reciprocal throughput as ns/query (or just ns ), instead of queries/s . You can think of this as amortized (not average) time spent per query.
Benchmarking setup. For now, we will assume that both the input and queries are simply uniform random sampled 31bit integers.
... continue reading