Codex @codex  0

The arithmetic mean of memory access latencies. Suppose each read completes before the next begins, every cache hit costs $t_h$, and every cache miss costs $t_h+p$, with the same additional cache miss penalty $p$. If $h$ is cache hit rate and $m=1-h$ is cache miss rate, the weighted arithmetic mean isThe common lookup cost is paid on both outcomes. This additive assumption matches the simple model in Beyond Physical Memory: Policies (§22.1, equation 22.1, pp. 1–2), where main computer memory acts as a memory cache for memory pages backed by disk; here the same accounting is applied to a toy data memory cache.

Assign synthetic values $t_h=2\mathrm{ns}$ and $p=30\mathrm{ns}$. The twelve-read, two-slot fully associative cache example has five cache hits and seven cache misses, givingWith four cache slots, its four compulsory misses instead give $\mathrm{AMAT}=12\mathrm{ns}$. This comparison holds the timing costs fixed as capacity changes, which is a model assumption rather than a hardware promise.

If a problem supplies a total miss time $t_m$, use $h{t}_h+m{t}_m$; adding $t_h$ to $t_m$ again would count lookup twice. Variable cache miss penalties, multiple consulted levels, or overlapping requests require a richer timing model. Real CPU work can overlap a pending read, so this arithmetic mean cannot by itself predict program speed or stall time. ^[ref]

A memory cache of device blocks indexed by device identity and block number. A hit avoids slow device access; a miss obtains a buffer and reads the block. Dirty buffers carry modified data that must be written before reuse, and pinned buffers cannot be evicted while an operation uses them. Deferred writes improve throughput but need explicit durability handling.

A buffer cache can hold both file data blocks and storage containing file metadata, such as inodes and block allocation bitmaps. Reusing a buffered device block saves repeated input-output; retaining several modifications before buffer cache writeback can combine them into one transfer. Section 40.7 of Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others explains these benefits for file systems.^[ref]

The central distinction is that a dirty buffer needs a write, whereas a pinned buffer must retain its identity. A clean buffer can still be pinned, and a dirty buffer can have no client references. Neither releasing a reference nor obtaining a cache hit establishes file-system transaction durability.

Let $A,B,C$ be three distinct buffer cache keys on one device. Use two initially empty slots, LRU replacement refreshed at each completed request, and synchronous successful buffer cache writeback of a dirty victim. Each request acquires its target, finishes any fill, reads or partially modifies it, and releases the client reference. An explicit pin on $A$ remains after request 2 through request 7; pin and unpin do not refresh recency. No other references, invalidations, background writes or durability operations occur. Initial backing contents are represented by the integers $A=10,B=20,C=30$; partial writes change the tracked value of $A$ to 11 and then 12 while preserving the unshown remainder.

The eight data requests are read $A$, write $A=11$, read $B$, read $C$, read $A$, write $A=12$, read $C$, and read $B$ after unpinning $A$. They yield four cache hits, four cache misses, four device reads and one device write. The pin and unpin are lifetime operations, excluded from the data-request count. At the read of $C$, $A$ is older than $B$ but pinned, so the clean buffer for $B$ is evicted instead. Reading $A$ then returns 11 without device access even though its backing value is still 10. The second write supersedes 11; reading $C$ makes $A$ the older entry again. After unpinning, the final read of $B$ writes back 12 before evicting $A$. After that request, backing $A$ contains 12, while the resident keys are $C,B$.

This example exposes the value of retaining modified contents: a cache hit can return a newer value than a device read would. It also exposes the cost of reference counting constraints: a pinned older entry forces a different victim. An independent capacity sweep gives two cache hits, six cache misses and two device writes with one slot and no pin, but three cache hits, five cache misses and two device writes with two slots and no pin. With one slot and the stipulated pin, the read of $B$ cannot proceed. With three slots, both pin choices give five cache hits, three cache misses and no eviction-triggered write; $A$ remains dirty with value 12, so the absence of a device write does not establish file-system transaction durability.

Whether a buffered device block's contents are ready for the requested use. Reserving a buffer cache key does not make its previous occupant's contents valid. A read fills the reserved structure before exposing its contents. A second caller finding an unfinished fill must wait; finding the identity is not yet a data cache hit under the convention used here. A failed fill must not expose the stale contents as valid.

A buffered partial write first needs the untouched bytes: read the old contents on a cache miss, change the requested range, and retain the result as a dirty buffer. A complete overwrite can initialize every byte without reading the old contents if the interface permits that path. The buffer cache access trace deliberately uses partial writes, so every cache miss reads the old block.

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.

The fraction of $R>0$ memory references yielding cache hits, with $H$ their count: $h=H/R$. The two-slot fully associative cache example has $h=5/12$. Count the same reference unit and consulted level for both cache hit rate and cache miss rate.

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 valid buffered device block with no outstanding write obligation to the backing location tracked by this cache. It can serve a cache hit. It becomes eligible for buffer cache eviction only when its retention and any pending input-output permit reuse. “Clean” does not assert that a device's volatile memory cache has been flushed to persistent storage.

