Cache Basics: Blocks, Hits, and Misses

A cache is a small, fast storage structure that holds a subset of the data found in a larger, slower memory, positioned so the processor checks it first. The defining property of a cache is not its physical technology (though caches are almost always built from SRAM rather than DRAM) but its role: it sits in the memory hierarchy between a fast consumer and a slow producer of data, and it works only because most accesses can be satisfied without going to the slow producer. Caches do not move data one byte or one word at a time. Instead, memory is divided into fixed-size, aligned chunks called blocks (also called lines), typically 32 to 128 bytes in modern processors. When the processor requests a single byte or word that is not in the cache, the entire block containing that address is fetched from memory and installed in the cache. This is the mechanical expression of spatial locality: if you touch one address, you are likely to touch nearby addresses soon, so fetching the whole neighborhood in one trip amortizes the cost of the slow access. Every memory access made by the processor is classified as either a hit or a miss. A hit occurs when the requested block is already present in the cache; the data is returned quickly, in the cache's fast access time. A miss occurs when the requested block is absent; the system must fetch the block from a lower, slower level of the hierarchy (a lower-level cache or main memory), install it in the cache, and only then supply the requested data — incurring a miss penalty. The hit rate of a cache is the fraction of accesses that are hits, and the miss rate is the complementary fraction. These are empirical, workload-dependent quantities, not fixed properties of the hardware: the same cache can have a 98% hit rate on one program and a 60% hit rate on another.

To understand hits and misses precisely, walk through what happens on every memory access. The processor issues an address. The cache must determine, using some fast lookup mechanism (detailed in Direct-Mapped Caches and later associative designs), whether the block containing that address currently resides in the cache. Two outcomes are possible.

On a hit, the cache locates the data within the block already stored and returns it in a small, fixed number of cycles — the cache's hit time. No trip to memory is needed.

On a miss, several things must happen in sequence: the cache must select a location to place the new block (possibly evicting an old one, a topic explored under replacement policies), issue a request to the next level down for the entire block, wait for that block to arrive, install it in the cache, and finally extract the requested word and return it to the processor. The total extra time this costs, beyond a hit, is the miss penalty. The key structural fact that block-based organization exploits is this: a single miss "pays for" many future hits, provided the program exhibits locality. If a program reads an array sequentially, one miss on the first element of a block brings in the entire block, and subsequent accesses to the other elements of that block are hits — even though those bytes were never individually requested before. ``` function ACCESS(address): block_number = address DIV block_size // which block this address falls in block_offset = address MOD block_size // position within the block if CACHE_LOOKUP(block_number) == FOUND: // HIT data = CACHE_READ(block_number, block_offset) record_hit() return data // fast path: hit_time cycles else: // MISS record_miss() new_block = FETCH_FROM_MEMORY(block_number) // slow: miss_penalty cycles victim = CHOOSE_VICTIM_IF_NEEDED() // eviction policy, if cache full CACHE_INSTALL(block_number, new_block, victim) data = CACHE_READ(block_number, block_offset) return data // total: hit_time + miss_penalty function HIT_RATE(access_log): hits = 0 for each address in access_log: if ACCESS(address) resulted in a hit: hits = hits + 1 return hits / length(access_log) ``` Two design parameters fall directly out of this mechanism. The block size determines how much data is fetched per miss — larger blocks capture more spatial locality per miss but take longer to transfer and risk bringing in unused data (cache pollution). The cache capacity (total number of blocks the cache can hold) determines how much of the program's working set can be resident at once. Both parameters shape the hit rate, and both are explored quantitatively once the placement and replacement mechanisms of Direct-Mapped Caches are introduced.

Time. A cache hit resolves in the cache's fixed hit time, typically 1 to a few cycles for a small L1 cache — independent of cache size in the sense that lookup uses parallel hardware (tag comparison across a small number of ways), not a linear search, so hit time is O(1) with respect to the number of accesses. A miss costs hit_time + miss_penalty, where the miss penalty is dominated by the latency of the next level of the hierarchy (tens of cycles for L2, over a hundred for DRAM). The overall average memory access time (developed fully in Cache Performance and Average Memory Access Time) is ``` AMAT = hit_time + miss_rate × miss_penalty ``` This single equation is why hit rate matters enormously: even a miss rate of a few percent, multiplied by a miss penalty of 100+ cycles, can dominate the average. A cache with 95% hit rate, 1-cycle hit time, and 100-cycle miss penalty has AMAT = 1 + 0.05 × 100 = 6 cycles — six times slower than the hit time alone, illustrating why architects fight over the last few percentage points of hit rate.

Space. A cache of capacity C bytes organized into blocks of size B bytes holds C/B blocks. Each stored block requires bookkeeping overhead beyond the raw data: a tag (to identify which memory block currently occupies that cache line) and a valid bit (to distinguish real data from garbage at startup), and later a dirty bit once write-back is introduced. This metadata is a small constant per block, so total cache storage is Θ(C) plus Θ(C/B) bits of metadata — the metadata overhead shrinks, in relative terms, as block size B grows, which is one (partial) argument for larger blocks.

