Eytzinger binary search

Deep dive

How it works

In: sorted array of n keys (build), then a query key · Out: lower-bound position of the query · State: the array in BFS order, index 0 unused · Cost: ⌈log2(n + 1)⌉ comparisons, 81 ns per lookup at 2^26 u32 keys (table below)

1. Build: in-order traversal of the implicit tree (index 1, children 2k, 2k+1) assigns sorted values in order. Index 0 is unused.
2. Search for lower bound of x: k = 1; while k ≤ n: k = 2k + (a[k] < x). Each step appends one bit (0 = went left, 1 = went right) to k.
3. Recover the answer: the lower bound is the last node where we went left. Strip the trailing 1-bits and that final 0: k >> (trailing_ones(k) + 1). Result 0 means every element is < x.
4. Prefetch: node k has 16 descendants 4 levels down, at indices 16k..16k+15, which are 64 bytes of u32 (one cache line). Prefetch a[16k] at every step; by the time the search gets 4 levels deeper, its line is usually already in L1, so up to 4 misses are in flight.

sorted:     1 2 3 4 5 6 7
eytzinger:  _ 4 2 6 1 3 5 7      (index 0 unused)
                 4
              2     6
             1 3   5 7
lower_bound(5): k=1 (4<5, right) -> 3 (6>=5, left) -> 6 (5>=5, left) -> 12 > n, stop
                12 = 0b1100: trailing_ones = 0, so k >> 1 = 6, a[6] = 5

Code

pub struct Eytzinger { a: Vec<u32> } // a[0] unused; children of k are 2k and 2k+1

impl Eytzinger {
    pub fn new(sorted: &[u32]) -> Self {
        fn fill(k: usize, src: &[u32], i: &mut usize, a: &mut [u32]) {
            if k < a.len() {
                fill(2 * k, src, i, a);
                a[k] = src[*i];
                *i += 1;
                fill(2 * k + 1, src, i, a);
            }
        }
        let mut a = vec![0; sorted.len() + 1];
        fill(1, sorted, &mut 0, &mut a);
        Eytzinger { a }
    }

    /// Index into the layout of the first element >= x, or 0 if all elements are < x.
    #[inline]
    pub fn lower_bound(&self, x: u32) -> usize {
        let a = &self.a;
        let mut k = 1;
        while k < a.len() {
            prefetch(&a[(16 * k).min(a.len() - 1)]); // 4 levels ahead; clamped to stay in bounds
            k = 2 * k + (a[k] < x) as usize; // compiles to setcc/csel, no branch
        }
        k >> (k.trailing_ones() + 1) // undo the right turns after the last left turn
    }

    pub fn value(&self, k: usize) -> Option<u32> { (k != 0).then(|| self.a[k]) }
}

#[inline(always)]
fn prefetch<T>(p: &T) {
    #[cfg(target_arch = "x86_64")]
    unsafe {
        use std::arch::x86_64::{_mm_prefetch, _MM_HINT_T0};
        _mm_prefetch::<_MM_HINT_T0>(p as *const T as *const i8);
    }
    #[cfg(target_arch = "aarch64")]
    unsafe {
        std::arch::asm!("prfm pldl1keep, [{0}]", in(reg) p as *const T, options(nostack, readonly, preserves_flags));
    }
}

/// Branch-free binary search on the plain sorted layout (Khuong and Morin), for comparison.
pub fn branchless_lower_bound(a: &[u32], x: u32) -> usize {
    if a.is_empty() { return 0; }
    let (mut base, mut n) = (0, a.len());
    while n > 1 {
        let half = n / 2;
        if a[base + half] < x { base += half; } // cmov
        n -= half;
    }
    base + (a[base] < x) as usize
}

Complexity and constants

