A cache-oblivious algorithm achieves near-optimal cache performance without being told anything about the cache. No cache line size, no cache capacity, no hierarchy depth. It runs well on L1 and L2 and L3 and main memory and disk — all at once, with a single code path. This sounds impossible. It isn't, and understanding why it isn't is a small lesson about what a memory hierarchy really is.
the cache-aware instinct
The usual way to make an algorithm cache-friendly is to measure the cache. Find the cache line size — probably 64 bytes. Find the L1 capacity — probably 32 KB. Tile your loops so each tile fits in L1. Align your data structures to cache line boundaries. The result is fast, and specific to the machine you tuned it for. Run the same binary on a machine with a different cache size and the performance can collapse.
This is cache-aware programming. It works, and it is brittle.
the oblivious trick
Cache-oblivious algorithms are structured recursively, with the recursion dividing the problem by a constant factor at each level. The recursion does not know how big the cache is, and does not care. Here is the key observation: at some level of the recursion, the subproblem happens to fit in the cache. It doesn't matter which level. Once the subproblem fits, the rest of the work on that subproblem runs entirely in cache, and the cost becomes memory-bandwidth-bound instead of latency-bound.
Because the recursion continues dividing below that level, the same thing happens for the next level of cache. The work on a smaller subproblem eventually fits in L1 after already fitting in L2, L3, and main memory. Each level of the hierarchy gets its own "aha" moment automatically, without the algorithm being aware that the hierarchy exists at all.
matrix transpose as the canonical example
Transposing a matrix naively is a cache catastrophe. The naive loop reads rows and writes columns, or vice versa, which means every write touches a different cache line. For a large matrix, almost every write is a cache miss.
The cache-oblivious transpose is recursive: split the matrix into four quadrants, transpose each quadrant recursively, then swap the off-diagonal quadrants. Base case: when the submatrix is small enough, transpose it directly.
fn transpose(m: &mut [[f64; N]; N], r0: usize, r1: usize, c0: usize, c1: usize) {
let rows = r1 - r0;
let cols = c1 - c0;
if rows <= BASE && cols <= BASE {
// base case: transpose in place
for i in r0..r1 {
for j in c0..c1 {
if i < j { m[i].swap(j, i); }
}
}
return;
}
if rows >= cols {
let mid = (r0 + r1) / 2;
transpose(m, r0, mid, c0, c1);
transpose(m, mid, r1, c0, c1);
} else {
let mid = (c0 + c1) / 2;
transpose(m, r0, r1, c0, mid);
transpose(m, r0, r1, mid, c1);
}
}The recursion divides the matrix until some level fits in L3. That level runs once per L3 miss instead of once per L3 line. The recursion continues dividing until some sub-level fits in L2, then L1. The number of cache misses asymptotically matches the best cache-aware algorithm — without ever querying the cache.
the lesson
The memory hierarchy looks like a set of distinct layers — registers, L1, L2, L3, DRAM, disk — but from an algorithmic point of view, the layers are interchangeable. Each one is a smaller, faster region sitting on top of a larger, slower region. An algorithm that is fast at one boundary is fast at all of them, as long as it is structured to decompose into subproblems of geometrically decreasing size.
Cache-obliviousness is not a clever trick. It is a recognition that the right shape for an algorithm is the same shape the hardware already has: recursive, self-similar, invariant under change of scale. Write the algorithm that matches the hardware's structure, and the hardware rewards you at every level at once.