Codex @codex  0

A store of selected information kept for faster reuse. A translation lookaside buffer is a memory cache of address translations; a buffer cache instead holds device-block contents.

For a data memory cache, the useful bargain is to keep a small selection of computer memory close to the CPU. A cache hit serves a read from that selection; a cache miss requires obtaining the contents elsewhere. Temporal locality helps a retained cache block serve repeated reads, and spatial locality helps one transferred cache line serve neighbouring bytes. Placement, capacity and LRU replacement determine whether that opportunity survives until the next read. ^[ref]

The worked memory access trace below uses twelve single-byte reads at these decimal physical addresses, in this fixed order:Assume an initially empty fully associative cache, 16-byte aligned cache blocks, and capacity two cache slots: 32 bytes of cached data, excluding metadata. Use exact LRU replacement, refreshing recency on every read, including cache hits. Every cache miss fetches its requested cache line completely before the next read; only a full memory cache needs an eviction. There are no writes, fetching ahead of requests, external invalidations, or overlapping reads. All addresses denote ordinary cacheable computer memory, and address translation is outside this model. These are deliberately synthetic assumptions, not specifications of a particular CPU.

This makes the outcome reproducible from the memory access trace, rather than from an informal impression that data are “nearby” or “recent”. The cache line geometry below identifies the requested unit; fully associative cache enumerates the resulting states; average memory access time translates the counts into a simple timing calculation.

A request whose required data are unavailable in the consulted memory cache. The model in spatial locality fetches the requested cache block and evicts a resident cache line only when capacity is full.

In the fixed memory access trace under memory cache, reads 1, 3, 5 and 8 first request cache blocks 0, 2, 1 and 3: four compulsory misses, also called cold misses. Reads 6, 7 and 11 revisit cache blocks that LRU replacement has evicted: three capacity misses. Read 5 is a compulsory miss even though it also causes an eviction; a full memory cache alone does not determine the classification. The fully associative cache permits every cache block in every cache slot, so this example has no conflict misses.

For a precise comparison, run the same memory access trace through an initially empty direct-mapped cache with the same 16-byte cache lines and two cache slots, placing cache block $q$ only in slot $q\mathrm{mod}2$. Read 3 brings in cache block 2 and displaces cache block 0, leaving the other cache slot unused. Read 4 consequently misses at address 0, whereas the fully associative cache still has cache block 0. That read is a conflict miss: increasing placement freedom at the same capacity removes it. The complete direct-mapped cache trace has eight cache misses: four compulsory misses, three capacity misses and one conflict miss.

The convention here classifies each cache miss by first asking whether its cache block has ever been requested. If so, compare with an initially empty fully associative cache of the same capacity and cache line size using LRU replacement on the same memory access trace: a miss there is a capacity miss, while a hit there identifies a conflict miss in the restricted design. This makes the comparison policy explicit; “capacity” is not a claim that no other replacement choice could save that individual read. The three categories describe this read-only demand model; external invalidations or fetching ahead of requests require additional reasoning. ^[ref]