• Comparisons: ⌈log2(n + 1)⌉, identical to binary search.
• Cache lines touched: the top ~4 levels (15 nodes) share one or two lines that stay hot across queries; below that roughly one new line per level, but prefetched 4 levels early so up to 4 misses overlap.
• Measured (this entry's code, Rust, one Apple M-series core, 2 M random queries, ns/query):

• Memory: n + 1 elements, no pointers. Prefetching costs extra memory bandwidth (it fetches lines on both paths), irrelevant unless many threads saturate DRAM.

Efficiency

• Cost: ⌈log2(n + 1)⌉ comparisons, same as binary search; the cost is memory latency. Measured with this entry's code on one Apple M-series core (2 M random queries): at 2^26 u32 keys partition_point 196 ns, Eytzinger + prefetch 81 ns; at 2^16 keys 11 ns vs 14 ns. Memory: 4 bytes per u32 key plus one unused slot. Bound: memory latency (cache-miss chain), then DRAM bandwidth under many threads.
• Levers:
  • prefetch 4 levels ahead (a[16k]) — 196 → 81 ns at 2^26, but 30-50 % slower in cache (measured above) — arrays well beyond L2
  • 64-byte alignment of the array — one line holds all 16 descendants (order of) — always with prefetch
  • batched queries (8-16 interleaved) — overlaps misses across searches (Algorithmica) — many independent lookups
  • 2 MB huge pages — fewer TLB misses (order of) — arrays beyond the TLB reach
  • wide static B-tree / S+ tree nodes (FAST, Kim et al. 2010) — fewer levels, SIMD compare per node — largest static sets
• Naive → standard → state of the art:
  • partition_point on a sorted array · 196 ns at 2^26 keys (measured above)
  • Eytzinger layout with prefetch · 81 ns at 2^26 keys (measured above)
  • S+ tree with SIMD nodes and batching · faster again, see Algorithmica and Khuong & Morin 2017

Implementation notes

• Align the array to 64 bytes (#[repr(align(64))] wrapper or an aligned allocation, with the root at a known offset) so a[16k..16k+16] is exactly one cache line; otherwise each prefetch covers only part of the 16 descendants.
• Prefetch distance: 16 for u32 keys (4 levels), 8 for u64 (3 levels). Deeper prefetch (2 lines) helps on high-latency memory at bandwidth cost.
• Map results back to sorted ranks with a parallel array of original indices, or store (key, value) pairs in Eytzinger order.
• Batch queries: interleave 8-16 independent searches (software pipelining) for another large gain; each search's misses overlap with others'.
• Huge pages (2 MB) remove TLB misses, which dominate once the array exceeds the TLB reach (a few MB with 4 KB pages).
• S+ tree / static B-tree (16 keys per node, SIMD compare per node) is faster still for large n: fewer levels, one line per level.

Pitfalls

• Unclamped prefetch addresses far beyond the array (16k grows past n) can hit unmapped pages and trigger page walks: in our test, 2^10 keys went from 7 to 72 ns per query. Clamp or pad the array.
• Forgetting index 0 is unused (off-by-one in build or result).
• Rebuilding for every update: O(n); fine for static or batch-updated data only.
• Testing only in cache: the benefit appears beyond L2; benchmark at realistic sizes with random queries.
• Duplicates: lower_bound semantics hold, but the returned index is in layout order, not rank order.

Variants and alternatives

In production

Mostly in custom static indexes and lookup tables rather than named products. Rust crates eytzinger and ordsearch (Jon Gjengset, with prefetching) implement the layout; Khuong & Morin (2017) benchmark it against other array layouts across CPU generations. Wide static B-tree layouts in the FAST and S+ tree style are the usual choice in database and search-engine read-only indexes.

Implementations

Sources

• P.-V. Khuong, P. Morin, Array Layouts for Comparison-Based Searching, ACM Journal of Experimental Algorithmics, 2017. paper
• C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, P. Dubey, FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs, SIGMOD, 2010. paper
• S. Slotin, Algorithms for Modern Hardware (en.algorithmica.org/hpc), chapters on binary search and static B-trees. binary search · S+ tree