Static Search Trees 40x Faster Than Binary Search – Deep Dive and Benchmarks

TL;DR

Static search trees (S+ trees) answer lower‑bound queries on a sorted Vec<u32> 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 a combination of cache‑aware node layout, hand‑written SIMD find functions, large‑batch processing, explicit prefetching, pointer‑arithmetic tricks, and interleaving of query pipelines.

---

1. Problem and Baseline

• Task – Given a sorted list of 32‑bit unsigned integers, build a static index that returns the smallest element ≥ a query (or u32::MAX if none). The metric is throughput (queries / second) measured on a fixed‑frequency i7‑10750H laptop.
• Baseline – Rust’s binary_search (branchy) and an Eytzinger layout (heap‑style binary tree stored in an array). The Eytzinger layout prefetches future nodes and is ~4× faster than plain binary search when the data exceeds L2 cache, but still limited by one value per 64‑byte cache line.

"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)

2. From Linear Scan to SIMD‑Optimized find

The core of an S‑tree node is a sorted array of 16 u32 values (one cache line). The find routine must return the first index where value ≥ query.

Implementation	Technique	Throughput (ns/query) vs. Eytzinger
find_linear	Simple loop with early return	~2× slower than Eytzinger
find_linear_count	Count values < query (branchless) – auto‑vectorized by LLVM	2× faster than linear, now beats Eytzinger
find_ctz	Portable SIMD (simd_le) → trailing‑zero count	Slightly faster than count version
find_popcnt (hand‑written AVX2)	Manual _mm256_packs_epi32 + movemask + popcnt	115 ns/query on 1 GB input (≈2.5× faster than auto‑vectorized)

The hand‑written version reduces the instruction count from ~12 to 5 per node scan, shaving a few nanoseconds per level.

3. Batching Queries

Processing many queries simultaneously lets the CPU keep 10–12 in‑flight memory requests. The batch routine iterates over the tree layers once per batch, updating a per‑query state k[i].

• Batch size 1 ≈ single‑query throughput (115 ns).
• Batch size 8–16 drops to 45 ns/query (≈2.5× speedup).
• Batch size 128 gives the best steady‑state throughput (≈30 ns) because it saturates the CPU’s 12 line‑fill buffers.

"Going from batch size 1 to 2 does not double the performance… the CPU’s out‑of‑order execution was already deep enough to effectively execute (almost) 2 queries in parallel anyway." – author

4. Prefetching

After determining the child index for a query, the code issues a prefetch_index for the next node. Prefetching yields:

• No benefit when the tree fits in L1 (prefetch is a no‑op).
• Noticeable flattening of the latency curve once the data exceeds L2.
• 30 ns/query on a 1 GB dataset (≈33 % improvement over pure batching).

5. Pointer‑Arithmetic Optimizations

Two low‑level tricks further trim the inner loop:

1. Hoist SIMD splat – pre‑compute Simd::splat(q) for each query.
2. Byte‑based pointers – store node pointers as byte offsets and multiply the path index by 64 once, eliminating repeated shl $6 shifts.

These changes cut the per‑iteration instruction count from 17 to 15 and shave the throughput from 30 ns to 28 ns/query.

6. Interleaving All Layers

The final bottleneck is the alternating CPU‑bound (first few levels) and memory‑bound (deep levels) phases. By interleaving the processing of multiple batches—executing layer 0 of batch A, then layer 0 of batch B, … up to the deepest layer—the pipeline stays fully occupied.

• Result: 24 ns/query on a 1 GB dataset (≈1.2× faster than the best non‑interleaved version).
• Code size grows (multiple specialized generic functions) but the performance gain is consistent.

7. Tree Layout Variants

7.1 Left‑Max vs. Right‑Min Nodes

Switching from the classic right‑min (store minimum of right subtree) to a left‑max layout reduces the number of cache‑line hops for values that sit between subtrees. Throughput improves from 24 ns to 22 ns/query.

