Computer memory

Storage holding information used by a computer. Here, resident memory pages occupy main computer memory; a physical address identifies a location in the physical address system rather than an operating-system process's private numbering.

Computer memory that retains stored information without power.

Non-volatile memory programmed and erased electrically. Its program and erase granularities need not match the block size exported to a file system.

An individually addressable place in computer memory holding a value. An abstract memory interface can separate reading and updating existing memory locations from allocating a fresh memory location.

Storage for pending writes, usually with their memory addresses, data and status. A younger load instruction must account for older overlapping buffered store instructions, often by store-to-load forwarding.

An age-ordered structure tracking store instructions, their memory addresses and data, and their eligibility to become visible. An implementation may distinguish a speculative store queue from the committed store buffer.

Satisfying a load instruction from an older pending store instruction rather than stale backing computer memory. The youngest applicable older write supplies each requested byte; unresolved or partial overlaps require additional handling.

A memory access whose execution is observable under the source language or machine rules, so that replacing repeated accesses by a saved value can change behavior. The precise guarantees depend on the programming language; volatile access alone does not provide thread synchronization.

A memory read through an address whose contents are fixed during ordinary operation. Used as a Boolean function lookup table, $a$ address bits select one of $2^a$ words, each holding $b$ output bits, so the logical table capacity is $2^{a}b$ bits. A finite-state machine can store its next-state function in such a table while separate flip-flops store the current state.

The ordering of the bytes of a multi-byte value in addressed memory. Little-endian storage puts the least significant byte at the lowest address; big-endian storage puts the most significant byte there. Logical shifts of a value already held in a processor register act on bit significance, independently of that storage convention.

A pointer is a value designating a location in a program's memory model, or a special value such as a null pointer that designates no object. A node in a pointer-linked binary tree stores pointers to its two children. Representation, size, alignment and the validity of dereferencing depend on the programming language and target; 32-bit AAPCS32 data pointers occupy four bytes.

Following a chain of stored pointers, as in a linked list. A later memory address may depend on the result of an earlier load instruction, limiting how far ahead cache prefetching can run.

A null pointer is a distinguished pointer value that designates no object or function. Pointer-linked binary trees commonly use it to represent an absent child. Dereferencing it is invalid; its representation is target dependent, although AAPCS32 specifies an all-zero null representation.

A numerical identifier for a location in computer memory. In a byte-addressed system, consecutive four-byte array elements have memory addresses differing by four.

An assembly language memory operand whose effective address is the sum of a base processor register and an offset processor register. A byte-load table lookup uses the index directly as a byte offset; wider entries require an appropriate scale. The effective address is formed from the old register values before the destination register is overwritten.

Storage used for heap allocation, with software object lifetimes not necessarily nested like procedure calls on a call stack. Garbage collection can reclaim unreachable software objects; keeping references to every allocated software object prevents that reclamation regardless of how little of each software object's data a program still needs.

Heap allocation creates an software object whose lifetime need not match one lexical procedure call. Other software objects can retain references to it after the constructing call returns. Automatic storage reclamation therefore follows reachability or another memory-management discipline, rather than simply returning from that call.

Making storage available for reuse after its object is no longer accessible to any legitimate user. Concurrent readers retaining old pointers make safe memory reclamation a separate problem from atomic pointer publication.

A published reader protection record used by a protocol that validates the protected pointer and delays memory reclamation while relevant readers may access the object. Merely copying an unprotected pointer does not supply this lifetime guarantee.

A family of concurrent access techniques that publishes replacement versions and postpones memory reclamation until a suitable grace period has passed. Correct reader tracking, publication ordering and lifetime rules are essential.

An interval sufficient to establish that every reader that might retain a preexisting reference has left its protected read-side region. Completion permits the corresponding old object to undergo memory reclamation.

An access through a pointer after its storage has been released. Reusing the same memory address for a different object can make this failure silently return unrelated data instead of immediately crashing.

Automatic reclamation of allocated storage no longer reachable by a program. Clearing a private linked structure can discard its root references in constant pointer work even though later reclamation may require additional collector work. Data-structure operation bounds should state whether they count deferred memory-management costs.

A tracing garbage collection implementation starts from garbage collection roots and follows software object references. Software objects outside that reachable set can be reclaimed, including cycles that have no path from a root. A decorator or adapter holding a component reference keeps that component reachable while the wrapper remains reachable. The number of allocated software objects alone does not establish how much storage can be reclaimed.

A garbage collection root is an initially accessible reference from which the collector traces reachable software objects. Depending on the runtime, roots include active stack or register references and static references. Software objects reached transitively through reference fields must remain live. Exact root sets and collection timing are implementation details.

Tracking how many references retain an object. For the copy-on-write model, the object is a page frame and each mapping retains it; removing the last reference permits reclamation. Real operating-system kernels can track other kinds of ownership too. ^[ref]

An access to a location in computer memory, such as an instruction fetch, a read or a write. A page-level reference sequence records the corresponding memory page for each access, retaining repetitions and order.

