Production Case Study: Cache-Friendly Eytzinger Binary Search Layout vs Standard Binary Search

Why std::lower_bound Is Slow on Modern Hardware

Given a static sorted table of $N = 2^{20}$ ($1{,}048{,}576$) 32-bit integers ($4\text{ MB}$), how fast is std::lower_bound? Textbook complexity says $20$ comparisons. Hardware reality says ~16 sequential DRAM/L3 memory stalls for three architectural reasons analyzed by Paul-Virak Khuong and Pat Morin (2017):

1. Zero Spatial Locality in the Top $\log_2 N - 4$ Levels: A $64$-byte CPU cache line holds sixteen 32-bit integers. Standard sorted order packs adjacent ranks ($A[i], A[i+1], \dots, A[i+15]$) into a cache line. That spatial locality is completely useless until the search interval $[lo, hi)$ shrinks to width $\le 16$ in the final $4$ iterations! The first $16$ probes each fetch a 64-byte line only to read a single 4-byte integer and discard the remaining 60 bytes.
2. Data-Dependent Memory Addresses Block Hardware Prefetching: The CPU cannot know whether the next probe is $mid - step$ or $mid + step$ until the load of $A[mid]$ completes, preventing memory-level parallelism (MLP).
3. Power-of-Two Cache-Set Aliasing: When $N = 2^{20}$, the top probes occur at byte offsets $N/2, N/4, 3N/4, N/8, \dots$, which are all large multiples of $2^{12} = 4096$ bytes. Because CPU L1/L2 caches index their cache sets using lower address bits (bits $6\dots 11$), all top binary-search probes map to the exact same cache set, evicting each other even when the working set is tiny!

The Eytzinger (BFS / 1-Indexed Heap) Array Layout

Named after 16th-century genealogist Michaël Eytzinger (and identical to the 1-indexed array layout of a binary heap), the Eytzinger layout stores the implicit binary search tree in Breadth-First Search (BFS) level order starting at index $k = 1$:

• The root (overall median) is at $B[1]$.
• For any node at index $k$, its left child (quartile $< B[k]$) is at $B[2k]$ and its right child (quartile $ge B[k]$) is at $B[2k + 1]$.

Production C++20 Implementation: 64-Byte Aligned Eytzinger Table with Prefetching

#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <span>
#include <vector>

template <std::totally_ordered T>
class EytzingerTable {
public:
    explicit EytzingerTable(std::span<const T> sorted_input)
        : n_(sorted_input.size()), tree_(n_ + 1) {
        std::size_t src_idx = 0;
        build_inorder(1, sorted_input, src_idx);
    }

    // Returns the Eytzinger index k in [1..n_] of the first element >= x,
    // or 0 if all elements are < x.
    std::size_t lower_bound_eytzinger_index(const T& x) const noexcept {
        std::size_t k = 1;
        constexpr std::size_t kPrefetchMultiplier = 16; // 4 levels ahead = 16 elements (64B for uint32_t)

        while (k <= n_) {
            if (k * kPrefetchMultiplier <= n_) {
                __builtin_prefetch(&tree_[k * kPrefetchMultiplier], 0, 1);
            }
            // Branchless step: left child (2k) if tree_[k] >= x, right child (2k+1) if tree_[k] < x
            k = (k << 1) + static_cast<std::size_t>(tree_[k] < x);
        }

        // Strip trailing 1-bits (right branches) + the 0-bit of the last left branch
        const int trailing_ones = std::countr_one(k);
        return k >> (trailing_ones + 1);
    }

    const T& node_value(std::size_t k) const noexcept { return tree_[k]; }

private:
    std::size_t n_;
    std::vector<T> tree_; // 1-indexed: tree_[1 .. n_]

    // Populates tree_ in BFS order via an in-order traversal of the implicit binary tree
    void build_inorder(std::size_t k, std::span<const T> sorted_in, std::size_t& src_idx) noexcept {
        if (k > n_) return;
        build_inorder(k << 1, sorted_in, src_idx);
        tree_[k] = sorted_in[src_idx++];
        build_inorder((k << 1) | 1, sorted_in, src_idx);
    }
};