  The program performance on modern hardware is characterized by \emph{locality
of reference}, that is, it is faster to access data that is close in address
space to data that has been accessed recently than data in a random location.
This is due to many architectural features including caches, prefetching,
virtual address translation and the physical properties of a hard disk drive;
attempting to model all the components that constitute the performance of a
modern machine is impossible, especially for general algorithm design purposes.
What if one could prove an algorithm is asymptotically optimal on all systems
that reward locality of reference, no matter how it manifests itself within
reasonable limits? We show that this is possible, and that excluding some
pathological cases, cache-oblivious algorithms that are asymptotically optimal
in the ideal-cache model are asymptotically optimal in any reasonable setting
that rewards locality of reference. This is surprising as the cache-oblivious
framework envisions a particular architectural model involving blocked memory
transfer into a multi-level hierarchy of caches of varying sizes, and was not
designed to directly model locality-of-reference correlated performance.
