Static Search Trees: Achieving 40x Speed Over Binary Search
Static search trees: 40x faster than binary search (2024)
I optimized a static search tree to achieve massive throughput gains for sorted data queries. By leveraging Eytzinger layouts, SIMD instructions, and aggressive prefetching, I pushed performance far beyond standard binary search. This work aims to accelerate bioinformatics tasks like DNA indexing, demonstrating how low-level CPU optimizations can yield dramatic real-world speedups.
At 1GB input, binary search needs around 1150ns per query, while the optimized Eytzinger layout is 6x faster at 200ns per query.
- kazinator
> The main benefit of the Eytzinger layout is that all values needed for the first steps of the binary search are close together, so they can be cached efficiently: we put the root at index 1 and the two children of the node at index i are at 2i and 2i + 1.
This is exactly what is done in good old binary heaps; though binary heaps do not maintain a balanced binary tree, only the property that key(parent) < key(left_child) and key(parent) < key(right_child). Binary heaps don't support efficient search for a particular key.
I don't remember ever reading a description of binary heaps which mentioned Eytzinger. This is because the layout for binary heaps was discovered without knowledge of Eytzinger. It may have been Knuth who discovered Eytzinger and made the connection?
It's quite obvious that this layout is good for caching. The first few layers of the tree will all fit into a single VM page, the nodes closest to the root into one cache line. Then the subsequent layers are similarly packed in order.
Let's say that k layers of the tree fit into page. If the search path from root to leaf is 3k, it should touch only three pages, right?
- stevefan1999
My first instinct is https://en.wikipedia.org/wiki/Van_Emde_Boas_tree
Not sure why
- TheRealPomax
> Input. A sorted list of 32bit unsigned integers vals: Vec<u32>.
Okay, but that's not even remotely like the kind of input that this tree was created for. From the next paragraph, this work is in part
> [...] to make efficient datastructures to index DNA [...]. One such datastructure is the suffix array, that sorts the suffixes of the input string. Classically, one can then find the locations where a string occurs by binary searching the suffix array.
So where is the analysis of how it performs for that use-case? Searching through "already sorted 32 bit numbers" has nothing to do with searching a 3 billion character string (that by definition cannot be internally sorted) for substrings.