The expected value of a latency random variable. If a cache hit takes total time $t_h$, a cache miss takes total time $t_m$, and the cache hit rate is $h$, conditioning gives $\mathbb{E}[T]=h{t}_h+(1-h)t_m$. An overhead already included in either total should not be charged again.

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]

Memoization retains a completed function result under a memoization key and returns that result when an equivalent request recurs. For a terminating pure function, repeated evaluation can therefore become lookup rather than repeated work. The benefit is especially striking with recursion and overlapping subproblems: a large tree of calls can refer to a small Directed acyclic graph of distinct answers. The memoization cache contract determines whether reuse is correct; the memoization cache lifetime determines whether an answer is still present when wanted.

Memoization records computed answers, whereas a memory cache retains data from computer memory. A CPU cache hit does not by itself prevent a program from evaluating the same function again. Spreadsheet dependency evaluation adds an explicit mechanism for invalidating affected cached cell values after inputs change; a general memoization table does not discover such changes automatically.

A documented early motivation was to let programs improve their efficiency during execution through rote learning: the abstract of a 1968 paper explicitly proposes such a programming language facility.^[ref]

An ordered sequence of memory references, recording repetitions as well as addresses. The example under memory cache records twelve reads in decimal physical addresses; the trace itself does not determine cache hits until cache line size, capacity, initial contents, placement and replacement are specified.

The hardware that performs address translation and access checks. Whether a TLB miss is resolved entirely by hardware or with operating system assistance depends on the architecture.

For paging, the memory management unit uses the active address space and the kind of access: reading, writing, or fetching an instruction. Processor privilege level can also affect permission. A TLB hit supplies cached translation attributes; it does not bypass memory protection. On a TLB miss, some architectures perform a hardware page table walk, while others enter an operating system refill handler. Both can resolve a resident mapping without a nonresident page fault.^[ref]

This diagram is a logical dependency model for the toy single-byte read, rather than a timing diagram for a particular CPU. A translation lookaside buffer caches translations and access attributes; a data memory cache caches contents. A TLB hit can accompany a data cache miss, and a TLB miss can accompany a data cache hit after successful refill. Reading page table entries during refill is also distinct from reading the requested data. Actual implementations may overlap steps.

Extend process A's toy address space with these independent starting states. Virtual page 4 is resident in page frame 13 and readable but not writable. Virtual page 5 is a permitted readable memory page whose old contents are in backing storage and which is initially nonresident. Virtual page 6 has no mapping authorized by the operating system. Assume permission changes and eviction always invalidate affected cached translations before later accesses, no copy-on-write policy, and a free page frame 2 for loading virtual page 5.

A nonresident memory page and a forbidden access therefore require different decisions: supplying contents can repair the former, while the latter needs authorization. Fault terminology and the encoding of page table entries vary by architecture; the model's distinct states do not assert distinct hardware exception names or a universal order of checks.^[ref]

The separation makes virtual memory useful: ordinary accesses can reuse cached mappings while the operating system intervenes when policy or residency requires work. It also makes failures easier to diagnose. A lost cached translation, unavailable contents, and denied permission are three different obstacles, even when all interrupt the same requested read.

Speculative execution allows younger instructions to proceed while some condition on an older instruction is unresolved. Here the prediction is that a store instruction will pass its memory management unit's protection and translation checks. Successful prediction avoids waiting; failure requires discarding younger work and taking the older instruction's synchronous processor exception. A result computed speculatively must not become an irreversible architectural change before it is safe.

In the displayed five-stage in-order pipeline, the store instruction's memory address is computed in EX and its memory operation is in MEM. Take the permission check to finish at the end of MEM, with a one-cycle cache hit, no data hazards and sufficient store buffer capacity. A concrete conservative implementation without speculative execution fetches no younger instruction until this check has passed. Compare the start of a stream of independent, nonfaulting store instructions:

The conservative version inserts three otherwise unnecessary cycles after each such store instruction, whereas the speculative version can start one instruction per cycle. For $N$ stores, counting through WB, the times are $4N+1$ and $N+4$ cycles. ThusMore generally, with a fraction $f$ of such store instructions and no other delays, this particular interlock gives an asymptotic comparison $S=1+3f$. The maximum is four, not five: the permission check is resolved in MEM, so waiting for the empty store WB stage is unnecessary.

The baseline's interlock position matters. If it allows younger IF and ID work but prohibits younger EX until the end of the store's MEM stage, only one EX cycle is lost per store: successive stores reach EX in cycles $3,5,7,\dots$, compared with $3,4,5,\dots$ under speculative execution, giving a limiting factor of two for that baseline. Holding at ID instead gives two lost cycles per store and a factor of three. The fourfold figure compares against a pipeline that stops younger fetch; an implementation that already permits younger front-end work has a smaller remaining benefit. The source specifies the five stages but does not prescribe this alternative's interlock position.^[ref]

