Cache Fundamentals: How Small, Fast Memory Predicts What You Need Next

Why Caching Works: The Principle of Locality

A cache is only useful because real programs do not access memory in a purely random pattern. Instead, they exhibit Locality of Reference, which comes in two related forms: Temporal Locality, meaning a recently accessed memory location is likely to be accessed again soon, and Spatial Locality, meaning memory locations near a recently accessed one are also likely to be accessed soon, such as the next elements in an array.

What a Cache Actually Stores

A Cache is a small, fast memory that holds copies of recently used data from main memory, positioned between the processor and main memory in the hierarchy discussed earlier in this series. When the processor requests data already present in the cache, it can be retrieved far faster than fetching it from main memory.

Locating Data: The Direct-Mapped Cache

The simplest cache organization is called a Direct-Mapped Cache, where each memory address maps to exactly one specific location in the cache, determined by a portion of the address bits.

Memory address broken into fields:
[ Tag | Index | Block Offset ]

• The Index bits select which cache location to check.
• The Tag bits are stored alongside the data and compared against the requested address to confirm the correct data is present, since multiple different memory addresses can map to the same index.
• The Block Offset bits select the specific byte within a larger stored block, since caches typically store data in fixed-size chunks rather than single bytes.

Cache Hits and Cache Misses

When the processor requests data and finds it already present in the cache with a matching tag, this is called a Cache Hit, and the data is returned quickly. When the requested data is not found, this is called a Cache Miss, and the processor must retrieve the data from a slower level of the memory hierarchy, then store a copy in the cache for potential future use.

On a cache hit:
Return data immediately from cache

On a cache miss:
Fetch data from main memory
Store a copy in the cache
Return data to the processor

Why Block Size Matters

Because of spatial locality, caches do not store just a single requested byte on a miss; they retrieve and store an entire Block (also called a Cache Line) of nearby memory at once, anticipating that neighboring data will likely be needed soon. Choosing an appropriate block size involves a tradeoff: larger blocks exploit spatial locality more effectively but take longer to transfer on a miss and can waste cache space if the extra data is not actually used.

Why Understanding These Basics Matters

Every more advanced caching topic discussed later in this series — measuring and improving cache performance, more flexible mapping strategies, and multi-level cache hierarchies — builds directly on these core concepts of locality, direct mapping, and the hit/miss distinction introduced here.