Cache-Aware vs Cache-Oblivious Layouts (van Emde Boas Layout)

The Ideal-Cache Model $(M, B)$ & Recursive Divide-and-Conquer

The Cache-Oblivious (Ideal-Cache) Model analyzes algorithms on a two-level memory hierarchy with cache capacity $M$ words and cache-line block size $B$ words (assuming the tall-cache condition $M = \Omega(B^2)$ and optimal offline replacement, which LRU matches within a factor of 2). The algorithm knows neither $M$ nor $B$. How can an algorithm optimize for an unknown $B$? By recursing all the way down to $O(1)$ base cases! At some level of the recursion tree, the subproblem size natively drops below $M$ (fitting in cache) and below $B$ (fitting in a single cache line).

Consider two flagship applications of cache-oblivious design:

• 1. Static Binary Search Trees (van Emde Boas Layout): A standard pointer-based BST or even a breadth-first (BFS / Eytzinger) heap array incurs $\Theta(\log_2 N)$ cache misses per query once search depth exceeds cache capacity, because jumping from index $i$ to $2i$ leaps across distant cache lines at the bottom of the tree. The van Emde Boas (vEB) layout recursively cuts a tree of height $h$ at mid-height $h/2$ into one top subtree $T_0$ of height $h/2$ (size $\approx \sqrt{N}$) and $\approx \sqrt{N}$ bottom subtrees $T_1, \dots, T_k$ of height $h/2$, storing [T_0][T_1][T_2]...[T_k] contiguously in memory. At the recursion level where subtree size $\le B$, each small subtree of height $\approx \frac{1}{2} \log_2 B$ sits inside a single cache line! Thus a root-to-leaf search of $\log_2 N$ steps crosses only: $$Q(N) = \frac{\log_2 N}{\frac{1}{2} \log_2 B} = O(\log_B N) \text{ cache misses!}$$
• 2. Cache-Oblivious Matrix Multiplication & Transposition: Naive loop for i..for j: B[j][i] = A[i][j] scans $A$ row-wise (stride 1, $N^2/B$ misses) but writes $B$ column-wise (stride $N$, $N^2$ misses!). Recursively splitting the larger dimension in half ($A_{11}, A_{12}, A_{21}, A_{22}$) until submatrices fit in L1 cache reduces misses to the optimal $\Theta(1 + N^2 / B)$.

Visualizing the Recursive van Emde Boas Tree Slicing

Notice how cutting a height-$h$ tree horizontally at depth $h/2$ packs the top triangle $T_0$ into array indices $[0 .. \sqrt{N}-1]$, followed immediately by each bottom triangle $T_1, T_2, \dots$ contiguously.

Production Implementation: Cache-Oblivious Matrix Transposition & Prefetched Eytzinger Search

The C++20 code below implements both the cache-oblivious recursive matrix transpose and Khuong-Morin's branchless, prefetched Eytzinger array search.

// C++20: Cache-Oblivious Matrix Transpose + Branchless Eytzinger Search
#include <bit>
#include <cstddef>
#include <cstdint>

// 1. Cache-Oblivious Matrix Transpose: O(H*W) work, optimal O(1 + H*W / B) cache misses
// Works across L1, L2, L3, and TLB without knowing B or M!
void transposeOblivious(const float* __restrict src, float* __restrict dst,
                        size_t N, size_t r0, size_t r1, size_t c0, size_t c1) noexcept {
    const size_t H = r1 - r0;
    const size_t W = c1 - c0;
    if (H <= 16 && W <= 16) {
        for (size_t r = r0; r < r1; ++r) {
            for (size_t c = c0; c < c1; ++c) {
                dst[c * N + r] = src[r * N + c];
            }
        }
        return;
    }
    if (H >= W) {
        size_t rMid = r0 + H / 2;
        transposeOblivious(src, dst, N, r0, rMid, c0, c1);
        transposeOblivious(src, dst, N, rMid, r1, c0, c1);
    } else {
        size_t cMid = c0 + W / 2;
        transposeOblivious(src, dst, N, r0, r1, c0, cMid);
        transposeOblivious(src, dst, N, r0, r1, cMid, c1);
    }
}

// 2. Khuong & Morin (2017): Branchless Eytzinger (1-indexed BFS) Binary Search
// Prefetches 4 tree levels ahead (16 contiguous grandchildren = one 64B cache line!)
size_t eytzingerLowerBound(const int32_t* a, size_t n, int32_t target) noexcept {
    size_t k = 1;
    while (k <= n) {
        __builtin_prefetch(a + k * 16); // Prefetch entire 64B cache line 4 levels down!
        k = 2 * k + (a[k] < target);    // Branchless CMOV/ADC index descent
    }
    // Decode original answer index by stripping trailing 1-bits from path k
    k >>= std::countr_one(k) + 1;
    return k;
}