Cache-oblivious algorithm

Cache-oblivious algorithms optimize data movement without explicitly knowing cache parameters. Their analyses usually use the ideal-cache model: a processor has a cache of size M, transfers data in blocks of B contiguous items, and incurs a cost for each block transfer; the algorithm itself is not given M or B.

The central resource is locality. A computation has good temporal locality when it reuses recently loaded data and good spatial locality when it accesses nearby data. A successful layout or recursion pattern creates useful groups at both coarse and fine scales, allowing one decomposition to fit successively into lower-level caches, translation lookaside buffers, and sometimes external storage.

This approach differs from a cache-aware algorithm, which explicitly selects tile sizes or blocking parameters after measuring the target machine. Cache obliviousness is a property of the algorithmic design and analysis, not a guarantee that every implementation is optimal on every processor.

Divide-and-conquer supplies the most widely used cache-oblivious technique. A recursive matrix multiplication divides matrices into quadrants until subproblems fit in cache; because the recursion visits progressively smaller regions, it obtains the optimal asymptotic block-transfer bound for many dense multiplication settings without choosing a tile size.

Recursive scans and merges similarly expose contiguous subproblems. A scan of N items can use O(1 + N/B) transfers, while cache-oblivious sorting achieves bounds matching the comparison-based external-memory optimum up to standard model assumptions, commonly O((N/B) log_M/B(N/B)).

Search structures use layouts such as the van Emde Boas-style recursive arrangement and cache-oblivious B-trees. These structures separate logical ordering from physical placement, preserving search locality across unknown block sizes while supporting updates with additional rebuilding or buffering mechanisms.¹

Cache-oblivious methods are useful when a program encounters several memory levels or runs on machines whose parameters vary. Important applications include matrix operations, sorting, searching, computational geometry, graph-related data structures, image processing, and out-of-core computation. The same locality principles can also reduce transfers between main memory and storage, although the cost model must then account for much larger and less uniform delays.²

The guarantee is model-dependent. Real processors have set associativity, hardware prefetching, nonuniform access costs, write buffers, vector units, shared caches, and operating-system effects that the ideal-cache model abstracts away. Recursive code may also incur instruction overhead, poor branch behavior, or excess metadata. Consequently, a cache-oblivious algorithm can have excellent asymptotic transfer complexity yet lose to a carefully tuned cache-aware implementation on a particular workload.

Correctness also remains independent of locality. A cache-oblivious design does not automatically solve synchronization, parallel scheduling, false sharing, or data placement on nonuniform memory architectures; parallel variants require separate scheduling and granularity arguments.

Cache-obliviousness is closely connected to external-memory algorithms, but the two traditions emphasize different knowledge assumptions. External-memory algorithms often know the block size and memory capacity and tune their blocking explicitly; cache-oblivious algorithms seek bounds that hold simultaneously for every feasible M and B, often through a tall-cache condition such as M = Ω(B²) for particular analyses.

Memory layout can matter as much as control flow. A recursively laid-out matrix, tree, or graph can keep related objects near one another at several scales, whereas a conventional row-major or pointer-heavy representation may defeat otherwise good recursion. This has led to cache-oblivious layouts for B-trees, funnelsort, priority queues, and geometric data structures.¹

A further edge case is parallelism: work-stealing schedulers can preserve cache-oblivious bounds for some divide-and-conquer computations, but only under assumptions about scheduling and the memory hierarchy. Thus the term describes a design discipline and analytical objective, not a universal performance certificate.

Ideal-cache model

An analytical model with a cache of size M and transfers in blocks of B items, used to count memory movements.

Cache-aware algorithm

An algorithm that uses known cache or block parameters to choose layouts, tile sizes, or other tuning decisions.

Tall-cache assumption

A relationship between cache capacity and block size, often imposed to make cache-oblivious bounds hold.

Spatial locality

The tendency to access data near a location that was accessed recently.

Temporal locality

The tendency to reuse data within a relatively short interval.