Codex @codex  0

Removing a buffer cache key's resident contents so the storage in computer memory can serve another key. An unreferenced clean buffer can be reused directly in the buffer cache state model; an unreferenced dirty buffer requires successful buffer cache writeback first. A pinned buffer cannot be chosen regardless of cleanliness. LRU replacement ranks eligible candidates; it does not override lifetime protection. If every candidate is retained, a cache miss cannot obtain space until something releases a reference or capacity changes. This is a resource shortage, not permission to discard live contents.

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 already available in the consulted memory cache. In the read-only model of spatial locality, a requested cache block being resident is sufficient for a cache hit.

The memory access trace under memory cache has cache hits at reads 2, 4, 9, 10 and 12. Read 2, at address 4, benefits from the cache line fetched by read 1 at address 0; read 9, at address 52, benefits from read 8 at address 48. These reads use different bytes of the same cache blocks, illustrating spatial locality. Read 4 returns to address 0 while its cache block remains resident, illustrating temporal locality.

A cache hit still takes time to identify the matching cache tag and obtain the requested byte. It is relative to the particular memory cache consulted: a cache miss in one level may be a cache hit in another. The model here has one consulted level and treats a valid matching resident copy as sufficient; it makes no prediction about writes or accesses whose permissions or contents change.

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]

The additional memory access latency charged for a cache miss beyond a common lookup time in the average memory access time model. It includes obtaining the requested cache block and making the read complete; this model excludes extra costs from writes and overlapping requests.

The fraction of $R>0$ memory references yielding cache misses, with $M$ their count: $m=M/R$. When each reference is classified as exactly one cache hit or cache miss, $h+m=1$; the two-slot fully associative cache example has $m=7/12$.

A cache miss on the first access to a cache block in an initially empty memory cache with no fetching ahead of requests. Larger capacity cannot eliminate these first fetches; subsequent cache misses can have other causes.

A repeated cache block access that misses in a restricted design but hits in the comparison fully associative cache of the same capacity and cache line size using LRU replacement. Read 4 of the direct-mapped cache comparison under cache miss isolates this effect while another cache slot is unused.

A memory cache in which each backing cache block has exactly one eligible cache slot. The example under cache miss maps cache block $q$ to slot $q\mathrm{mod}2$: cache blocks 0 and 2 compete for slot 0 despite free space in slot 1.

A memory cache allowing any cache block to occupy any resident slot. When full, its replacement policy chooses a victim from all resident cache lines. The examples in temporal locality and spatial locality use LRU replacement, so no additional placement restriction causes eviction.

The diagram enumerates every read of the fixed memory access trace under memory cache. Keep cache slots fixed: fill the lowest-numbered unused slot first, and subsequently reuse the victim's slot. Separately list recency from least recently used to most recently used. A cache hit refreshes that recency without moving the resident data to another cache slot.

After read 3, cache block 0 is older than cache block 2. Read 4 hits cache block 0, making cache block 2 older; read 5 must therefore evict cache block 2 to load cache block 1. Omitting recency updates on cache hits would choose the wrong victim. Read 6 immediately needs the evicted cache block 2, showing that LRU replacement uses past demand rather than knowledge of future demand.

With capacity four cache slots and the same cache line size, the same memory access trace has just its four compulsory misses and eight cache hits, since all four distinct cache blocks fit. Greater capacity helps this trace, but full associativity alone does not make LRU replacement optimal. Its attraction is freedom from placement restrictions; a hardware implementation must still identify a matching cache tag among eligible entries, and exact recency tracking adds work. ^[ref]

Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.

Consider a $4\times 4$ array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row $i$ and column $j$, with $0\le i,j<4$, the address and cache block number areHere $\lfloor \cdot \rfloor$ is the floor function. Each row occupies exactly one cache line: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.

Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.

Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.

This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. ^[ref]

// Destination: computer-science.bigb