hesela.devLocality of reference
Locality of reference is the tendency to reuse recently accessed data or access nearby addresses within a short interval.
Temporal locality concerns reuse of the same data over a short interval; spatial locality concerns nearby addresses in a specified address space. These patterns motivate caching and fetching neighboring data, but do not guarantee a speedup. [1]
Nonsequential accesses can repeatedly visit a small set, while a sequential one-pass scan need not revisit any entry. Evaluate the pattern at the cache-entry granularity and observation interval, rather than treating random I/O as the absence of locality. This is a distinction between access order and reuse, not a measurement of a device. [1] [3]
A working-set size summarizes distinct entries in a chosen window. Reuse distance instead counts distinct identities strictly between consecutive references to one entry; the two measurements answer different questions. This is the zero-based reuse-distance convention; some papers instead count a one-based stack position. [2] [4] [3]
An upstream cache can absorb repeated reads before they reach a lower storage layer. A device-level trace therefore need not expose the application's reuse pattern; comparisons must name the observation point and history interval. [3]
Relations
- related
- Working set, Reuse distance, Miss-ratio curve, SSD mapping cache, Page cache, Cache pollution
Limitations
- Locality depends on the observation layer and granularity; a workload label alone does not establish a cache hit ratio. [3]
Citations
- Peter J. Denning. The Locality Principle. Communications of the ACM 48(7), July 2005, pp. 19-24.
- Peter J. Denning. The Working Set Model for Program Behavior. Communications of the ACM 11(5), May 1968, pp. 323-333, section 3.
- Wires et al. Characterizing Storage Workloads with Counter Stacks. OSDI 2014, sections 2 and 3.2.
- Ding and Zhong. Reuse Distance Analysis. UR-CS-TR-741, February 2001, section 2.1 and Figures 1-3.
Further reading
Sources & caveats
- Denning 2005 discusses temporal and spatial clustering and locality phases; Wires et al. provides storage-cache trace context.
- The sequential/nonsequential distinction is an engineering interpretation, not a device performance result.
- Repair locality and storage-tier temperature are separate existing concepts, not aliases of reference locality.