Correctness of the hit/miss classification rests on an invariant that any working cache must maintain: a block is reported present if and only if it was placed in the cache by some earlier miss and has not since been evicted or invalidated. Formally, define `resident(t)` as the set of block numbers held in the cache immediately after the access at time t. The invariant is: ``` block ∈ resident(t) ⟺ block was fetched at some time t' ≤ t AND block was not evicted between t' and t ``` Every correct cache design — direct-mapped, set-associative, or fully associative — must preserve this invariant exactly; a lookup mechanism that ever reports a hit for a block not truly resident (a false hit) would silently return stale or wrong data, breaking program correctness, not just performance. Conversely, reporting a miss for a resident block only costs performance, not correctness — which is why cache correctness proofs focus entirely on ruling out false hits.

Why locality makes this work — the honest argument. Caching is not a universally guaranteed speedup; it is a bet on locality that real programs statistically win. Temporal locality (recently accessed data will likely be accessed again soon) justifies keeping any recently touched data around at all. Spatial locality (data near a recently accessed address will likely be accessed soon) justifies fetching whole blocks rather than single words. A program with no locality — for example, accessing uniformly random addresses across a memory region far larger than the cache — gets essentially zero benefit from caching, and its miss rate approaches 100% regardless of cache design. Real workloads (loops, sequential array scans, stack-based recursion, instruction fetch) exhibit strong locality, which is the empirical fact that makes the entire memory hierarchy worthwhile.

Tradeoffs are real and unavoidable. Larger blocks improve spatial-locality capture per miss but increase miss penalty (more bytes to transfer) and can waste bandwidth and cache space on data never used (pollution) if locality is weak or access patterns are strided in a way that skips most of the block. Larger caches reduce capacity misses but increase hit time (physically larger SRAM arrays are slower to search) and cost more chip area and power. There is no single best block size or cache size independent of workload — this is precisely why real systems use multi-level hierarchies with different block sizes and capacities at each level.

Consider a tiny cache with block size = 16 bytes and enough capacity to hold 4 blocks, initially empty (a "cold" cache). A program touches the following byte addresses, in order: ``` 0, 4, 20, 16, 8, 36, 4, 100, 16, 100 ``` First compute each address's block number: block_number = address ÷ 16.

Out of 10 accesses, there are 4 misses and 6 hits. ``` hit_rate = 6 / 10 = 0.60 (60%) miss_rate = 4 / 10 = 0.40 (40%) ``` Notice the mechanism directly at work: the access to address 4 is a hit only because the earlier miss on address 0 pulled in the entire 16-byte block [0–15], which happens to contain byte 4 as well. Similarly, addresses 20 and 16 fall in the same block [16–31], so fetching block 1 once serves both. Every one of the 4 misses here is a compulsory miss (also called a cold-start miss) — the very first reference to a block that has never been in the cache before. This trace, with only 10 accesses and a cache with ample capacity, is too short to exhibit capacity misses (evicting a block only to need it again later, because the working set exceeds cache size) or conflict misses (a miss caused not by lack of space overall but by the mapping rule forcing two active blocks into the same cache location, a phenomenon introduced fully in Direct-Mapped Caches). To see why block size choice matters, rerun the same trace with block size = 8 bytes instead of 16. Now block_number = address ÷ 8:

Now there are 6 misses and only 4 hits — hit rate drops to 40%. Shrinking the block size lost the "free" hit that address 16 previously got from address 20's fetch (they're now in different 8-byte blocks), demonstrating concretely that block size directly governs how much spatial locality gets captured.

The cache concept emerged from a very concrete engineering pressure: by the 1960s, processor logic (built from fast but expensive and power-hungry circuits) was outrunning the affordable main memory technology of the day. Architects needed a way to make a small amount of expensive fast memory behave, statistically, like a much larger pool of memory — without programmers having to manage the movement of data by hand.

Wilkes's 1965 paper "Slave Memories and Dynamic Storage Allocation" is widely credited as the origin of the cache concept — he called it a "slave memory," a small fast store automatically managed by hardware to hold recently used data, invisible to the programmer. The idea was commercially realized shortly after in the IBM System/360 Model 85 (1968), the first machine to ship with a cache in the modern sense, and the term "cache" itself (from the French cacher, to hide) entered common usage soon after to describe this hidden, automatic layer.

Every modern general-purpose processor — from smartphone SoCs to server CPUs — relies on multiple levels of cache (L1, L2, L3) to keep execution units fed, and the vocabulary of blocks, hits, and misses is the shared language architects, compiler writers, and systems programmers use to reason about performance. Database engines and key-value stores build their own software caches (buffer pools, page caches) using the identical hit/miss/locality logic, just at a coarser granularity of disk pages instead of cache lines. Web infrastructure applies the same principle at yet another scale: CDN edge caches and browser caches reduce network round-trips using the exact same hit-rate reasoning developed here. Compiler optimizations such as loop tiling and data structure layout (array-of-structures versus structure-of-arrays) are explicitly designed to increase spatial and temporal locality, directly targeting cache hit rate as the performance lever. Understanding hits and misses is also the entry point into performance debugging: tools like `perf` and hardware performance counters report cache miss rates precisely so engineers can diagnose why a program runs slower than its instruction count alone would predict.

Ask the tutor: How does associativity change which blocks can map where, and why does that reduce conflict misses?