= Temporal locality
Temporal locality is the tendency for the same item to be accessed again soon after an earlier access. For <computer memory>, the item might be an <array> element, a <cache line> or a <memory page>; always specify the unit. <Temporal locality> concerns reuse over time, whereas <spatial locality> concerns accesses to nearby addresses. Both are properties of a workload, rather than guarantees about its next <memory reference>. <Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, chapter 22, section 22.5 and the Types of Locality aside]{ref}
For a worked example, let $A$ and $B$ denote two distinct <cache blocks> at unrelated, nonadjacent <physical addresses>. An initially empty <fully associative cache> holding two <cache lines>, with <LRU replacement>, receives the <sequence> $A,B,A$. The first $A$ causes a <cache miss> and leaves $A$ resident; $B$ causes another <cache miss> and leaves both $A$ and $B$ resident; the last $A$ is a <cache hit>. <LRU replacement> now regards $B$ as older than $A$. The benefit comes from <temporal locality> of $A$, irrespective of how far apart the <cache blocks> lie. With capacity one, the same <sequence> gives three <cache misses>: reuse helps only if the item survives until it is needed.
The appealing idea is that a small <memory cache> can serve a large computation when its currently useful data stay small. Repeatedly reading a counter or executing the same instructions can exploit <temporal locality>. <LRU replacement> and recency-based approximations try to retain recently used items. A <working set> records recent demand; if the active <working set> cannot fit in resident <memory pages>, <memory thrashing> can defeat this benefit. At <cache line> granularity, even accesses to different <array> elements can reuse the same <cache block>, as the <spatial locality> example shows.
Peter J. Denning's May 1968 paper connected recent <memory page> use to near-future demand through the <working set>. Section 3 explicitly discusses the clustering of references to the same <memory page> in time. This is a documented early treatment of the reasoning behind <temporal locality>, rather than a claim about who first coined the term. https://denninginstitute.com/pjd/PUBS/WSModel_1968.pdf[Peter J. Denning, The Working Set Model for Program Behavior, Communications of the ACM 11(5), section 3: Definition and Properties, especially P2: Prediction]{ref}
Back to article page
