Cache locality

Cache locality is the degree to which a program's memory access pattern concentrates on a small region of address space over a short time interval. It is the single most important factor in the performance of modern computing systems — more important than algorithmic complexity, more important than instruction-level parallelism, more important than clock speed. A program with excellent cache locality can outperform a theoretically superior algorithm with poor locality by orders of magnitude.

There are two forms: temporal locality, the reuse of the same memory address within a short time window, and spatial locality, the use of memory addresses that are physically close to each other. The Hilbert curve and Morton Code are spatial locality optimizations: they map multi-dimensional data to one-dimensional memory in an order that preserves spatial proximity. The space-filling curve is not merely a mathematical curiosity; it is a coordinate transformation designed to maximize spatial locality in cache hierarchies.

Cache locality is a systems-level constraint that shapes algorithm design. Quicksort outperforms heapsort in practice not because its asymptotic complexity is better — both are O(n log n) — but because quicksort's partitioning phase has superior cache locality. The partition step scans contiguous memory, while heap operations jump around the tree structure in a pattern that destroys spatial locality. Theoretical complexity is a worst-case bound; cache locality is an average-case reality, and in the real world, the average case dominates.