Modern CPUs are bottlenecked by memory, not computation. A single DRAM access costs ~100ns — roughly 200 CPU cycles. Cache-oblivious algorithms achieve optimal cache performance without knowing cache line size, associativity, or total cache capacity. They work everywhere: L1, L2, L3, disk.
The Memory Hierarchy Problem
Consider traversing a binary tree stored in pointer-based layout:
struct Node {
int key;
struct Node *left, *right;
};Every pointer chase is a potential cache miss. On a tree with n nodes, traversal takes O(n) cache misses — each node is on a different cache line. The hardware prefetcher can't help because pointer chasing is irregular.
// Pointer-based tree: terrible cache behavior
void traverse(Node *root) {
if (!root) return;
traverse(root->left); // cache miss
traverse(root->right); // cache miss
}The van Emde Boas Layout
The vEB layout flattens a complete binary tree into an array by recursively placing the top half of the tree contiguously, then the bottom half:
def veb_layout(tree: list, start: int, end: int) -> list:
"""Flatten a complete binary tree into vEB order.
Top sqrt(n) nodes come first, then two sqrt(n)-sized subtrees."""
if end - start <= 0:
return []
mid = (start + end) // 2
# Root node at index 0
result = [tree[mid]]
# Top subtree (height h/2)
result.extend(veb_layout(tree, start, mid))
# Bottom subtree (height h/2)
result.extend(veb_layout(tree, mid + 1, end))
return result
# For a complete binary tree of height h:
# Top sqrt(n) nodes → height h/2 subtree
# Next sqrt(n) nodes → another h/2 subtree
# Result: tree traversal touches O(log n) cache lines instead of O(n)The key insight: traversing the top sqrt(n) nodes stays in cache. Then you recurse into subtrees that also fit in cache. Total cache misses: O(log n / log B) where B is cache line size in nodes.
Cache Complexity Model
Cache-oblivious analysis uses the cache miss model:
- M: cache size (in cache lines)
- B: cache line size (in elements)
- A cache miss loads B adjacent elements
- An algorithm is cache-oblivious if it achieves O(1/B * T) cache misses for any M, B
// Matrix multiply: naive vs cache-oblivious
// Naive: O(n³) cache misses (terrible)
void naive_multiply(double *A, double *B, double *C, int n) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
C[i*n + j] += A[i*n + k] * B[k*n + j];
}
// Cache-oblivious (recursive): O(n³/B) cache misses (optimal)
void recursive_multiply(double *A, double *B, double *C,
int n, int nstrideA, int nstrideB) {
if (n <= BASE_CASE) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
C[i*nstrideB + j] += A[i*nstrideA + k] * B[k*nstrideB + j];
return;
}
int half = n / 2;
recursive_multiply(A, B, C, half, nstrideA, nstrideB);
recursive_multiply(A, B + half, C + half, half, nstrideA, nstrideB);
recursive_multiply(A + half, B, C + half*nstrideB, half, nstrideA, nstrideB);
recursive_multiply(A + half, B + half, C, half, nstrideA, nstrideB);
}Fractal Layouts for Sparse Matrices
The vEB idea generalizes to any recursive structure. Sparse matrices stored in CSR format can use a "fractal" or "recursive block" layout:
Original CSR (row-major):
Row 0: [nonzero, nonzero, zero, zero, nonzero]
Row 1: [zero, nonzero, zero, nonzero, zero]
...
Recursive block layout:
Block 0x0 (top-left quadrant)
Block 0x1 (top-right quadrant)
Block 1x0 (bottom-left quadrant)
Block 1x1 (bottom-right quadrant)
Each block recursively subdividedThis layout keeps nearby-in-matrix elements nearby-in-memory, even for sparse patterns.
Practical Performance
import numpy as np
import time
def measure_cache_behavior(n: int):
"""Compare naive vs tiled matrix access patterns."""
matrix = np.random.rand(n, n)
result = np.zeros(n)
# Column-wise access (cache-hostile)
start = time.perf_counter()
for _ in range(100):
for j in range(n):
result[j] = matrix[:, j].sum()
col_time = time.perf_counter() - start
# Row-wise access (cache-friendly)
start = time.perf_counter()
for _ in range(100):
for i in range(n):
result[i] = matrix[i, :].sum()
row_time = time.perf_counter() - start
return col_time, row_time
# n = 4096: column access is 3-5× slower than row access
# The difference comes entirely from cache missestradeoff / Cache-Oblivious vs Cache-Aware
Cache-oblivious design is especially valuable in libraries and frameworks that run on diverse hardware. You write the algorithm once, and it automatically adapts to any cache hierarchy — from ARM embedded to x86 server.
Cache-oblivious algorithms are portable and automatic. Cache-aware algorithms can be marginally faster when tuned for specific hardware, but require architecture-specific constants. For most applications, cache-oblivious is sufficient.
Synthesis
Cache-oblivious algorithms use recursive decomposition to match memory hierarchy levels without explicit knowledge of cache parameters. The van Emde Boas layout for trees, recursive matrix multiply, and funnel sort are canonical examples. The technique transforms O(n) cache misses into O(n/B) or better, which in practice means 10-100× speedups on real workloads.