Static Search Trees 40× Faster Than Binary Search – Deep Dive into Optimizations

Static Search Trees 40× Faster Than Binary Search – Deep Dive into Optimizations

TL;DR – Static search trees beat binary search by up to 40× in throughput

Static search trees (S+ trees) can answer lower‑bound queries on a sorted 32‑bit integer array up to 40× faster than the Rust standard library binary search, reaching 27 ns per query on a 4 GB dataset. The speedup comes from cache‑aware node layout, SIMD‑based find, aggressive batching, prefetching, pointer‑arithmetic tricks, and interleaving of query layers.

1. Problem and Baseline

Goal. Given a sorted Vec<u32> and a batch of queries, return the smallest element ≥ each query (or u32::MAX). The metric is throughput – queries per second – measured as nanoseconds per query.

Baseline. Rust’s binary_search on a plain array and the Eytzinger layout (a binary‑tree stored in breadth‑first order) were used as reference points. On a 1 GB input the Eytzinger layout is ~6× faster than binary search (≈200 ns/query vs 1150 ns/query) because it can prefetch four cache lines ahead.

2. SIMD‑Accelerated Node Search (find)

Linear scan is slow

A naïve linear scan over the 16 sorted values in a node takes ~240 ns/query on a 1 GB dataset, slower than the Eytzinger baseline.

Auto‑vectorization eliminates branches

Counting values < q instead of early‑returning enables the compiler to emit AVX2 SIMD compares, popcounts, and a popcnt instruction. This version is 2× faster than the linear scan and beats the Eytzinger layout.

"The auto‑vectorized version is over two times faster than the linear find, and now clearly beats Eytzinger layout!" – author’s comment.

Manual SIMD with popcnt

Hand‑written intrinsics replace the compiler‑generated popcnt‑plus‑tzcnt sequence with a single vpmovmskb followed by popcnt. The final find_popcnt function reduces the instruction count to 5 instructions per node search, yielding 115 ns/query for the S‑tree – a 2× speedup over the auto‑vectorized version.

3. Batching Queries

Processing many queries simultaneously keeps multiple memory requests in flight. With a batch size of 16, latency per query drops from 115 ns to 45 ns (≈2.5× faster). The CPU’s 12 line‑fill buffers limit further gains; larger batches give diminishing returns.

4. Prefetching

Explicit prefetch_index for the child node after each level reduces the L2‑to‑L3 miss penalty. Prefetching is neutral when the data fits in L1, modestly helpful for L2, and cuts the 45 ns/query down to 30 ns/query once the dataset exceeds L2 (≈1 GB).

5. Pointer‑Arithmetic Optimizations

  • Up‑front SIMD splat – moving the Simd::splat out of the inner loop saves a few cycles but does not change throughput.
  • Byte‑based pointers – storing node offsets in bytes and using byte_add removes the costly <<6 shift per access, shaving a few instructions and improving 1 GB throughput from 31 ns to 28 ns/query.
  • Merging /2 and *64 – the final find_splat64 multiplies the popcount result by 32 directly, eliminating an unnecessary and $‑64 mask.

6. Tree Layout Variations

Left‑max vs Right‑min nodes

Storing the maximum of the left subtree (left‑max) instead of the minimum of the right reduces one extra cache line fetch for many queries, improving interleaved throughput from 24 ns to 22 ns/query.

Node size (15 vs 16 values)

Using 15 values per node (branching factor 16) simplifies the index arithmetic (x << 4) and yields a small speed gain for L3‑fit data, but doubles the structural overhead from 6.25 % to 13.3 %.

Memory layout experiments

  • Packed (default) – layers stored back‑to‑back.
  • Reversed – layers stored in reverse order (as in the original Algorithmica paper).
  • Full array – a flat array with implicit offsets.

None of these layouts beat the default packed layout; the extra arithmetic cost outweighs any cache‑line alignment benefits.

7. Prefix Partitioning (Reducing Tree Height)

The input can be split by the top b bits, building independent S‑trees per prefix. This saves the first ⌈b/⌈log₂(B+1)⌉⌉ levels for each query.

  • Simple full layout – large memory overhead (up to 2×) and only modest speed gains for small inputs.
  • Compact subtrees – pads each subtree to the size of the largest, reducing overhead but adding per‑query part tracking, which slightly slows queries.
  • Compact first level – compresses only the root layer; space overhead matches the compact layout while query speed matches the full layout.
  • Overlapping trees – share storage between adjacent prefixes; memory usage drops dramatically, performance stays comparable to the compact‑first‑level variant.
  • Prefix map – a lookup table maps a prefix to the start offset of its subtree, achieving near‑minimal overhead (≈1/16) while keeping query time close to the unpartitioned tree.

Overall, partitioning does not outperform simple interleaved queries on random data, and on skewed human‑genome k‑mer data the extra index lookup erodes the benefits.

8. Multi‑Threaded Scaling

Running the optimized S‑tree on 6 cores reduces per‑query time from 27 ns (single‑thread) to 7 ns, a ~4× speedup limited by total RAM bandwidth. Slower single‑thread methods converge to the same throughput because the memory subsystem becomes the bottleneck.

9. Conclusions

  • Throughput improvement: 1150 ns → 27 ns per query (≈40×) on a 4 GB sorted array.
  • Key techniques: SIMD‑heavy find, large‑batch processing, prefetching, pointer‑arithmetic tricks, interleaved layer execution, and a left‑max node layout.
  • Space‑time trade‑offs: 15‑value nodes double overhead but give modest speed gains for cache‑fit data; partitioning reduces tree height but adds memory overhead and lookup cost.
  • Future directions: branchy search for skewed partitions, interpolation search to cut RAM accesses, 16‑bit packing to increase branching factor, range queries, and integration with suffix‑array search.

10. Notable Community Feedback

"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..." – kazinator (HN comment)

"My first instinct is https://en.wikipedia.org/wiki/Van_Emde_Boas_tree" – stevefan1999 (HN comment)

"Why does figure 1 use the same color and style for two different graphs?" – petters (HN comment)

11. References

  • Khuong, P‑V., & Morin, P. (2017). Array Layouts for Comparison‑Based Searching. ACM JEA, 22.
  • Abrar, M. H., & Medvedev, P. (2024). PLA‑Index: A K‑Mer Index Exploiting Rank Curve Linearity. WABI 2024.
  • Algorithmica blog posts on S‑trees and static B‑trees (https://en.algorithmica.org/hpc/data-structures/s-tree/).

Sources