How Do Temporal and Spatial Locality Justify Memory Caching?
Temporal locality and spatial locality are two fundamental patterns in how computer programs access memory, and together they explain why caching recently accessed memory blocks dramatically improves system performance. Because processors execute instructions much faster than main memory can supply data, modern computers rely on small, high-speed caches to bridge this speed gap. By keeping recently used data and its nearby neighbors close to the processor, caches turn slow main memory accesses into fast cache hits.
The Speed Gap Between Processors and Memory
In classical computing, the central processing unit (CPU) operates at clock speeds that far exceed the access speeds of main memory (DRAM). Fetching a word from main memory can take hundreds of clock cycles, during which the processor would otherwise sit idle. To prevent this bottleneck, computer architects place a hierarchy of smaller, faster SRAM caches (such as L1, L2, and L3) between the CPU and main memory.
However, because fast SRAM is expensive and physically limited in size, a cache can only hold a tiny fraction of the data stored in main memory. For a cache to be effective, the processor must find the data it needs in the cache most of the time. This is where the principle of locality becomes essential.
Temporal Locality: Reusing Recent Data
Temporal locality refers to the tendency of a program to access the same memory location repeatedly within a short period of time. Common examples include:
- Loop variables and counters: A loop index or accumulator is read and updated on every iteration.
- Frequently called functions: Instructions in a hot loop or utility function are fetched repeatedly.
- Shared constants and flags: Configuration values or status flags are checked many times during execution.
Temporal locality directly justifies retaining recently accessed data in the cache. If a memory address is accessed once, there is a high probability it will be needed again soon. By keeping that data in the cache rather than immediately discarding it, subsequent accesses result in fast cache hits instead of slow main memory fetches.
Spatial Locality: Accessing Nearby Data
Spatial locality refers to the tendency of a program to access memory locations whose addresses are close to one another. Common examples include:
- Sequential instruction execution: Programs typically execute instructions one after another in memory.
- Array and struct traversal: Iterating through an array or reading fields of a data structure accesses contiguous memory addresses.
Spatial locality justifies fetching entire blocks (cache lines) of memory rather than individual bytes or words. When a cache miss occurs for address \(A\), the memory controller loads a contiguous block of data—typically 64 bytes—containing \(A\) and its neighboring addresses. As a result, when the program moves on to \(A + 1\), \(A + 2\), and so on, those values are already waiting in the cache.
How Both Principles Work Together
Together, temporal and spatial locality determine both what gets loaded into the cache and how long it stays there. Spatial locality ensures that a single memory fetch preloads nearby data that is likely to be needed next, while temporal locality ensures that recently used blocks remain in the cache for repeated use.
The performance benefit can be quantified using the Average Memory Access Time (AMAT):
\[\text{AMAT} = \text{Hit Time} + (\text{Miss Rate} \times \text{Miss Penalty})\]
By exploiting temporal and spatial locality, caches minimize the \(\text{Miss Rate}\), ensuring that the \(\text{Miss Penalty}\) of accessing main memory is paid as rarely as possible. Without these two locality patterns, caching recently accessed memory blocks would offer little advantage over reading directly from main memory.