A null reference denotes the absence of an ordinary referenced software object. In null-terminated linked lists it marks the end of a chain. A search can return it to signal absence, but the caller must check before selecting data members. Short-circuit evaluation can make a combined nonnull-and-property guard safe.

Two program references designate the same mutable object or overlapping mutable state. Binary-update contracts must account for this possibility: an update intended to combine two old values should snapshot both operands before modifying the receiver. A frame condition preserving a distinct operand cannot literally preserve a second reference that aliases the modified receiver.

A copy that duplicates the relevant reachable mutable structure instead of sharing all original references. A Memento pattern snapshot containing mutable arrays must preserve their saved contents against subsequent mutation, whether by a suitable deep copy or by an immutable persistent representation. The intended ownership graph and any permitted sharing must be specified; blindly copying one outer object is only a shallow copy.

The identity of a particular allocated object, distinct from equality of its current fields. Two different linked list nodes can store identical payloads, while two references can designate the same node. Pointer algorithms must state whether they preserve identities, copy payloads or allocate replacements. Testing cycle completion by identity avoids confusing two equal-looking nodes.

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.

An address in the physical address system, obtained from a virtual address by address translation in the examples here. Physical address ranges can also identify devices, so not every physical address denotes ordinary computer memory.

A unit of information; throughout these examples, one byte contains eight bits and is the smallest independently addressed unit of computer memory.

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.

Consistency requirements for cached copies of the same memory location, including agreement on its writes. Cache coherence does not itself impose sequential consistency across different locations.

Independent data in the same cache line cause unnecessary ownership transfers or invalidations when different CPU cores access them. A frequently written lock beside stable reader data can invalidate those data despite no logical conflict.

Loss of useful cached data because less useful data occupy the limited memory cache. Excessive cache prefetching can increase later demand cache misses by evicting useful cache lines.

A memory cache policy that sends a write miss onward without allocating the missed cache line in that level. Different levels of a cache hierarchy may use different write policies.

A memory cache policy that allocates the relevant cache line on a write cache miss. Fetching that cache line can delay a store instruction unless other mechanisms hide the delay.

Several levels of memory cache, typically combining a small low-latency first level with larger later levels. Each level reduces traffic reaching the next; local and global cache miss rates must be distinguished.

Fetching a cache line before a demand access requires it, to overlap transfer latency with useful work. A software prefetch is one way to request this; unnecessary requests can cause cache pollution.

A program-directed hint to fetch a cache line early. A useful nonblocking hint produces no destination processor register value and allows execution to continue before the transfer completes. Fault and dropping behavior depend on the specified instruction contract.

Keeping reusable copies in a cache.

A fixed-sized, aligned block of consecutive bytes transferred and tracked as a unit by a data memory cache. Here cache line and cache block name that unit of data, including its identity in backing computer memory; a resident slot holds a copy. Reading one element can bring neighbouring elements into the same cache line, exploiting spatial locality.

For a nonnegative integer physical address $a$ and a cache line size $B$ bytes, Euclidean division gives the backing cache block number $q$ and offset $d$:Here the brackets denote the floor function and $\mathrm{mod}$ gives the remainder. Cache line $q$ contains bytes at physical addresses $Bq$ through $Bq+B-1$. With $B=16$, read address 52 selects cache block 3, spanning addresses 48–63, and offset 4. Addresses 48 and 52 therefore request the same cache line; addresses 15 and 16 request different cache lines despite being adjacent.

For a cache line size $B=2^b$, the low $b$ bits give the offset. In a fully associative cache, all remaining bits identify the backing cache block as its cache tag; there are no address bits selecting a particular cache slot. An eight-bit illustration gives $52={00110100}_2$: four bits 0011 for cache block 3 and four bits 0100 for offset 4 in the binary numeral system. The eight-bit width is illustrative; the trace does not assume an actual eight-bit machine. ^[ref]

Distinguish this identity from a cache slot, which can hold different cache blocks over time. After read nine in the memory cache example, cache slot 0 contains cache line 3 and cache slot 1 contains cache line 0. Their cache tags identify 3 and 0; neither cache line number is its slot number. Some texts use “cache line” for the storage entry itself; this article reserves cache slot for that role.

A resident storage entry that can hold one cache block and metadata identifying its contents. Cache line identity belongs to backing computer memory; cache slot identity belongs to the consulted memory cache.

Metadata identifying which eligible backing cache block a valid cache slot currently holds. In the fully associative cache example, the cache tag is the full cache block number $q$; in the two-slot direct-mapped cache example, the slot supplies $q\mathrm{mod}2$ and the cache tag can store $\lfloor q/2\rfloor$ using the floor function.

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.

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 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 repeated cache block access that misses even in the comparison fully associative cache of the same capacity and cache line size using LRU replacement. In the memory cache example these are reads 6, 7 and 11. The replacement assumption matters to this classification.

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.

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.

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 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]

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.

The time from a memory reference's request until the requested data become available. Average memory access time averages this delay in the stated serial model; it does not directly measure whole-program runtime.

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]