A comprehensive glossary can also be found at http://www.memorymanagement.org.
ABA problem the inability of certain atomic operations to distinguish reading the same value twice from a memory location as ‘nothing changed’ versus some other thread changing the value after the first read and then changing it back before the second read.
accurate see type-accurate.
activation record a record that saves the state of computation and the return address of a method, sometimes called a frame.
address conventionally, a fixed-length unsigned integer representing the location of a datum in memory.
address space a set of addresses, physical or virtual, available to the program.
age-based collection a collection technique that partitions the heap into spaces by age.
aging space a subspace of a generation, typically the youngest generation, into which objects are copied for a few collections before promoting them.
alignment hardware or virtual machine constraints may require that objects and fields be stored only on certain address boundaries.
allocation the action of allocating a free cell.
allocator the memory manager component responsible for creating objects (but not initialising them).
ambiguous pointer a value that may or may not be a true pointer to an object; see conservative collection.
ambiguous root a root that is an ambiguous pointer.
arbitrary compaction a compaction technique that moves objects without regard for their original order in memory or any reference relationship; see compaction order.
arraylet a fixed-size chunk representing some subset of the cells of an array.
atomic a primitive operation that appears to execute indivisibly and instantaneously with respect to other primitive operations.
barrier (read or write) an action (typically a sequence of code emitted by the compiler) mediating access to an object; see also read barrier, write barrier, stack barrier.
belt a set of increments used by the Beltway collector.
best-fit allocation a free-list allocation strategy that places an object in the cell in the heap that most closely matches the object’s size.
big bag of pages allocation (BiBoP) a segregated-fits allocation strategy that places objects with the same attribute (such as type) in the same block, thus allowing the type to be associated with the block rather than with individual objects.
bitmap an array of bits (or often, bytes), each associated with an object or granule.
bitmapped-fits allocation a sequential fits allocation strategy that uses a bitmap to record the free granules in the heap.
black an object is black if the collector has finished processing it and considers it to be live; see also tricolour abstraction.
black-listing an address range that has been found to be a target of a false pointer may be blacklisted in conservative collection to prevent space leaks.
block an aligned chunk of a particular size, usually a power of two.
block structured heap a heap comprised of a set of contiguous blocks of memory, rather than a single contiguous range of addresses.
block-based allocation see big bag of pages allocation.
boundary tag structures on the boundaries of blocks that assist coalescing.
bounded mutator utilisation (BMU) the minimum mutator utilisation observed for a given time window or any larger one; BMU is monotonically increasing, unlike MMU.
breadth-first traversal a traversal of the object graph in which an object’s siblings are visited before its descendants (referents).
bucket a subspace used to segregate objects by age within a step.
bucket brigade an approach to generational collection using buckets.
buddy system a segregated-fits allocation strategy that allocates blocks, typically in power of two sizes to allow easy splitting and coalescing; see also Fibonacci buddy system.
buffered reference counting a form of reference counting in which mutators buffer reference counting operations and subsequently send them for execution to the collector.
bump pointer allocation see sequential allocation.
byte map see bitmap.
cache a fast memory which stores copies of data from frequently used memory locations.
cache block see cache line.
cache coherence the degree to which two or more caches agree on the contents of memory.
cache hit a memory access that finds its containing cache line in the cache.
cache line the unit of memory that can be transferred between the cache and memory.
cache miss a memory access that does not find its containing cache line in the cache.
call stack a stack holding the stack frames of the methods being executed by a thread.
car the unit of collection in the Mature Object Space (‘Train’) collector.
car (in Lisp) the word in a cons cell that holds or points to the list element.
card a small, power of two sized and aligned, area of the heap.
card marking a technique used by the mutator to record the source of pointers of interest to the collector; the write barrier updates a card table.
causal consistency a consistency model in which a prior read is ordered before any write that may store the value obtained by the read, and a prior write is ordered before any read that may load the value stored by the write.
cdr (in Lisp) the word in a cons cell that holds or points to the next cons cell in the list.
cell a contiguous group of granules, which may be allocated or free, or even wasted or unusable.
channel a single-reader, single-writer communication mechanism; for example, between two threads.
Cheney scanning a technique used with copying collection for tracing live objects without use of a stack.
chip multiprocessor (CMP) a multiprocessor that has more than one processor on a single integrated circuit chip; see also multicore processor and many-core processor.
chunk a large contiguous group of granules.
circular first-fit allocation see next-fit allocation.
coalesced reference counting a form of buffered reference counting that avoids applying redundant reference count operations.
coalescing recombining adjacent cells into a single cell; see also segregated-fits allocation.
coherence protocol a cache management protocol for maintaining some memory consistency model.
collection a single instantiation of a collector; typically this instantiation would reclaim at least all objects in the space being collected that were dead at the time that the collector was called.
collection cycle a complete execution of the collector.
collector a system component responsible for garbage collection.
compacting relocating marked (live) objects and updating the pointer values of all live references to objects that have moved so as to eliminate external fragmentation.
compaction see compacting.
compaction order the order in which a compacting collector rearranges objects; this may be arbitrary, linearising or sliding.
compare-and-set an atomic instruction that compares a memory location to an expected value “old”, and if the location’s value equals “old”, sets the value to “new”. In either case it indicates whether or not it updated the memory location.
compare-and-swap as compare-and-set but returns the value of the memory location observed before any update, rather than returning a boolean truth value.
completeness the property of a collector that guarantees to reclaim all garbage eventually; for example reference counting is not complete because it cannot reclaim cycles of dead objects.
concurrent collection execution of the garbage collector concurrently with execution of mutator threads.
condemned space the space or subspace chosen to be collected.
connectivity-based (garbage) collection (CBGC) a collection technique that partitions the heap into spaces based on connectivity.
cons cell a double-word cell used by Lisp for storing the spine of a list.
conservative collection a technique for collection that receives no assistance from a language’s compiler or run-time system and so must make over-estimates of the set of live objects.
consistency model a specification of how the memory system will appear to the programmer, placing restrictions on the values that can be returned by a read in a shared-memory program execution.
copy reserve a space reserved as a target for copying in copying collection.
copying see evacuating.
copying collection collection that evacuates live objects from one semispace to another (after which, the space occupied by the former can be reclaimed).
creation space see nursery.
crossing map a map that decodes how objects span areas (typically cards).
cyclic data structure a self-referential data structure.
dangling pointer a pointer to an object that has been reclaimed by the memory manager.
dead an object is dead if it cannot be accessed at any time in the future execution of the mutator.
deallocation the action of freeing an allocated cell.
deferred reference counting a reference counting scheme in which some reference count operations (typically those on local variables) are deferred to a later time.
deletion barrier a write barrier that detects the removal of a reference; see also snapshot-at-the-beginning.
dependent load a load from a memory location whose address depends on the result of a prior load.
depth-first traversal a traversal of the object graph in which an object’s descendants are visited before its siblings.
derived pointer a pointer obtained by adding an offset to an object reference.
direct collection a collection algorithm that determines whether an object is live simply from that object itself, in contrast to indirect collection.
double mapping a technique that maps the same page at two different addresses with different protections.
double-ended queue (deque) a data structure allowing adding to and removing from the front (head) and back (tail).
eager reference counting an eager reference counting memory manager applies reference count increments and decrements immediately, rather than deferring them; see also buffered reference counting, coalesced reference counting, deferred reference counting, lazy reference counting.
eager sweeping sweeping immediately as opposed to lazy sweeping.
eden see nursery.
en masse promotion generational collection scheme in which all survivors of a minor collection are promoted.
epoch a period of execution of a reference counting collector during which synchronised operations can be eliminated or replaced by unsynchronised operations.
escape analysis an analysis (usually static) that determines whether an object may become reachable from outside the method or thread that created it.
evacuating moving an object from a condemned space to its new location (in to-space); see copying collection or mark-compact collection.
explicit deallocation the action of deallocation under the control of the programmer, rather than automatically.
external fragmentation space wasted outside any cell; see also internal fragmentation.
false pointer a value that was falsely assumed to be a pointer to an object; see conservative collection.
false sharing the coincidence of different processors different accessing memory locations that happen to lie in the same cache line, resulting in increased cache coherence traffic.
fast (slow) path Most memory managers take care to optimise the common case (fast path) for allocation or barriers. The fast path is typically inline code with the less common case (slow path) handled in a procedure call.
fast-fits allocation a sequential fits allocation strategy that uses an index to search for the first or next cell that satisfies the allocation request.
fat pointer a pointer that also holds additional metadata; for example, a version number.
Fibonacci buddy system a buddy system in which the size classes form a Fibonacci sequence.
field a component of an object holding a reference or scalar value.
filler object an object allocated in the gaps between real objects to support heap parsability.
finalisation an action performed on an object when it is determined to be no longer reachable.
finaliser a method that runs when the collector determines that the object is no longer reachable.
first-fit allocation a free-list allocation strategy that places an object in the first cell in the heap that can contain the object.
first-in, first-out (FIFO) see queue.
flip the swapping of fromspace and to-space in copying collection at the start of a collection cycle.
floating garbage garbage that was not reclaimed in a previous collection cycle.
footprint (memory) the volume of memory that a program uses while running.
forward cause mutator to refer to the to-space copy of an object; insert a forwarding address.
forwarding address the address to which an object has been evacuated (typically stored in the fromspace object’s header).
fragmentation the inability to use free memory because of the arrangement of objects; see also internal fragmentation and external fragmentation.
frame a power of two sized and aligned chunk; typically a discontiguous space comprises a number of frames; however, see also activation record.
free the state of a cell that is available for reallocation; see also reclaim.
free pointer a pointer to the free granules of a chunk; see sequential allocation.
free-list allocation a sequential fits allocation strategy that uses a data structure to record the location and size of free cells.
fromspace the semispace from which copying collection copies objects.
fromspace invariant the invariant that the mutator holds only fromspace references.
garbage an object that is not live but whose space has not been reclaimed.
garbage collection (GC) an automatic approach to memory management that reclaims memory occupied by objects that are no longer in use by the program (mutator).
garbage collector see collector.
GC-check point a point in mutator code that may trigger collection, such as an allocation site; every GC-check point must be a GC-safe point, but not necessarily vice versa.
GC-point a point in the mutator code at which it is safe for garbage collection to occur; a GC-point might or might not actually trigger garbage collection.
GC-safe point see GC-point.
generation a space characterised by the age of the objects it contains.
generational collection collection that segregates objects by age into generations and preferentially collects the youngest generation.
generational hypothesis the hypothesis that object lifetime is correlated with age; see also weak generational hypothesis and strong generational hypothesis.
gibibyte (GiB) standard usage unit meaning 230 bytes; see also gigabyte.
gigabyte (GB) common usage unit meaning 230 bytes; see also gibibyte.
granule the smallest unit of allocation, say a word or a double-word.
grey an object is grey if the collector has not yet finished processing it; see also tricolour abstraction.
grey packet a unit of collector work used for load balancing; a packet contains a fixed number of grey objects for a collector to process. See also tricolour abstraction.
guard page a page mapped with no-access protection so as to cause a trap when accessing beyond an allowed limit, thus avoiding the need for an explicit range limit check.
handle a structure holding a reference to an object, and optionally additional status information; typically, a handle is not moved by the collector whereas its target object might be.
handshake a protocol for mutaor and collector threads to rendezvous at garbage collection phase boundaries.
happens-before a requirement on the order in which operations occur on memory.
hard real-time system a real-time system in which all deadlines must be met within a strict bound; missing a deadline is a critical system failure.
header a part of an object used to store metadata used by the run-time system.
headroom additional space for allocation required to avoid thrashing tracing collectors.
heap a data structure in which objects may be allocated or deallocated in any order, independent of the lifetime of the method that created them.
heap allocation allocation of an object in the heap.
heap parsability the capability to advance through the heap from one object to the next.
heaplet a subset of the heap containing objects accessible to only a single thread.
hyperthreading see simultaneous multithreading.
increment a unit of collection in the Beltway collector; however, see also incremental collection.
incremental collection collection in which the mutator performs small quanta of collection work; see also concurrent collection.
incremental update a technique for solving the lost object problem that informs the collector of incremental changes made by the mutator to the set of objects known to be live.
incremental update barrier see insertion barrier.
indirect collection a collection algorithm that does not detect garbage per se, but rather identifies all live objects and then concludes that anything else must be garbage.
insertion barrier a write barrier that detects the insertion of a reference; see also incremental update.
interior pointer a derived pointer to an internal object field.
internal fragmentation space wasted inside a cell, for example due to rounding up requested sizes; see also external fragmentation.
JVM a virtual machine for the Java language.
kibibyte (KiB) standard usage unit meaning 210 bytes; see also kilobyte.
kilobyte (KB) common usage unit meaning 210 bytes; see also kibibyte.
large object space (LOS) a space reserved for objects larger than a given threshold, and typically managed by a non-moving collector.
last-in, first-out (LIFO) see stack.
lazy reference counting deferring freeing of zero-count objects when reference counting until they are subsequently acquired by the allocator, at which point their children can be processed.
lazy sweeping sweeping only on demand (when fresh space is required).
leak see memory leak.
limit pointer a pointer to the end of a chunk; see sequential allocation.
linear allocation see sequential allocation.
linearisable an execution history of concurrent operations that appear to execute serially in some non-overlapped way, where if two operations do not overlap in the history then they must appear to happen in the order they were invoked.
linearisation point the point in time at which an operation in a linearisable history appears instantaneously to occur.
linearising compaction a compaction technique that attempts to place objects next to those that they reference; see compaction order.
live an object is live if it could be accessed at some time in the future execution of the mutator.
livelock a situation in which two (or more) competing threads prevent progress of the other(s) indefinitely.
liveness (of collector) the property of a (concurrent) collector that it eventually completes its collection cycle.
liveness (of object) the property of an object that it will be accessed at some time in the future execution of the mutator.
load-linked/store-conditionally atomic instruction pair that first reserves a location and then updates it only if the processor’s coherence mechanism confirms that its value has not been changed since the reservation was made.
local allocation buffer (LAB) a chunk of memory used for allocation by a single thread.
locality the degree to which to items (fields, objects) are accessed together in space or time; see also spatial locality and temporal locality.
location an addressable unit of memory, having a unique address.
lock a synchronisation mechanism for controlling access to a resource by multiple concurrent threads; usually only one thread at a time can hold the lock, while all other threads must wait.
lock-free a guarantee of system-wide progress, although individual threads may fail to make progress; implies obstruction-free; see also non-blocking.
lost object problem a situation that can arise when interleaved execution results in the mutator’s hiding references from the collector so that the collector erroneously reclaims live objects.
major collection collection of both the old generation and young generation; see also generational collection.
malloc a function in the C standard library that allocates memory in the heap.
managed code application code running on a managed run-time.
managed run-time a run-time system that provides services such as automatic memory management.
many-core processor a multiprocessor that has a large number of processors on a single integrated circuit chip; sometimes distinguished from a multicore processor in that the cores of a many-core processor are smaller and simpler.
mark bit a bit (stored in the object’s header or on the side in a mark bitmap) recording whether an object is live.
mark stack (or queue) a stack (or queue) used as the work list for the marking process.
mark-compact collection a tracing collection that typically operates in three or more phases, first marking all live objects and then compacting these objects to eliminate fragmentation.
mark-sweep collection a tracing collection that typically operates in two phases, first marking all live objects and then sweeping through the heap, reclaiming the storage of all unmarked, and hence dead, objects.
mark/cons ratio a common garbage collection metric that compares the amount of work done by the collector (‘marking’) with the amount of allocation (‘consing’) done; see cons cell.
marking recording that an object is live, often by setting a mark bit.
mature object space (MOS) a space reserved for older (mature) objects managed without respect to their age.
mebibyte (MiB) standard usage unit meaning 220 bytes; see also megabyte.
megabyte (MB) common usage unit meaning 220 bytes; see also mebibyte.
memory fence an operation on a processor that prevents certain reorderings of memory accesses.
memory leak a failure to reclaim memory that is no longer in use by the program.
memory manager component responsible for allocating and reclaiming memory.
memory order the order of writes (and reads) to multiple memory locations at caches or memories, and thus as perceived by other processors; see also program order.
metadata data used by the virtual machine or memory manager but not part of the running application.
minimum mutator utilisation (MMU) the minimum mutator utilisation for a given time window.
minor collection collection of only the young generation or nursery; see also generational collection.
mmap a Unix system call that creates a mapping for a range of virtual addresses.
mostly-concurrent collection a technique for concurrent collection that may pause all mutator threads briefly.
mostly-copying collection a technique for copying collection that copies most objects but does not move others (because of pinning).
moving collection any collection technique that moves objects.
multi-tasking virtual machine (MVM) a virtual machine that runs several applications (tasks) within a single invocation of the virtual machine.
multicore processor see chip multiprocessor and many-core processor.
multiprocessor a computer that provides more than one processor.
multiprogramming the execution of multiple processes or threads on a single processor.
multitasking the execution of multiple tasks on a single processor.
multithreading the execution of multiple threads on one or more processors.
mutator the user program, so called because from the collector’s point of view it simply mutates the graph of objects.
mutator utilisation the fraction of CPU time used by the mutator, as opposed to the collector.
nepotism the situation where a dead object in an uncollected space preserves an otherwise dead object in the condemned space.
newspace the space in which objects are allocated.
next-fit allocation a free-list allocation strategy that places an object in the next cell in the heap that can contain the object.
node see object.
non-blocking a guarantee that threads competing for a shared resource do not have their execution delayed indefinitely; see also obstruction-free, lock-free, wait-free.
non-uniform memory access (NUMA) a multiprocessor in which a shared memory unit is associated with each processor, giving that processor faster access to that memory unit.
Not-Marked-Through (NMT) a state of a reference indicating that it has not been traced through by the Pauseless collector to assure that its target object has been marked.
null a distinguished reference value that does not refer to any object.
nursery a space in which objects are created, typically by a generational collector.
object a cell allocated for use by the application.
object inlining an optimisation technique that replaces a reference to a unique object with that object’s fields; see also scalar replacement.
object table a table of handles, which refer to objects.
oblet a fixed-size chunk representing some subset of the cells of an object.
obstruction-free a guarantee that at any point, a single thread executed in isolation (that is, with all obstructing threads suspended) will complete its operation within a bounded number of steps; see also non-blocking.
old generation a space into which objects are promoted or tenured.
on-stack replacement a technique for replacing a method’s code with new code while it still has active invocations.
on-the-fly collection a technique for concurrent collection that stops mutator threads at most one at a time.
padding extra space inserted by the allocator to meet alignment constraints.
page a block of virtual memory.
parallel collection use of multiple processors or threads to perform collection; not to be confused with concurrent collection.
partial tracing tracing only a subset of the graph of objects; typically used to refer to a trial deletion algorithm that traces a sub-graph that is suspected of being garbage.
pause time the time during which mutators are halted while stop-the-world collection runs.
phantom reference in Java, the weakest kind of reference; phantom references are typically used for scheduling cleanup actions more flexibly than is possible with finalisation.
pinning preventing a collector from moving a particular object (typically because it is accessible to code that is not collector-aware).
pointer the address in memory of an object.
pointer field a field that contains a pointer to another object.
prefetching fetching a value into the cache earlier than it would naturally be fetched.
prefetching on grey fetching the first cache line of an object when that object is marked grey.
pretenuring allocating an object directly into an old generation.
primitive (instruction) an instruction directly executable by a hardware processor.
process an instance of a computer program that is executing within its own address space; a process may comprise multiple threads executing concurrently.
processor (CPU) a unit of hardware that executes (primitive) machine instructions.
program order the order of writes (and reads) to multiple memory locations as they appear in the program; see also memory order.
prolific type an object type having many instantiations.
promote move an object into an old generation.
promptness the degree to which a collector reclaims all garbage at each collection cycle.
queue a first-in, first-out data structure, allowing adding to the back (tail) and removing from the front (head).
raw pointer a plain pointer (in contrast to a smart pointer).
reachable the property of an object that it can be accessed by following a chain of references from a set of mutator roots.
read barrier a barrier on reference loads by the mutator.
real-time (garbage) collection (RTGC) a technique for concurrent collection or incremental collection supporting a realtime system.
real-time system a hardware or software system that is subject to deadlines from event to system response.
reclaim return storage occupied by an object to the memory manager for reuse.
recursion if this is not clear, see recursion.
reference the canonical pointer used to identify an object.
reference count a count of the number of references that point to an object, typically stored in the object’s header.
reference counting a collection scheme that manages objects by maintaining a count of the number of references to each object.
reference listing a collection scheme that manages objects by maintaining a list of references to each object.
region a space visible to and managed by the programmer or (typically inferred automatically by the) compiler; a region can typically be made free in constant time.
region inferencing a static analysis that determines the region into which to place an object in a region-based memory management scheme.
relaxed consistency any consistency model that is weaker than sequential consistency.
release consistency a consistency model in which acquire operations prevent later accesses from occurring before the acquire, but earlier accesses can happen after the acquire;release operations prevent earlier accesses from happening after the release but later accesses can happen before the release.
remembered set (remset) a set of objects or fields that the collector must process; typically, mutators supported by generational collection, or concurrent collection or incremental collection, add entries to the remembered set as they create or delete pointers of interest to the collector.
remset see remembered set.
rendezvous barrier a code point at which each thread waits until all other threads have reached that point.
replica (in a copying collector) the copy in tospace of a fromspace object.
replicating collection a technique for concurrent copying collection in which two (or more) copies of live objects are maintained.
restricted deque a double-ended queue where the action of adding or removing is allowed at only one end of the queue.
resurrection an action performed by a finaliser that causes the previously unreachable object to become reachable.
root a reference that is directly accessible to the mutator without going through other objects.
root object an object in the heap referred to directly by a root.
run-time system the code that supports the execution of a program, providing services such as memory management and thread scheduling.
safety the property of a collector that it never reclaims a live object.
scalar a non-reference value.
scalar field a field that contains a scalar value.
scalar replacement an optimisation technique that replaces a reference to a unique object with local variables representing its fields; see also object inlining.
scan pointer a pointer to the next location to be scanned; typically used in Cheney scanning.
scanning processing each pointer field of an object.
scavenging picking out live objects from the fromspace, typically leaving forwarding addresses behind; see copying collection.
schedulability analysis the analysis of a set of real-time tasks to decide whether they can be scheduled so that none of them misses a deadline.
scheduler an operating system component that chooses which threads to execute on which processors at any given time.
scheduling choosing when to execute a unit of collection.
segregated-fits allocation an allocation strategy that partitions the heap by size class in order to minimise fragmentation.
semispace one of two spaces into which a copying collection divides the heap.
semispace copying see copying collection.
sequential allocation an allocation strategy that allocates objects consecutively from one end of a free chunk; often called bump pointer allocation or linear allocation.
sequential consistency a consistency model in which all memory operations appear to execute one at a time, and the operations of each processor appear to execute in its program order.
sequential fits allocation a free-list allocation strategy that searches the free-list sequentially for a cell that satisfies the allocation request.
sequential store buffer (SSB) an efficient implementation of a remembered set, such as a chain of blocks of slots.
shade to colour a white object grey; see tricolour abstraction.
shared pointer a form of smart pointer defined for C++ based on reference counting.
simultaneous multithreading (SMT) the capability of a processor to execute multiple independent threads at the same time.
size class a logical set of objects that are managed by the same allocation and collection policies and whose size falls within a specific range; the amount allocated is generally rounded up to the largest size in the class.
slack-based scheduling a technique for scheduling real-time collection that performs collector work when no real-time task is running.
sliding compaction a compaction technique that preserves the order in memory of live objects; see compaction order.
slot see field.
smart pointer a form of pointer upon which operations such as copying or dereferencing are overloaded in order to perform memory management operations.
snapshot barrier see deletion barrier.
snapshot-at-the-beginning a technique for solving the lost object problem that preserves the set of objects live at the start of the collection cycle.
soft real-time system a real-time system (controversially) in which most deadlines must be met within strict bounds to preserve quality of service; completion of an operation after its deadline results in degraded service.
soft reference in Java, a reference that is stronger than a weak reference but not as strong as a strong reference; soft references are typically used to build caches that the garbage collector can reclaim when it comes under memory pressure.
space a subset of the heap managed by a particular collection policy.
space utilisation the fraction of heap space usable for mutators’ data; that is, excluding garbage collector metadata, other semispaces, and so on.
spatial locality the degree to which two items (fields, objects) are likely to be allocated close to each other (for example, on the same page or cache line).
spin lock a lock where the waiting threads simply ‘spin’ in a loop until they can acquire the lock.
splitting dividing a cell into two adjacent cells; see also segregated-fits allocation.
stack a last-in, first-out data structure, allowing adding and removing only from the front (top); see also call stack.
stack allocation allocation of an object in the stack frame of its allocating method.
stack barrier a barrier on returning (or throwing an exception) beyond a given stack frame in a thread’s call stack.
stack frame an activation record allocated in the call stack.
stack map a data structure indicating which addresses the collector should consider to be references to objects in a call stack.
static allocation allocation of an object at an address known at compile time.
step a subspace used to segregate objects by age within a generation.
sticky reference count a reference count that has been incremented to the maximum permissible value, not changed by subsequent pointer updates.
stop-the-world collection a technique for collection during which all mutator threads are halted.
store buffer see write buffer; not to be confused with a sequential store buffer.
strict consistency a consistency model in which every memory access and atomic operation appears to occur in the same order everywhere.
strong generational hypothesis the hypothesis that the older an object is, the less likely it is to die.
strong reference a reference to an object that contributes to its reachability; normal references are usually strong.
strong tricolour invariant a tricolour abstraction invariant that no black object ever refers to a white object.
survivor an object that is live at the time of a collection and thus not reclaimed.
sweeping reclaiming unmarked (dead) objects in a linear pass through (a subset) of the heap.
symmetric multiprocessor (SMP) a multiprocessor with identical separate processors and shared, possibly non-uniform memory access, memory.
synthetic benchmark an artificially constructed benchmark intended only to evaluate a system. Although the behaviour of synthetic benchmarks may be stochastic, such benchmarks may not reproduce the interactions exhibited by real programs, or may have working sets too small to exhibit their locality effects.
task a unit of work performed by a process or thread, usually in a real-time system.
tebibyte (TiB) standard usage unit meaning 240 bytes; see also terabyte.
temporal locality the degree to which two items (fields, objects) are likely to be accessed close to each other in time.
tenuring see promote.
terabyte (TB) common usage unit meaning 240 bytes; see also tebibyte.
test-and-set an atomic instruction that sets that value of a location only if it was not set. In either case, it returns the old value.
test-and-set lock see spin lock.
test-and-test-and-set lock a lower-overhead variant of a test-and-set lock that uses (expensive) atomic hardware primitives only when the lock appears to be free.
thrash overly frequent collections (or paging), at the expense of mutator activity.
thread the smallest unit of processing that can be scheduled for execution by an operating system; multiple threads may execute in the same address space. See also process.
thread-local collection garbage collection of only those objects accessible to a single thread.
threaded compaction a technique for compacting that links objects so that all those originally pointing to a given object can be discovered from that object.
throughput the rate at which data is processed by the mutator(s) (alternatively, by the collector(s)).
tidy pointer the canonical pointer used as an object’s reference.
time-based scheduling a technique for scheduling real-time collection that reserves a pre-defined portion of execution time solely for collector work during which the mutator is stopped.
tospace the semispace to which copying collection evacuates live objects.
tospace invariant the invariant that the mutator holds only tospace references.
tracing visiting the reachable objects by traversing all or part of an object graph.
tracing collection a technique for indirect collection that operates by tracing the graph of live objects.
train a component of the Mature Object Space (‘Train’) collector.
transaction a collection of reads and writes that must appear to execute atomically.
transaction abort the unsuccessful termination of a transaction which discards its effects.
transaction commit the successful completion of a transaction which ensures that its effects are made visible.
transactional memory a mechanism analogous to database transactions for controlling concurrent access to shared memory; it may be implemented in hardware or software.
transitive (referential) closure given a set of objects, fields or other locations (roots), the transitive referential closure of the set of roots is the set of objects that can be reached from those roots by following references.
translation lookaside buffer (TLB) a small associative memory that caches part of the translation between virtual and physical addresses.
traversal visiting each node in a graph exactly once.
trial deletion the temporary deletion of a reference in order to discover whether this causes an object’s reference count to drop to zero.
tricolour abstraction a characterisation of the work of the garbage collector as partitioning objects into white (not yet visited) and black (need not be revisited), using grey to represent the remaining work (to be revisited).
type-accurate a property of a garbage collector that it can precisely identify every slot or root that contains a pointer.
type-safe In the context of this book, a programming language is type-safe if it cannot manufacture a reference value from a non-reference type.
ulterior reference counting a reference counting scheme that manages young objects by copying and older ones by reference counting.
unique pointer a smart pointer that retains sole ownership of an object through a pointer and destroys the object when the unique pointer goes out of scope; two different unique pointers cannot manage the same object.
virtual machine (VM) a run-time system that abstracts away details of the underlying hardware or operating system.
wait-free a guarantee of both system-wide (lock-free) and per-thread progress so that a thread will complete its operation in a bounded number of steps; see also non-blocking.
wavefront the boundary, comprising grey objects (still to be processed), separating black objects (already processed) from white objects (not yet processed).
weak consistency a consistency model which treats each atomic operation as a total memory fence.
weak generational hypothesis the hypothesis that most objects die young.
weak reference a reference to an object that does not contribute to its reachability. Java for example provides several flavours of weak reference (see soft reference and phantom reference).
weak tricolour invariant a tricolour abstraction invariant that any white object pointed to by a black object must also be reachable from some grey object either directly or through a chain of white objects.
white an object is white if the collector has not processed it; at the end of a collection cycle, white objects are considered dead. See also tricolour abstraction.
wilderness the last free chunk in the heap.
wilderness preservation a policy of allocating from the wilderness only as a last resort.
work stealing a technique for balancing work among threads where lightly loaded threads pull work from more heavily loaded threads.
work-based scheduling a technique for scheduling real-time collection that imposes collector work as a tax on units of mutator work.
worst-case execution time (WCET) the maximum time an operation can take on a specific hardware platform; knowing worst-case execution times is necessary for schedulability analysis of a hard realtime system.
write barrier a barrier on reference stores by the mutator.
write buffer a buffer that holds pending writes to memory, also called a store buffer (not to be confused with a sequential store buffer).
young generation see nursery.
zero count table (ZCT) a table of objects whose reference counts are zero.