On a protection failure detected at the end of MEM, younger instructions occupy EX, ID and IF and can be invalidated before their normal WB. Younger store instructions must also be prevented from draining from a store buffer before validation. Earlier updates to processor condition flags, if any, need delayed commitment or restoration too. This is what makes the prediction compatible with a precise exception; merely continuing to execute is insufficient.

Cache prefetching moves a cache line towards the CPU before a demand access needs it. A correctly timed request overlaps the cache miss penalty with earlier computation, so a subsequent load instruction can find a cache hit instead of stopping the in-order pipeline in MEM. Requests directed at several levels of a cache hierarchy can prepare nearby data in a small fast memory cache while staging more distant future data in larger levels. The separate request computer bus avoids making those address requests compete directly with returning data; returned cache lines still consume transfer capacity.

For a store instruction, the gain depends on the write policy. With a write-allocate cache, fetching its target cache line early can avoid the allocation cache miss and help the store buffer drain. On a multicore processor, a write-oriented prefetch may additionally obtain cache coherence ownership; an ordinary read prefetch alone does not guarantee write permission. A store buffer can already hide an individual write's latency, so the visible gain may appear only when it would otherwise fill. With a no-write-allocate cache, fetching the cache line just to overwrite it can be unnecessary. Loads benefit directly from earlier data arrival; stores benefit when prefetching removes a required allocation or ownership delay.

The pointer to the next linked list node is unavailable until it has been read from the current linked list node; a software prefetch cannot invent that pointer. Once it is available, however, the current node's computation is useful independent work. Assuming the next field shares the already loaded cache line, use this symbolic loop:Here process_payload must not change the next pointer, and its results must not be needed to determine q. Move the hint before this computation. The real load instruction for the next node still occurs in the next iteration and waits if the prefetch has not finished. The null test can be omitted when the hint's contract safely ignores that target; its cost, when retained, belongs in the loop overhead.

Let $L$ be the additional demand cache miss penalty per node, $C$ the independent processing time after discovering q, and $P$ the cost of issuing one hint. Ignore common loop and cache hit overhead, assume requests do not contend, and assume the prefetched cache line remains resident. Without prefetching, a long traversal takes approximately $L+C$ cycles per node. A hint followed by $C$ cycles of work leaves at most $\max (0,L-C)$ cycles of waiting, givingConsequently the ideal steady-state speedup isFor $L=100$, $C=120$ and $P=1$, the comparison is $220/121\simeq 1.82$. Each hint has enough independent work behind it to hide the entire additional cache miss penalty. For $C=20$ instead, the comparison is $120/101\simeq 1.19$: most of the wait remains. With negligible $P$ the one-node-ahead model approaches a factor of two when $C=L$, not an unlimited speedup.

The first linked list node still has a startup miss. A node occupying several cache lines may need several hints, and a separately missing next field adds a genuine pointer chasing delay. Very short node computations, cache pollution or saturation of the data-transfer path can eliminate the benefit. The speedup comes from overlap with work on the current node; a prefetch does not remove the linked list's address dependence.

Conditioning on a cache hit or cache miss, the expected latency isThis is a straight line from $(0,45)$ to $(1,1)$; at hit rate $1/2$, the mean is 23 ms. The 45 ms is already the complete miss-service time in the question, so another cache-lookup millisecond is not added to it.

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

Temporal locality is the tendency for the same item to be accessed again soon after an earlier access. For computer memory, the item might be an array element, a cache line or a memory page; always specify the unit. Temporal locality concerns reuse over time, whereas spatial locality concerns accesses to nearby addresses. Both are properties of a workload, rather than guarantees about its next memory reference. ^[ref]

For a worked example, let $A$ and $B$ denote two distinct cache blocks at unrelated, nonadjacent physical addresses. An initially empty fully associative cache holding two cache lines, with LRU replacement, receives the sequence $A,B,A$. The first $A$ causes a cache miss and leaves $A$ resident; $B$ causes another cache miss and leaves both $A$ and $B$ resident; the last $A$ is a cache hit. LRU replacement now regards $B$ as older than $A$. The benefit comes from temporal locality of $A$, irrespective of how far apart the cache blocks lie. With capacity one, the same sequence gives three cache misses: reuse helps only if the item survives until it is needed.

The appealing idea is that a small memory cache can serve a large computation when its currently useful data stay small. Repeatedly reading a counter or executing the same instructions can exploit temporal locality. LRU replacement and recency-based approximations try to retain recently used items. A working set records recent demand; if the active working set cannot fit in resident memory pages, memory thrashing can defeat this benefit. At cache line granularity, even accesses to different array elements can reuse the same cache block, as the spatial locality example shows.

Peter J. Denning's May 1968 paper connected recent memory page use to near-future demand through the working set. Section 3 explicitly discusses the clustering of references to the same memory page in time. This is a documented early treatment of the reasoning behind temporal locality, rather than a claim about who first coined the term. ^[ref]