7.2 Node Size (15 vs. 16 values)

Using 15 values per node (branching factor 16) simplifies the index arithmetic (x = x << 4). It yields a modest speedup for L3‑fit datasets but doubles the memory overhead from 6.25 % to 13.3 %. For RAM‑bound workloads the extra overhead erases the benefit.

7.3 Memory Layouts (packed, reversed, full)

Experiments with reversed order and a full array (no offsets) showed no measurable speedup, so the packed layout remains the default.

8. Prefix Partitioning (Skipping Initial Levels)

The author explored partitioning the key space by high‑order bits, building independent S‑trees per prefix.

• Simple partition (full layout per part) reduces the tree height but incurs large space overhead (up to 50 % for skewed human‑genome k‑mer data).
• Compact subtrees (packed per‑part) lower memory use but add per‑query part‑offset bookkeeping, slightly hurting speed.
• First‑level compression (store only the first level compactly) recovers most of the space savings while keeping query speed comparable to the unpartitioned layout.
• Overlapping trees share storage between adjacent parts, further reducing memory at negligible speed cost.
• Prefix map (a lookup table mapping high‑order bits to the start of the appropriate subtree) gives the best space‑time trade‑off: ~1/16 overhead and query speed within a few nanoseconds of the best non‑partitioned variant.

"Overall, it seems that partitioning does not provide when we already interleave queries." – author’s summary

9. Multi‑Threaded Scaling

Running the interleaved S‑tree on 6 threads reduces latency from 27 ns (single‑core) to 7 ns per query. The sub‑linear speedup indicates the system is now limited by total RAM bandwidth rather than CPU.

10. End‑to‑End Result

Method	Throughput (ns/query) on 4 GB input
Rust binary_search	1150
Eytzinger (prefetch)	~200
Optimized S‑tree (popcnt SIMD)	115
Batching (size = 128)	30
Prefetch + Pointer tricks	28
Interleaved layers	24
Left‑max node + interleaving	22
6‑thread parallelism	7

Overall speedup: ≈40× over the naïve binary search.

11. Future Directions (as discussed in the post)

• Branchy search – selectively handle large partitions with extra branches to reduce average depth.
• Interpolation search – replace the first few levels with a linear interpolation step, potentially cutting RAM accesses for random data.
• 16‑bit packing – store values in 16 bits after a 16‑bit prefix lookup, raising the branching factor to 33 and shaving another tree level.
• Returning original indices – straightforward for S+ trees; more work needed for compact partitions.
• Range queries – duplicate the query pipeline for lower and upper bounds; early‑layer reuse can keep overhead low.
• Sorted‑query batching – radix‑sort queries to maximise cache reuse; the cost/benefit trade‑off remains open.
• Suffix‑array integration – build an S‑tree on every 4th suffix (using the first 32 bits) to narrow the binary‑search window dramatically.

---

12. Community Feedback Highlights

• Eytzinger vs. binary heap – kazinator notes the layout is identical to a binary heap’s array representation, but heaps lack efficient key search.
• Van Emde Boas connection – stevefan1999 points out the similarity to Van Emde Boas trees for cache‑oblivious search.
• Plot clarity – petters asks why Figure 1 uses the same colour for both curves; the author acknowledges a plotting quirk.
• Real‑world relevance – TheRealPomax questions the applicability to suffix‑array searches on DNA; the author’s future‑work section addresses this by proposing a suffix‑array integration.

---

13. Takeaway

Static search trees, when meticulously tuned for modern CPUs, can turn a memory‑bound lower‑bound search into a high‑throughput, cache‑friendly operation. The combination of SIMD‑accelerated node scans, aggressive batching, prefetching, and interleaved execution yields a 40× improvement over classic binary search, making S+ trees a compelling building block for large‑scale indexing tasks such as suffix‑array queries in bioinformatics.