The Memory Management Glossary
A-Z

 Contents | News | Glossary | FAQ | Articles | Bibliography | Links | Feedback

This is the entire Memory Management Glossary as one document and is designed to be suitable for printing; for online use, it is usually easier to access the glossary divided by letter. In this version, references to other entries are indicated «like this», and URLs are specified explicitly <URL:like this>.

Our aim is for these entries to be accurate, comprehensible, and useful, and also to have an entry for all common memory management terms. If you can't find the term you're looking for, if our definition doesn't help you, or if you'd like to suggest corrections or additions, please let us know via our feedback page.

For an explanation of the structure of the entries, and information on how to link to definitions, please see the glossary help page.


A

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

absolute address (for full details, see «physical address»)

Physical «addresses» are used to index into «physical memory(1)». On some systems, they are called absolute addresses.

activation frame (for full details, see «activation record»)

An activation or function record is a data structure, associated with the invocation of a function, procedure or control block that stores the variables, temporaries and fixed-sized data local to the block, and the information required to return to the invoking context. It is often stored on a «stack».

activation record (also known as function record, activation frame)

An activation or function record is a data structure, associated with the invocation of a function, procedure or control block that stores the variables, temporaries and fixed-sized data local to the block, and the information required to return to the invoking context. It is often stored on a «stack».

In a register-based hardware architecture, the current activation record is typically partially stored in registers.

«Closures» and «continuations» are specializations of activation records in support of particular language features of LISP, Scheme and related languages.

Relevance to memory management: The current activation record is part of the state of the «mutator», and is therefore a «root» to the «collector(2)». In languages that permit recursion, activation records have «dynamic extent». In languages that permit closures or continuations, activation records may have «indefinite extent». Although they may not be visible to the programmer, their «storage» must be managed by the language run-time support. Because they are usually not visible to the programmer, they may be a source of inexplicable memory overhead.

See also: «stack frame».

activation stack (for full details, see «control stack»)

A «stack» that stores «activation records», particularly subroutine return information, is known as a control stack.

active (for full details, see «live»)

«Memory(2)» or an «object» is live if the program will read from it in future. The term is often used more broadly to mean «reachable».

address

An address is a specification of a «location» in an «address space».

An address is almost always represented as an unsigned integer stored in a single «machine word». The address is decoded by the hardware in order to access a location on a «physical memory(2)» device (such as a «RAM») or some «memory-mapped» resource.

A simplified view of addresses, address space, and locations on a 32-bit architecture
Diagram: A simplified view of addresses, address space, and locations on a 32-bit architecture

Similar terms: «pointer».

address space

An address space is the set of possible «addresses». It can also be considered to be a partial function from addresses to «locations».

Typically, addresses start at zero and run to 2^N-1, where N is the address width (for example, 15, 16, 24, 32, 64), which is usually the same as the width of the address bus. This may not be true for «segmented» architectures.

In modern systems, large parts of the whole address space may be reserved by the operating system or architecture, or not «mapped» at any given time. The mapped part of the address space may be discontiguous or sparse.

See also: «virtual address space»; «physical address space».

address translation cache (for full details, see «TLB»)

The translation lookaside buffer or address translation cache is small piece of associative «memory(1)» within a processor which caches part of the translation from «virtual addresses» to «physical addresses».

address-ordered first fit

The «allocation policy» that always uses the suitable «free block» with the lowest address. One of the most common allocation policies in use. Commonly implemented by «first fit» on a single address-ordered «free block chain». Sometimes just called "first fit".

See also: «first fit»; «LIFO-ordered first fit»; «address-ordered first fit».

Related publications:


aging space

In some «generational garbage collection» systems, when «generations» are divided into «buckets», the aging space is where «objects» which survive a «collection» stay until they are old enough to be «promoted».

Opposites: «creation space».

algebraic data type

Algebraic data types aggregate or alternate a number of dissimilarly-typed objects. They are termed algebraic because they can be expressed as a sum-of-products: (a and b and c) or d.

Examples of algebraic data types include: structures, records, tuples, and unions.

Relevance to memory management: Algebraic data types are usually represented using a «heap». Because of their non-uniformity, algebraic data types are more difficult to «scan».

See also: «scalar data type»; «vector data type»; «heap».

alignment

Alignment is a constraint on the «address» of an «object» in «memory(2)».

The constraint is usually that the object's address must be a multiple of a power of two, 2^N, and therefore that the least significant N bits of the address must be zero.

The bus hardware of many modern processors cannot access multi-«byte(2)» objects at any memory address. Often «word»-sized objects must be aligned to word boundaries, double-words to double-word boundaries, double-floats to 8-byte boundaries, and so on. If a program attempts to access an object that is incorrectly aligned, a «bus error» occurs.

Relevance to memory management: A memory manager must take care to «allocate» memory with an appropriate alignment for the object that is going to be stored there. Implementations of «malloc» have to allocate all «blocks» at the largest alignment that the processor architecture requires.

Other reasons for aligning objects include using the least significant bits of the address for a «tag».

Opposites: «unaligned».
See also: «natural alignment».

alive (for full details, see «live»)

«Memory(2)» or an «object» is live if the program will read from it in future. The term is often used more broadly to mean «reachable».

allocate (also known as cons(2))

Allocation is the process of assigning resources. When requested to by the program, an application «memory manager» or «allocator» allocates a «block» of «memory(2)» for the program to store its data in. Allocation is also known as consing, from «cons(1)».

When faced with a request for memory from the program, a memory manager must choose a suitable block and hand it over, or fail. The choices made by the memory manager at this point can have a significant effect on the future efficiency of the program.

Allocation is rarely a simple issue. For example, programs usually allocate «activation records» («automatic variables», and so on) for functions from a processor «stack» simply by subtracting a number from their stack «pointer». However, in a «virtual memory(1)» system, this may extend the stack onto a previously unused «page», in which case the operating system memory manager must carry out some quite complex operations in order to supply the program with «backing store» for the stack so that the program can continue.

Historical note: The term reserved was often used to mean "allocated".

Similar terms: «malloc».
Opposites: «free(1)».
See also: «constructor(1)».

Related publications:


allocation mechanism

The algorithm by which an «allocator» chooses a «free block» from which to satisfy an allocation request. An allocation mechanism is the implementation of an «allocation policy».

A common mechanism is "«first fit» on an address-ordered «free block chain», with eager «coalescing»". This implements the «address-ordered first fit» policy, and commonly inherits that name, although there are many other mechanisms for implementing that policy (e.g. "leftmost fit on a balanced tree of free blocks ordered by address").

Related publications:


allocation policy (also known as placement policy)

The concrete policy used by an «allocator» for choosing a «free block» to satisfy an «allocation» request.

For instance, "always allocate from the largest free block" («worst fit») or "use the most recently freed block suitable" («LIFO-ordered first fit»).

Each allocation policy is motivated by an «allocation strategy» and implemented by an «allocation mechanism».

See also: «address-ordered first fit»; «best fit».

Related publications:


allocation strategy

The high-level design motivation or strategy, of an «allocator», which uses observations or theories about patterns of allocation requests to justify an «allocation policy».

For instance, "do not allow small long-lived «objects» to fragment large «free(3)» areas", "allocate consecutive objects close together", and so on. The allocation strategy motivates an «allocation policy», which is implemented by an «allocation mechanism».

Related publications:


allocator

The term allocator is often used to refer to the «memory manager», usually when it is a simple manual one.

Similar terms: «memory manager».
See also: «allocation».

ambiguous reference (also known as unsure reference)

An ambiguous or unsure «reference» is a value that is potentially a reference, but the «collector(1)» cannot prove that it is.

The presence of ambiguous references in a «garbage-collected» system requires the use of «conservative garbage collection».

Opposites: «exact reference».
See also: «floating garbage».

ambiguous root

An ambiguous root is a «root» containing «ambiguous references».

Opposites: «exact root».
See also: «conservative garbage collection».

arena

The area of «memory(2)» used by «malloc» for allocation.

So named from a semi-mythical "malloc: corrupted arena" message supposedly emitted when some early versions became terminally confused.

See also: «brk».

ATC (for full details, see «TLB»)

The translation lookaside buffer or address translation cache is small piece of associative «memory(1)» within a processor which caches part of the translation from «virtual addresses» to «physical addresses».

atomic object (for full details, see «leaf object»)

A leaf object is an «object» that does not «reference» any other objects.

automatic memory management

Automatic «memory management» is a general term for techniques that automatically «recycle» unused «memory(2)».

It is not possible, in general, to automatically determine which «objects» are still «live». Even if it didn't depend on future input, there can be no general algorithm to prove that an object is live (cf. the Halting Problem). However, effective approximations are possible. In «tracing garbage collection», the approximation is that an object can't be live unless it is «reachable». In «reference counting», the approximation is that an object can't be live unless it is «referenced». Analysis of the program text can reveal where objects «die»; A notable technique in this vein is «region inference». Hybrid algorithms are also possible.

Similar terms: «garbage collection».
Opposites: «manual memory management».

automatic storage duration

In C, «objects» that are declared with automatic storage duration are «live» for the duration of a block of code.

In most implementations of C, objects with automatic storage duration are «allocated» on the «stack» when a function is entered, and «deallocated» when it returns.

Similar terms: «stack allocation»; «dynamic extent».
Opposites: «static storage duration».


B

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

backing store

Backing «store(2)» is typically part of a hard disk that is used by a «paging» or «swapping» system to store information not currently in «main memory». Backing store is slower and cheaper than main memory.

Other «storage» may, less commonly, be used in place of a hard disk (for instance, magnetic tape, floppy disk, or historically, magnetic drum).

In general, backing store may mean any locations used to store information when its preferred or natural location is otherwise being used -- for instance, memory used by a graphical interface to keep a copy of the contents of obscured windows.

Similar terms: «swap space».

barrier(1)

A barrier is a block on reading from or writing to certain «memory(2)» «locations» by certain threads or processes.

Barriers can be implemented in either software or hardware. Software barriers involve additional instructions around «load» or «store(1)» operations, which would typically be added by a cooperative compiler. Hardware barriers don't require compiler support, and may be implemented on common operating systems by using «memory protection».

Relevance to memory management: Barriers are used for «incremental» or «concurrent» «garbage collection».

See also: «read barrier»; «write barrier».

Related publications:


barrier(2)

A memory barrier is an instruction on certain processor architectures that will ensure certain guarantees about the order of accesses to memory.

Some processor architectures, such as the Alpha AXP, make very few guarantees about the relative orders of «load» and «store(1)» operations in the instruction stream and the actual order of accesses to «main memory». These architectures will often have special instructions that make stronger guarantees.

For example Alpha AXP has the MB instruction which will:

Guarantee that all subsequent loads or stores will not access memory until after all previous loads and stores have accessed memory, as observed by other processors.

These instructions are vital for certain synchronization operations.

base pointer

A base pointer is a «pointer» to the base or start of an «object».

This term is commonly used in opposition to «derived pointer».

Note that in A Proposal for Garbage-Collector-Safe C Compilation, Boehm and Chase define "base pointer" to be "any pointer value directly recognizable by the «collector(1)»", and this may well include «interior pointers».

Opposites: «derived pointer».

Related publications:


best fit

The «allocation policy» that always allocates from the smallest suitable «free block». Suitable «allocation mechanisms» include «sequential fit» searching for a «perfect fit», «first fit» on a size-ordered «free block chain», «segregated fits», and «indexed fits». Many «good fit» allocators are also described as «best fit».

In theory, best fit may exhibit bad «fragmentation», but in practice this is not commonly observed.

See also: «allocation policy»; «first fit»; «sequential fit».

Related publications:


BIBOP (also known as big bag of pages)

BIBOP, or BIg Bag Of Pages, is a technique that encodes «object» type in the high-order bits of their «address», by using a lookup table that maps from those bits to a type.

Despite the name, the blocks involved need not be the size of a «page».

BIBOP requires storing only objects of the same type in a block, but this has the same advantages as «segregated fits» in general.

Historical note: This technique was invented for the PDP-10 MACLISP by JonL White and Stavros Macrakis. It was an advance on earlier techniques that divided the «address space» into contiguous blocks for each type.

Related publications:


big bag of pages (for full details, see «BIBOP»)

BIBOP, or BIg Bag Of Pages, is a technique that encodes «object» type in the high-order bits of their «address», by using a lookup table that maps from those bits to a type.

binary buddies

The most common «buddy system» «allocation mechanism», in which all block sizes are a power of two. Finding a block's buddy is then a matter of flipping the appropriate bit in the block's address.

«Internal fragmentation» is usually high, because objects are often not a good fit for power-of-two sized blocks.

See also: «buddy system»; «allocation mechanism».

Related publications:


bit-table (for full details, see «bitmap»)

A table of bits.

bitmap (also known as bit-table)

A table of bits.

Relevance to memory management: Bitmaps are sometimes used to represent the marks in a «mark-sweep» collector, or the used memory in a «bitmapped fits» «allocator».

bitmapped fit

A class of «allocation mechanisms» that use a «bitmap» to represent the usage of the «heap». Each bit in the map corresponds to a part of the heap, typically a «word», and is set if that part is in use. Allocation is done by searching the bitmap for a run of clear bits.

Bitmapped fit mechanisms have good «locality», as they avoid examining «in-band headers» when allocating.

See also: «allocation mechanism»; «sequential fit»; «indexed fit».

Related publications:


black

In a «tri-color marking» scheme, black «objects» are objects that have been «scanned».

More precisely, black objects have been noted «reachable» and the «collector(2)» has finished with them and need not visit them again (for the purposes of «tracing»).

Opposites: «white»; «gray».

blacklisting, black-listing

A «conservative garbage collector» can be made more effective by blacklisting values which resemble «addresses» that may be «allocated» at in the future, but are known not to be «pointers» . This list is then used to avoid allocation at those addresses.

For example, such values can be gathered by scanning the «roots» before any «objects» have been allocated.

Related publications:


block

Block is a vague term for an (often contiguous) area of «memory(1)». Often used to describe «memory(2)» «allocated» by an «allocator» such as «malloc».

bounds error (for full details, see «overwriting error»)

An overwriting or bounds error occurs when the programmer intends his program to write to a particular «block» of «memory(1)», but a program error causes the program to write outside the bounds of that block.

boxed

Boxed «objects» are represented by a «pointer» to a «block» of «memory(2)» that contains the object data. Sometimes the pointer is «tagged» to distinguish it from an «unboxed» object, or to represent its type. Only the pointer is duplicated when the object is passed around, so updates to the object are reflected everywhere.

Opposites: «unboxed».
See also: «tag»; «BIBOP».

Related publications:


break-table

A break-table is a data structure used by a «mark-compact» collector to store the «relocation» information.

See also: «mark-compact».

brk

brk is a UNIX® system call that sets the limit of the data segment. This limit is known as the break.

The C library implementation of «malloc» usually «allocates» «memory(2)» for the «heap» by extending the data segment with brk or «sbrk».

Unfortunately, most implementations of malloc never shrink the data segment, so the memory usage of a process never decreases. In most UNIX systems, the data segment resides immediately above the program code (text segment) in the «address space».

A simplified view of the address space of a UNIX process
Diagram: A simplified view of the address space of a UNIX process

broken heart

«Copying garbage collectors» «move» «reachable» «objects» into another «semi-space». They leave a «forwarding pointer» in the old «location», pointing to the new. The object at the old location is known as a broken heart.

Similar terms: «forwarding pointer».

bucket

In a «generational garbage collector», it is often desirable to divide «generations» by the age of the «object». These divisions are known as buckets.

See also: «generational garbage collection»; «aging space»; «creation space».

buddy system

Buddy systems are a subclass of «strict segregated fit» «allocation mechanisms» which make «splitting» and «coalescing» fast by pairing each block with a unique adjacent buddy block.

There is an array of «free lists», one for each allowable block size. Allocation rounds up the requested size to an allowable size and allocates from the corresponding free list. If the free list is empty, a larger block is selected and split. A block may only be split into a pair of buddies.

A block may only be coalesced with its buddy, and this is only possible if the buddy has not been split into smaller blocks.

The advantage of buddy systems is that the buddy of a block being freed can be quickly found by a simple address computation. The disadvantage of buddy systems is that the restricted set of block sizes leads to high «internal fragmentation», as does the limited ability to coalesce.

Different sorts of buddy system are distinguished by the available block sizes and the method of splitting. They include «binary buddies» (the most common), «Fibonacci buddies», «weighted buddies», and «double buddies».

See also: «allocation mechanism»; «segregated free lists»; «segregated fit»; «strict segregated fit».

Related publications:


buffer

A buffer is a large «block» of «memory(2)» from which blocks are «allocated» contiguously, as a simple technique for fast «allocation».

By keeping only a high-water mark (that is, a «pointer» to the start of unused memory), the buffer technique avoids expensive «in-band headers» and the searching of «free block chains». Buffers tend to, however, lead to «external fragmentation».

Related publications:


bus error

Strictly speaking, a bus error is a fault on a hardware bus, such as when an invalid «address» is issued.

Generally, any hardware exception caused by a «memory(2)» access (for example, «loading» an «unaligned» «word») is termed a bus error. The term is often used more loosely as a synonym for any memory access error.

See also: «segmentation violation».

byte(1)

A unit of storage measurement, equal to 8 bits.

It does not matter how the bits are arranged -- it is just a quantity.

This is the sense of byte used in the terms «kilobyte», «megabyte», «gigabyte», «terabyte», etc. The prefixes in these terms derive from the SI prefixes for powers of 1000, but since powers of two are much more common in binary computers, they are used to denote powers of 1024 (= 2^10).

See also: «word».

byte(2)

A data type defined by a processor architecture.

For example, the smallest «addressable» storage «location» on the Intel x86 family is the 8-bit byte.

The PDP-10 has 36-bit «words», and defines "byte" to be a general sub-«word» bit-field. (Compare this with «byte(3)».) On this machine it is commonplace for characters to be packed four or five to a word using 9- or 7-bit bytes respectively.

See also: «word».

byte(3)

A contiguous set of bits used to represent a range of values compactly.

The number of bits in a byte is a measure of the information content of the byte. An n-bit byte can represent 2^n distinct values.

Bytes may be packed into (or otherwise stored in bit-fields of) integers, words, or other aligned values for space efficiency.

byte(4)

A data type or storage unit defined by a programming language.

In ANSI/ISO C, "the unit of data storage large enough to hold the basic character set of the execution environment". In this sense, it is often used synonymously with the C type char. C defines sizeof(char) to be 1. Many architectures that run C programs equate this sense of byte and «byte(2)».


C

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

cache(1) (also known as memory cache, cache memory)

A processor's memory cache is a small piece of fast, but more expensive memory, usually «static memory(1)», used for copies of parts of «main memory». The cache is automatically used by the processor for fast access to any data currently «resident» there. Access to the cache typically takes only a few processor clock cycles, whereas access to «main memory» may take tens or even hundreds of cycles.

What part of main memory is resident in a cache, and the mechanisms by which it is kept consistent, are quite varied. See «cache policy».

Some systems have more than one level of cache. "level 1 cache" is the fastest, smallest «storage level», "level 2" the next fastest, and so on.

See also: «storage hierarchy»; «cache(2)».

cache(2)

A cache is any small, fast piece of «storage», used for copies of data that normally reside in a larger, slower piece of storage. The cache is used to speed up access to data «resident» in the slower storage.

In a typical cache, recently used data is «resident» in the cache (although the details of this depend on the «cache policy»). A «cache(1)» is the most common example of a cache(2).

See also: «storage hierarchy».

cache memory (for full details, see «cache(1)»)

A processor's memory cache is a small piece of fast, but more expensive memory, usually «static memory(1)», used for copies of parts of «main memory». The cache is automatically used by the processor for fast access to any data currently «resident» there. Access to the cache typically takes only a few processor clock cycles, whereas access to «main memory» may take tens or even hundreds of cycles.

cache policy

Any «cache(3)» uses a cache policy to decide which data to store. A cache policy is an attempt to predict the future, so that the cache will provide swift responses to future requests.

Cache policy may be implemented in hardware, software, or a combination of both. Some systems allow programs to influence cache policy, by giving hints or directions about future use of data.

There are three main aspects of cache behavior which the cache policy can affect:

Fetch policy

This determines which data is fetched into the cache, usually as a result of receiving a request for data that isn't cached.

Eviction policy

This determines which data is discarded from the cache to provide space for newly fetched data.

Write policy

This determines how and when modifications to cached data are synchronized with the underlying storage.

See also: «cache(1)»; «cache(2)»; «cache(3)».

Related publications:


caching(3) (also known as memoization, tabling)

Caching is a heuristic that stores answers to questions asked in the past in a cache or a table, in order that they may be more quickly answered in the future. This process is also called memoization and tabling (by the Prolog community).

A "look-ahead cache" attempts to store answers to questions that will be asked soon. A «cache(2)» is a common example of a cache(3).

cactus stack (also known as spaghetti stack)

A cactus stack is a «stack» with branches. When diagrammed, its shape resembles that of a saguaro cactus.

In languages that support «continuations», «activation records» can have «indefinite extent». One technique for implementing continuations is not to copy the activation records that are captured, rather to create a fork in the stack below the captured «stack frames», so that new frames appear as a parallel branch. Often the process of forking is done lazily, captured frames are only duplicated if they are modified.

card

A card is a division of memory, all cards being of equal size (in a particular area of discourse). A card is usually bigger than a «word» and smaller than a «page». Cards are used in a technique called «card-marking» whereby «dirty bits» (which record which portions of old generations have been written into) are maintained for each card. Often the use of cards will also entail the use of a «crossing map».

card marking, card-marking

A technique for managing «pointer» «stores» into old «generations» (which in turn is used to track «inter-generational pointers»). Each generation is divided into a number of equal-sized «cards», and when a generation is written into, the particular card written to is recorded (often by using a «bit-table»). Subsequently, when «scanning» an older generation in order to collect a younger generation, only the recorded cards (in the old generation) need to be scanned.

See also: «generational garbage collection».

Related publications:


cell (for full details, see «object»)

In «memory management», we use the term object or cell to mean a contiguous «block» of «memory(2)» forming a single logical structure.

Cheney collector (also known as Cheney scan)

A Cheney collector uses the new «semi-space» of a «two space collector» as a queue of objects remaining to be «scanned», thus eliminating the need for recursion when «tracing» the «graph» of «objects».

See also: «two space collector».

Related publications:


Cheney scan (for full details, see «Cheney collector»)

A Cheney collector uses the new «semi-space» of a «two space collector» as a queue of objects remaining to be «scanned», thus eliminating the need for recursion when «tracing» the «graph» of «objects».

closure

A closure is a function or procedure that is saved along with the current bindings from enclosing blocks for later invocation.

Some programming languages, such as Algol, permit nested blocks to access the local variables of enclosing blocks. Lisp-like languages further permit such an inner block (in particular a function or procedure) to be saved for later invocation. The act of saving such an inner block along with the current bindings of variables in the enclosing blocks that are referenced by the inner block, is called closing over or capturing those variables. The object created is termed a closure. A closure is invoked just like the function from which it was built, passing whatever parameters the function accepts, but when the function executes, the variables that belong to enclosing blocks will have the bindings that were in effect when the closure was created.

Relevance to memory management: A closure is typically implemented by saving both the function and any «activation records» that contain variables referenced by the function. The closure creates additional implicit «references» to the bindings closed over and hence must be accounted for in any memory management scheme. The closure itself is an object that must be managed and may have either «dynamic extent» or «indefinite extent» depending on whether it is only used by inner blocks of the creating block or passed out of the creating block.

See also: «continuation».

coalesce

Coalescing is the act of merging two adjacent «free blocks».

Coalescing reduces «external fragmentation», but is not totally effective.

Coalescing can be done as soon as blocks are freed, or it can be deferred until some time later (known as «deferred coalescing»), or it might not be done at all.

Dynamic Storage Allocation: A Survey and Critical Review has details about fragmentation, and which coalescing strategies are effective under what circumstances.

Related publications:


collect

An «object» is collected when it is «reclaimed» by a «garbage collector».

Similar terms: «reclaim».

collection (for full details, see «collection cycle»)

A collection cycle is a single complete execution of a «tracing garbage collection» algorithm.

collection cycle (also known as collection)

A collection cycle is a single complete execution of a «tracing garbage collection» algorithm.

Each collection cycle includes (not necessarily in strict order) choosing a «condemned set»; «scanning» «roots» and «objects» that have not been condemned; «tracing» the object graph to find all condemned objects that are «reachable»; and «reclaiming» those that were not reachable.

In non-incremental garbage collection, the «mutator» pauses at the start of a collection cycle and cannot continue until it is complete. In «incremental» and «parallel» garbage collection, a collection cycle can be interleaved with, or simultaneous to, mutator activity.

collector(1) (for full details, see «garbage collector»)

A (garbage) collector is (an implementation of) a «garbage collection» algorithm.

collector(2)

In a «garbage-collected» system, the part that executes the garbage collection code, which discovers unused «storage» and «reclaims» it.

For purposes of describing «incremental garbage collection», the system is divided into the «mutator» and the collector. These can be separate threads of computation, or interleaved within the same thread.

Historical note: This term is due to Dijkstra et al.

Opposites: «mutator».

Related publications:


color, colour

In a «tri-color marking» scheme, each «node» has a one of three colors: «black», «white», or «gray». In a «treadmill», nodes may also be colored «off-white».

committed (for full details, see «mapped»)

A range of «virtual addresses» is said to be mapped (committed on Windows®) if there is «physical memory(2)» associated with the range.

compactifying (for full details, see «compaction»)

Compaction is the process of «moving» «live» «objects» to eliminate «dead» space between them. Some people call this compactifying, to distinguish it from techniques for compressing data structures.

compaction (also known as compactifying)

Compaction is the process of «moving» «live» «objects» to eliminate «dead» space between them. Some people call this compactifying, to distinguish it from techniques for compressing data structures.

Compaction is used to avoid «external fragmentation» and to increase «locality of reference».

composite object

In the PostScript® language, composite objects are the «boxed» objects.

Unlike a «simple object», the main data (what PostScript calls the value) in a composite object are stored separately, in «VM(2)». Several composite objects can share the same value.

Similar terms: «boxed».
Opposites: «simple object».

comprehensive

A «collector(1)» is comprehensive if all «garbage» (or, all «unreachable» «objects») is «reclaimed» in one «collection cycle».

See also: «garbage collection».

concurrent garbage collection (for full details, see «parallel garbage collection»)

A parallel or concurrent «collector(2)» executes simultaneously with the «mutator», usually on a multi-processor machine.

condemned set (for full details, see «threatened set»)

Condemned «objects» are those which are candidates for «recycling» within a «collection cycle».

connected

«Objects» are connected if and only if one contains a «reference» to the other.

See also: «graph».

cons(1)

In Lisp, cons is a primitive operation creating a list element (from English "CONStruct"). By extension, a cons is the element created.

Other links:

cons(2) (for full details, see «allocate»)

Allocation is the process of assigning resources. When requested to by the program, an application «memory manager» or «allocator» allocates a «block» of «memory(2)» for the program to store its data in. Allocation is also known as consing, from «cons(1)».

conservative garbage collection

In conservative «garbage collection», the layout of «objects» and «roots» is not known, instead the «collector(1)» assumes that any field that looks like a «pointer» might be a «reference».

Conservative collectors can work with programs where information about the «memory(2)» layout is not available, because, for example, the language doesn't support «GC».

A conservative collector doesn't need to know the «format» of the objects, it just needs some idea of where the object boundaries are. It regards any field value that looks like a pointer to an object (or, sometimes, into the middle of one), as preventing the «recycling» of that object. It can't «move» objects, because then the references to the moved objects would need to be updated, and such «ambiguous references» must not be modified, in case they weren't pointers after all. Therefore, conservative collectors are usually «mark-sweep collectors».

Because references are ambiguous, some objects may be retained despite being actually «unreachable». In practice, this happens rarely, and refinements such as «black-listing» can further reduce the odds.

Opposites: «exact garbage collection».
See also: «ambiguous root»; «semi-conservative garbage collection»; «interior pointer».

Related publications:


constructor(1)

A constructor is a function or method that «allocates» and initializes an «object».

Opposites: «destructor(1)».

constructor(2)

In C++, a constructor is a member function that is used to initialize a newly-«allocated» object.

The actual allocation of «memory(2)» is performed by operator new or the compiler (for «static» and «stack allocation»), and the new «block» is then passed to the appropriate constructor.

See also: «destructor(2)».

continuation

A continuation is the data required to restore an execution context after invocation of another context, typically as a subroutine.

Relevance to memory management: If continuations can be represented as first-class objects, as in Scheme, the execution contexts can no longer be stored on a «stack», instead, (at least some) «activation records» have to be «heap-allocated».

See also: «closure».

control stack (also known as activation stack, execution stack)

A «stack» that stores «activation records», particularly subroutine return information, is known as a control stack.

Typically the control stack is supported and used by the hardware architecture and the operating system, limiting the types and sizes of «objects» that can be stored on it. Often, only one type of object, a «stack frame», is permitted, and the layout of that is defined by the hardware architecture.

Relevance to memory management: Theoretically, a control stack is simply an array of activation records, and hence just another object managed by the «memory manager». In practice, the control stack is central to the performance of the hardware architecture and may require special treatment. In particular, it may not be accessible as ordinary «memory(2)», or it may have its own «cache(2)» with specific updating requirements.

Similar terms: «stack».
See also: «data stack».

copying garbage collection (also known as scavenging garbage collection)

Copying garbage collection is a kind of «tracing garbage collection» that operates by «relocating» «reachable» «objects» (this is sometimes called scavenging) and then «reclaiming» objects that are left behind, which must be «unreachable» and therefore «dead».

A copying garbage collection relies on being able to find and correct all «references» to copied objects.

Copying garbage collection
Diagram: Copying garbage collection

Similar terms: «moving».
See also: «broken heart»; «forwarding pointer»; «two-space collector».

core

A historical synonym for «main memory», deriving from the cores or ferrite rings which were once the main technology used to implement main memory.

Similar terms: «main memory».

creation space

In «generational garbage collection», when «generations» are divided into «buckets», the creation space is where new «objects» are created in each generation.

This term is sometimes used as a synonym for «nursery space».

Opposites: «aging space».
See also: «generational garbage collection».

crossing map

Where «memory(2)» has already been divided into some fixed-sized unit (for example, «pages» or «cards»), a crossing map records where «objects» lie across the boundaries of the fixed-sized units. In other words, which fixed-sized units do not start with the beginning of an object.

A system which implements «remembered sets» by «page-marking» or «card-marking» needs to scan all the «pointers» in the page or card. If the system can not «scan» partial objects (or requires information in the object «header» in order to scan a partial object), a crossing map is necessary to find the beginning of the first object in the unit.

Relevance to memory management: In a sense, a crossing map is an optimization of «tagged architecture». It represents the minimum information necessary to determine how to interpret any word of memory.

cyclic data structure

A data structure is cyclic if some of its «references» form a loop; that is, there's an «object» that can be reached by following references from itself.


D

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

dangling pointer

A dangling «pointer» is a surviving «reference» to an «object» that no longer exists at that «address»

In «manual memory management», dangling pointers typically arise from one of:

Dangling pointers can occur under «automatic memory management», because of a «garbage collection» bug -- such as premature collection, or «moving» without updating all «references» -- but this is much rarer because «GC» code is usually a single common core of reused code.

data stack

A «stack» used to manage the storage of «stack-allocated» «objects», other than «activation records», often under program control.

Because of the limitations that may be imposed on the «control stack», or to support stack-like semantics for certain data structures, some language implementations manage additional data stacks in software for storing objects that have «dynamic extent» but that do not fit within the constraints of the control stack.

See also: «control stack».

dead

An «object» is dead if it is not «live»; that is, when the «mutator» cannot reach any state in which it accesses the object.

It is not possible, in general, for «garbage collectors» to determine exactly which «objects» are dead and which are live. Instead, they use some approximation to detect objects that are provably dead, such as those that are «unreachable».

Opposites: «live».
See also: «garbage»; «undead»; «free(3)».

deallocate (for full details, see «free(1)»)

In «manual memory management», to free or deallocate an «object» is to tell the «memory manager» that it is no longer needed. The «memory(1)» may then be «recycled» by being used for subsequent «allocation», or by being returned to the operating system.

deferred coalescing

Deferred coalescing is a policy which «coalesces» «free blocks» some time after the blocks are freed, as opposed to coalescing free blocks immediately as they are freed.

Adjacent free blocks can be coalesced to form larger free blocks; deferred coalescing is a catch-all for policies which perform this coalescing sometime after the blocks were freed.

Given this rather flexible definition there are a number of choices for when to coalesce: as the «free list» is traversed during allocation, when the allocation cannot be satisfied from the free list, periodically, and so on. In addition there are choices to be made regarding how much coalescing to perform at any one time.

deferred reference counting

Deferred «reference counting» reduces the cost of maintaining reference counts by avoiding adjustments when the «reference» is stored on the «stack».

On many systems, the majority of stores are made into local variables, which are kept on the stack. Deferred reference counting leaves those out and counts only references stored in «heap» objects. This requires compiler support, but can lead to substantial performance improvements.

«Objects» cannot be «reclaimed» as soon as their reference count becomes zero, because there might still be references to them from the stack. Such objects are added to a «zero count table» (ZCT) instead. If a reference to an object with a count of zero is stored into the heap, then the object is removed from the ZCT. Periodically the stack is «scanned», and any objects in the ZCT which were not referenced from the stack are reclaimed.

Deferred reference counting has been used successfully with several languages, notably Smalltalk. However, since it fails to collect objects with «cyclic» references, it is often used alongside a «tracing garbage collector».

Related publications:


derived pointer (for full details, see «interior pointer»)

An interior pointer is a pointer to «memory(2)» occupied by an «object» which does not point to the start location. Also called a derived pointer when it's derived from a «base pointer».

destructor(1)

A destructor is a function or a method that performs the explicit «deallocation» of an «object». It may also perform clean-up actions.

Opposites: «constructor(1)».

destructor(2)

In C++, a destructor is a member function that is used to clean up when an object is being «deallocated».

When an object is being destroyed (by delete or automatically), the appropriate destructor is called, and then the actual deallocation of «memory(2)» is performed by operator delete or the run-time system (for «static» and «stack allocation»).

See also: «constructor(2)».

DGC (for full details, see «distributed garbage collection»)

Distributed garbage collection is «garbage collection» in a system where «objects» might not reside in the same «address space» or even on the same machine.

direct method

Direct methods of «automatic memory management» maintain information about the «liveness» of each «object», detecting «garbage» directly.

Such bits of information, e.g., «reference counts», are typically stored within the objects themselves.

Direct «garbage collection» can allow «memory(2)» to be «reclaimed» as soon as it becomes «unreachable». However, the stored information must be updated as the «graph» of objects changes; this may be an expensive operation, especially in «distributed garbage collection» where it can lead to intensive communication between processors, and make garbage collection less robust to network failures.

Opposites: «indirect method».

Related publications:


dirty bit

A dirty bit is a flag indicating that a «page» (or similar) has been written to since it was last examined.

Dirty bits are used by «caches(2)» to determine which pages must be written out, and by garbage collectors in conjunction with «write barriers».

distributed garbage collection (also known as DGC)

Distributed garbage collection is «garbage collection» in a system where «objects» might not reside in the same «address space» or even on the same machine.

Distributed garbage collection is difficult to achieve in widely-distributed systems (over wide-area networks) because of the costs of synchronization and communication between processes. These costs are particularly high for a «tracing garbage collector», so other techniques, including «weighted reference counting», are commonly used instead.

double buddies

A «buddy system» «allocation mechanism» using a pair of «binary buddy» systems with staggered size classes.

One system is a pure binary buddy, with powers-of-two classes (2, 4, 8,...). The other uses some fixed multiple of powers-of-two (e.g., 3, 6, 12, ...). This resembles «weighted buddies», but the two buddy systems are treated independently: blocks cannot be «split» or «coalesced» from one to the other.

Related publications:


double free

A double free is when an attempt is made to «free(1)» a «memory(2)» «block» that has already been freed.

This usually occurs in «manual memory management» when two parts of a program believe they are responsible for the management of the same block.

Many manual «memory managers» have great trouble with double frees, because they cannot cheaply determine that «deallocated» blocks were already free. Instead, they corrupt their «free block chain», which leads to mysterious problems when the same block is subsequently «allocated».

See also: «premature free».

doubleword (also known as longword)

A doubleword is a unit of memory consisting of two adjacent «words». In digital's Alpha architecture, it's called a longword.

Historical note: On the Intel® 80386, 80486. and Pentium® processors, the doubleword of 32 bits is actually the natural word size, but the term word is still used for the 16-bit unit, as it was on earlier processors of this series.

See also: «quadword».

DRAM (for full details, see «dynamic memory»)

Dynamic memory, or dynamic RAM (DRAM, pronounced "dee ram"), is a type of «RAM».

dynamic allocation (for full details, see «heap allocation»)

Heap allocation or dynamic allocation means run-time «allocation» and «deallocation» of «storage» in arbitrary order.

dynamic extent

An «object» has dynamic «extent» if its «lifetime» is bounded by the execution of a function or some other block construct.

Objects of dynamic extent are usually «stack-allocated».

Similar terms: «automatic storage duration».
Opposites: «indefinite extent».

dynamic memory (also known as dynamic RAM, DRAM)

Dynamic memory, or dynamic RAM (DRAM, pronounced "dee ram"), is a type of «RAM».

Dynamic RAM requires periodic refreshing to avoid losing its contents (as opposed to «static memory(1)», the contents of which are preserved without any need for refreshing). The refreshing is performed by additional "refresh hardware" usually external to the dynamic RAM package itself, sometimes by the main CPU. Dynamic RAM is cheap and compact and is the choice for large amounts of relatively fast RAM, such as the «main memory» of PCs. Dynamic RAM often comes packaged in SIMMs or DIMMs.

See also: «static memory(1)»; «SDRAM».

dynamic RAM (for full details, see «dynamic memory»)

Dynamic memory, or dynamic RAM (DRAM, pronounced "dee ram"), is a type of «RAM».


E

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

edge

In a «graph», an edge is a connection between two «nodes».

In a directed graph (digraph), edges have a direction; otherwise the start and end nodes are interchangeable. By convention, two directed edges between the same two nodes, but in different directions, are depicted as a bi-directional edge.

Typically an edge represents some relation between nodes.

Relevance to memory management: In memory management, edges normally represent the fact that an «object» holds a «reference» to another object.

See also: «graph».

entry table(1)

An entry table is a table of «references» into a set of «objects» used to indirect references from the outside.

The Lieberman-Hewitt «collector(1)» represented references from older «generations» to younger ones by indirect pointers through an entry table in the younger generation that contained the actual «address» of the young object. This is fairly expensive without special hardware; other «generational» collectors generally use «remembered sets».

See also: «generational garbage collection»; «exit table».

Related publications:


entry table(2)

An entry table is an implementation of a «remembered set», where, for a given «generation», there is a list of «objects» in older generations which contain «references» into that generation.

One could also store the actual «locations» of the references, which would save time when «scanning», but incur other costs.

Similar terms: «remembered set».
See also: «generational garbage collection»; «exit table».

exact garbage collection (also known as precise garbage collection, type-accurate garbage collection)

«Garbage collection» is exact (or precise) if it deals only with «exact references».

An exact «collector(1)» needs to know the «format» of the «objects» and the «roots», so that it can tell which fields are references.

Opposites: «conservative garbage collection».

exact reference (also known as precise reference, sure reference)

An exact or precise or sure reference is a value the «collector(1)» knows is a «reference».

This is the usual sort of reference. The term is used to draw a contrast with «ambiguous reference».

Opposites: «ambiguous reference».

exact root (also known as precise root)

An exact or precise root is a «root» that contains only «exact references».

Opposites: «ambiguous root».
See also: «exact reference».

exact segregated fit

A «segregated fit» «allocation mechanism» which has a separate «free list» for each possible block size. The array of free lists may be represented sparsely. Large blocks may be treated separately.

See also: «segregated fit»; «segregated free list»; «allocation mechanism».

Related publications:


execution stack (for full details, see «control stack»)

A «stack» that stores «activation records», particularly subroutine return information, is known as a control stack.

exit table

An exit table is a table of all «references» from a set of «objects» to objects outside the set.

See also: «entry table(1)»; «entry table(2)».

Related publications:


extent (for full details, see «lifetime»)

The lifetime or extent of an «object» is the time for which the object is «live».

external fragmentation

External «fragmentation» is the inability to use «memory(1)» because «free(3)» memory is divided into many small «blocks».

If «live» «objects» are scattered, the free blocks cannot be «coalesced», and hence no large blocks can be «allocated».

Common solutions to external fragmentation include:

See also: «internal fragmentation».

Related publications:



F

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

fencepost, fence post

A fencepost is spare «memory(1)» between «allocated» «blocks» for checking purposes.

Some «memory management» systems leave spare memory between allocated blocks and store special values in it. If a checking routine finds that these memory «locations» have been modified, this probably indicates an «overwriting error» in the application that was allocated the adjacent block.

Such checking is extremely useful in a memory manager, because it can help application programmers to find bugs that would otherwise be difficult to reproduce and track down.

Similar terms: «in-band header».

fencepost error, fence post error

The term fencepost error refers to errors arising from the fact that, to enclose n consecutive intervals, you need n+1 end-points, from the number of posts required to support fence rails.

An example of a fencepost error would be, in C:


void f(void)
{
  int i;
  int a[10];
  for(i = 0; i <= 10; i++)
    a[i] = 0;
}

because the declaration int a[10]; creates an array of ten integers, with index from 0 to 9, but the for loop index i runs from 0 to 10.

Fibonacci buddies

A common «buddy system» «allocation mechanism», in which block sizes form a Fibonacci series (each block size is the sum of the two previous sizes). Each block can therefore be «split» to form two blocks of valid sizes, and the sizes are more closely spaced than in «binary buddies». However, if the same size is allocated repeatedly, performance may suffer as the remainder blocks may have to be split again (or become fragments).

See also: «buddy system»; «allocation mechanism».

Related publications:


FIFO-ordered first fit

The «allocation policy» that always uses the least-recently «freed» suitable «free block». Commonly implemented by adding freed blocks to the end of a «free block chain», and then using «first fit» allocation on this chain. «free(1)» can be very quick, depending on the «coalescing» policy.

According to Dynamic Storage Allocation: A Survey and Critical Review, this policy controls fragmentation quite well, better than «LIFO-ordered first fit» and as well as «address-ordered first fit» in some cases, although «locality» may be worse.

See also: «first fit»; «LIFO-ordered first fit»; «address-ordered first fit»; «allocation policy».

Related publications:


file mapping (for full details, see «memory mapping»)

Memory mapping is the technique of making a part of the «address space» appear to contain an "object", such as a file or device, so that ordinary «memory(2)» accesses act on that object.

finalization (also known as termination)

In «garbage-collected» languages, it is often necessary to perform actions on some «objects» after they are no longer in use and before their «memory(2)» can be «recycled». These actions are known as finalization or termination.

A common use of finalization is to release resources when the corresponding "proxy" object dies. For example, an open file might be represented by a stream object. When this object has been proven «dead» by the «collector(1)», it is certain that the file is no longer in use by the program, and it can and should be closed before the stream is recycled.

Note that finalization is not, in general, guaranteed to be prompt, and this can cause problems if it is used to manage scarce operating system resources such as file descriptors.

Many object-oriented languages provide support for finalization, for example, Cedar, Java, Perl 5, and Smalltalk.

The term finalization is sometimes used to refer to the use of «destructors(1)», for example in Ada.

first fit

First fit is a «sequential fit» «allocation mechanism». To quote Dynamic Storage Allocation: A Survey and Critical Review:

First fit simply searches the «free list» from the beginning, and uses the first «free block» large enough to satisfy the request. If the block is larger than necessary, it is split and the remainder is put on the free list.

The first fit mechanism provides a class of first fit «allocation policies», depending on the order in which the free list is stored. «Address-ordered first fit» stores the list in order of (usually increasing) address. «LIFO-ordered first fit» puts blocks on the front of the free list when they are «freed». «FIFO-ordered first fit» puts blocks on the end of the free list when they are «freed».

See also: «address-ordered first fit»; «LIFO-ordered first fit»; «FIFO-ordered first fit»; «sequential fit»; «next fit»; «best fit»; «worst fit».

Related publications:


flip

The instant in a «two-space collector» when the roles of the two «semi-spaces» are reversed. What was the new semi-space is now marked as old and «condemned». What was the old semi-space becomes the site for all new «allocations». Also used in a more general sense to mean the initiation of a new «collection cycle».

floating garbage

Floating garbage is «garbage» that is not «recycled» promptly due to some approximation or optimization in the «garbage collector».

Floating garbage results from conservatively estimating an «object» that is really «unreachable» to be «reachable» for the purposes of a particular «collection cycle». Using estimates can have considerable performance benefits but also result in higher «memory(2)» consumption.

Typical estimates that cause floating garbage are:

A more subtle kind of floating garbage is an unreachable data structure that spans multiple regions that are never «condemned» together.

format

A format describes the representation of an «object»; that is, how the object is laid out in memory.

A format usually specifies where the fields of the objects are located and what their type is.

Relevance to memory management: If formats are provided by a language or the application program, «exact garbage collection» can be used, because the «collector(1)» can determine which fields are «references».

See also: «conservative garbage collection».

forwarding pointer

Some «garbage collectors» «move» «reachable» «objects» into another space. They leave a «forwarding pointer» -- that is, a special «reference» pointing to the new location -- in the old «location», .

Similar terms: «broken heart».
See also: «copying garbage collection»; «two space collector».

fragmentation

Fragmentation is the inability to use «memory(1)» because of the arrangement of memory already in use. It is usually divided into «external fragmentation» and «internal fragmentation».

Related publications:


frame (for full details, see «in-band header»)

Some «memory managers» «allocate» a fixed amount more than is necessary for each «block» and use it to store information such as the size of the block or a «tag». This extra memory is known as an in-band header or a frame

free(1) (also known as deallocate)

In «manual memory management», to free or deallocate an «object» is to tell the «memory manager» that it is no longer needed. The «memory(1)» may then be «recycled» by being used for subsequent «allocation», or by being returned to the operating system.

Opposites: «allocate».
See also: «free(2)»; «destructor(1)».

free(2)

In C, the system function used for explicit «deallocation» is called free.

free(3)

«Memory(2)» is free if it is not currently «allocated».

Historical note: The term available was commonly used to mean "free".

Opposites: «allocated».
See also: «allocate»; «free(1)».

free(4) (for full details, see «unmapped»)

A range of «virtual addresses» is said to be unmapped (free on Windows®) if there is no «physical memory(2)» associated with the range.

free block

A single contiguous area of «memory(2)» available to satisfy an «allocation» request.

For the purpose of discussing «allocation mechanisms», two adjacent free blocks are not considered to be a single free block, until they are «coalesced». Free blocks may be «split».

See also: «allocation mechanism»; «free list».

Related publications:


free block chain

Some systems store the «free list» as a linked list, or chain.

Usually the links are stored within the «free(3)» «blocks». This means that all «allocated» blocks must be large enough to store these, and implies a minimum size.

Sometimes, the free block chain is ordered by «address». This makes «coalescence» considerably cheaper, but «deallocation» more expensive.

See also: «free list».

free list, free-list

The free list is the set of «free blocks».

Originally this term meant the single linked list of all free blocks, but as «allocation mechanisms» have become more varied, it has become more generic, and now may be implemented as a tree or other data structure rather than a linked list. If the implementation actually is a linked list of free blocks, this is called a «free block chain» to distinguish it from the abstract term.

There may be several free lists, classed by size or other characteristic. For instance, «segregated free list» systems classify free lists by block size.

See also: «free block»; «free block chain».

free store (for full details, see «heap»)

The heap or free store is the «memory(2)» area managed by «dynamic allocation».

freestore (for full details, see «heap»)

The heap or free store is the «memory(2)» area managed by «dynamic allocation».

function record (for full details, see «activation record»)

An activation or function record is a data structure, associated with the invocation of a function, procedure or control block that stores the variables, temporaries and fixed-sized data local to the block, and the information required to return to the invoking context. It is often stored on a «stack».


G

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

garbage

Garbage is «objects» that are «dead».

In «tracing garbage collection», the term is sometimes used to mean objects that are known to be dead; that is, objects that are «unreachable».

garbage collection (also known as GC)

Garbage collection (GC), also known as automatic memory management, is the automatic «recycling» of «dynamically allocated» «memory(2)». Garbage collection is performed by a «garbage collector» which recycles memory that it can prove will never be used again. Systems and languages which use garbage collection can be described as garbage-collected.

Garbage collection is a tried and tested memory management technique that has been in use since its invention in the 1950s. GC avoids the need for the programmer to «deallocate» memory «blocks» explicitly, thus avoiding a number of problems: «memory leaks», «double frees», and «premature frees». The burden on the programmer is reduced by not having to investigate such problems, thereby increasing productivity.

Garbage collection can also dramatically simplify programs, chiefly by allowing modules to present cleaner interfaces to each other: the management of object storage between modules is unnecessary.

It is not possible, in general, for a «garbage collector» to determine exactly which «objects» are still «live». Even if it didn't depend on future input, there can be no general algorithm to prove that an object is live (cf. the Halting Problem). All garbage collectors use some efficient approximation to liveness. In «tracing garbage collection», the approximation is that an object can't be live unless it is «reachable». In «reference counting», the approximation is that an object can't be live unless it is «referenced». Hybrid algorithms are also possible. Often the term garbage collection is used narrowly to mean only tracing garbage collection.

There is a large body of published work on particular and general GC algorithms.

Historical note: Garbage collection was first invented by John McCarthy in 1958 as part of the implementation of Lisp.

Other significant languages offering GC include Java, Perl, Modula-3, Prolog, ML, and Smalltalk. Major applications using GC include Emacs and AutoCAD; usually, you can't tell whether an application does or not, but these have extension languages that expose the fact.

Similar terms: «automatic memory management».
Opposites: «manual memory management».
See also: «conservative garbage collection»; «copying garbage collection»; «distributed garbage collection»; «generational garbage collection»; «incremental garbage collection»; «parallel garbage collection».

Other links:

Related publications:


garbage collector (also known as collector(1))

A (garbage) collector is (an implementation of) a «garbage collection» algorithm.

This term is often used when referring to particular implementations or algorithms, e.g., "the Boehm-Demers-Weiser collector".

GB (for full details, see «gigabyte»)

A gigabyte is 1024 «megabytes», or 1073741824 «bytes(1)».

GC (for full details, see «garbage collection»)

Garbage collection (GC), also known as automatic memory management, is the automatic «recycling» of «dynamically allocated» «memory(2)». Garbage collection is performed by a «garbage collector» which recycles memory that it can prove will never be used again. Systems and languages which use garbage collection can be described as garbage-collected.

General Protection Fault (also known as GPF)

A General Protection Fault on the 16-bit WindowsTM platforms is the equivalent of a «segmentation violation» on UNIX®.

generation

A generation is a set of «objects» of similar age.

A «generational garbage collector» will typically divide the set of all objects into generations, and «condemn» all the objects in a generation together. Rather than allowing whole generations to age, the «collector(1)» can «promote» objects into older generations as they survive successive «collection cycles».

New objects are usually allocated in the youngest or «nursery generation», but if we know that particular objects will be long-lived, we might want to allocate them directly in an older generation. Thus, more loosely, a generation is a set of objects which have similar expected «lifetimes».

See also: «bucket».

generation scavenging (for full details, see «generational garbage collection»)

Generational garbage collection is «tracing garbage collection» that makes use of the «generational hypothesis». «Objects» are gathered together in «generations». New objects are allocated in the youngest or nursery generation, and «promoted» to older generations if they survive. Objects in older generations are «condemned» less frequently, saving CPU time.

generational garbage collection (also known as generation scavenging)

Generational garbage collection is «tracing garbage collection» that makes use of the «generational hypothesis». «Objects» are gathered together in «generations». New objects are allocated in the youngest or nursery generation, and «promoted» to older generations if they survive. Objects in older generations are «condemned» less frequently, saving CPU time.

It is typically rare for an object to refer to a younger object. Hence, objects in one generation typically have few «references» to objects in younger generations. This means that the «scanning» of old generations in the course of collecting younger generations can be done more efficiently by means of «remembered sets».

In some purely functional languages (that is, without update), all references are backwards in time, in which case remembered sets are unnecessary.

See also: «remembered set».

generational hypothesis (also known as infant mortality)

Infant mortality or the generational hypothesis is the observation that, in most cases, young «objects» are much more likely to «die» than old objects.

Strictly, the hypothesis is that the probability of death as a function of age falls faster than exponential decay (inverse hyper-exponential), but this strict condition is not always required for techniques such as «generational garbage collection» to be useful.

gigabyte (also known as GB)

A gigabyte is 1024 «megabytes», or 1073741824 «bytes(1)».

See «byte(1)» for general information on this and related quantities.

good fit

The class of «allocation policies» which approximate «best fit». Strict best fit may be costly to implement (depending on the details of the «allocation mechanism»), so some implementors approximate it, choosing a block which is close in size to the allocation request.

See also: «best fit»; «allocation policy»; «next fit»; «worst fit».

Related publications:


GPF (for full details, see «General Protection Fault»)

A General Protection Fault on the 16-bit WindowsTM platforms is the equivalent of a «segmentation violation» on UNIX®.

grain

The grain of a platform is the smallest «alignment» that is sufficient to accommodate all data accesses on that platform. Often this is a «word» or a small multiple of a word. Double precision floating point numbers often have the strictest alignment requirements.

See also: «alignment»; «word».

graph

A graph is a set of «nodes» together with a set of «edges» connecting nodes.

If the edges have direction like arrows (for example, «references» in a graph of «objects»), then the graph is said to be a directed graph.

Directed graph
Diagram: Directed graph

Relevance to memory management: Graphs are used to model «reachability» for «tracing garbage collection». The «objects» are considered to form a graph, with the nodes of the graph being the objects and the edges of the graph being the references from one object to another. Usually, there is a single, distinguished «root» to which the «mutator» has direct access, and the nodes strongly connected to it are the reachable modes.

gray, grey

In a «tri-color marking» scheme, gray «objects» are objects that are proved or assumed (see «generational» and «condemn») to be «reachable», but have not yet been «scanned».

More precisely, gray objects have been noted reachable, but must still be visited by the «collector(2)» in order to process their children.

Similar terms: «gray list».
Opposites: «black»; «white».

gray list, grey list

The gray list is the set of «objects» that a «tracing garbage collector» has noted «reachable», but hasn't «scanned» yet.

The gray list is so called because it corresponds to the set of «gray» objects in the «tri-color marking» model of graph tracing. The gray list changes as the garbage collector progresses.

Each gray object is «scanned», and all «white» objects referred to by it become gray and are added to the list. Scanning a gray object turns it «black». When the gray list is empty, the tracing is finished, and white objects may be «reclaimed».

The representation of the gray list is a key part of garbage collector design. The size of the list is potentially proportional to the size of the «heap», and the operation of finding the next gray object to scan must be cheap.

See also: «Cheney scan».


H

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

handle

A handle is an object that represents a resource.

Handles are used when the resource cannot be represented directly. For example, a file handle is an object passed between a process and the OS in order to access a file, because the file itself cannot be represented.

Relevance to memory management: In memory management, a handle is an object that represents another «object». Handles are usually used because the object itself needs to be «moved» in «memory(2)», or even «swapped out» to disk. The program therefore cannot know the «address» of the object.

For example, the Mac® OS makes extensive use of handles in its heap management to avoid problems due to «fragmentation». If the Mac OS Memory Manager cannot satisfy a request for memory, it may try «compacting» the «heap» -- moving all the «relocatable» objects together to squeeze out gaps. It can do this because the program only has handles on the objects, and not their actual addresses.

Legend
Diagram: Legend

Handle-based heap before compaction
Diagram: Handle-based heap before compaction

Handle-based heap after compaction
Diagram: Handle-based heap after compaction

Similar terms: «pointer».

header (for full details, see «in-band header»)

Some «memory managers» «allocate» a fixed amount more than is necessary for each «block» and use it to store information such as the size of the block or a «tag». This extra memory is known as an in-band header or a frame

heap (also known as free store, freestore)

The heap or free store is the «memory(2)» area managed by «dynamic allocation».

This use of heap is unconnected with the data structure used by the heapsort algorithm.

heap allocation (also known as dynamic allocation)

Heap allocation or dynamic allocation means run-time «allocation» and «deallocation» of «storage» in arbitrary order.

Dynamic allocation is usually for «objects» whose size, quantity, or «lifetime» could not be determined at compile-time. It is necessary to implement modern data structures, such as recursive trees and full «closures».

Objects on the «heap» can be managed «manually», as in C, or «automatically», as in Lisp and JavaTM.

Opposites: «stack allocation»; «static allocation».
See also: «indefinite extent».

hit

A hit is a successful lookup in any form of «cache(3)», most commonly at some level of a «storage hierarchy», such as a «cache(1)» or «virtual memory(1)» system.

Opposites: «miss».

hit rate

At any level of a «storage hierarchy», the hit rate is the proportion of accesses which «hit».

Opposites: «miss rate».


I

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

immediate data

Immediate data is the representation of a «value object» as one or more machine «words», as a register, or as a field in an instruction.

Immediate data takes its name from the value of the object being immediately available, rather than requiring a «load» or indirection through a «reference».

Similar terms: «unboxed».
Opposites: «boxed»; «reference»; «pointer».

immune set

The set of «objects» which are not «condemned».

Opposites: «condemned set».

immutable

In some programming languages, «objects» of some types are immutable, that is, they cannot be modified. For example, in Standard ML, only arrays and refs are mutable; all other objects are immutable.

This property can be very useful for «garbage collection». For instance, no immutable object may contain a «reference» to an object younger than itself, and no immutable object will appear in a «remembered set». Garbage collectors for these languages often take advantage of this property.

In lazy languages, the evaluation of an expression may require an object of a different size, and adjustment of references may take place. This means that, although objects might be immutable at the language level, they are not immutable at the implementation level, and may contain references to younger objects.

Opposites: «mutable».
See also: «generational garbage collection».

immutable object (for full details, see «value object»)

A value object or immutable object is an «object» whose identity depends solely upon its value or magnitude.

in-band header (also known as frame, header)

Some «memory managers» «allocate» a fixed amount more than is necessary for each «block» and use it to store information such as the size of the block or a «tag». This extra memory is known as an in-band header or a frame

This is a form of «internal fragmentation», although sometimes, «alignment» requirements result in free space for the header.

Storing control information in-band often results in bad «locality», particularly for «deallocation».

Opposites: «out-of-band header».
See also: «stack frame»; «activation frame».

incremental garbage collection

Some «tracing garbage collection» algorithms can pause in the middle of a «collection cycle» while the «mutator» continues, without ending up with inconsistent data. Such collectors can operate incrementally and are suitable for use in an interactive system.

Primitive garbage «collectors(1)», once they start a «collection cycle», must either finish the task, or abandon all their work so far. This is often an appropriate restriction, but is unacceptable when the system must guarantee response times; for example, in systems with a user interface and in real-time hardware control systems. Such systems might use incremental garbage collection so that the time-critical processing and the garbage collection can proceed effectively in parallel, without wasted effort.

Similar terms: «parallel garbage collection».
See also: «tri-color marking»; «barrier(1)».

Related publications:


incremental-update, incremental update

Incremental-update algorithms for «tracing», «incremental GC» note changes made by the «mutator» to the «graph» of «objects» and update the «collector(2)» state to make it correctly trace the new graph.

In order for the collector to miss a «reachable» «object», the following two conditions need to hold at some point during tracing:

  1. The mutator stores a «reference» to a «white» object into a «black» object.
  2. All paths from any «gray» objects to that white object are destroyed.

Incremental-update algorithms ensure the first condition cannot occur, by painting either the black or the white object gray (see Barrier techniques for incremental tracing for details).

They are so called because they incrementally update the collector's view of the graph to track changes made by the mutator.

Historical note: This distinction between incremental-update and snapshot-at-the-beginning was first introduced for write-barrier algorithms, but it applies to any type of tracing algorithm.

Opposites: «snapshot-at-the-beginning».
See also: «tri-color marking»; «strong tri-color invariant»; «barrier(1)».

Related publications:


indefinite extent

An «object» has indefinite extent if its «lifetime» is independent of the block or function-call structure of the program.

The «lifetime» of such an object can sometimes be determined by the programmer, and specified by «freeing» the object explicitly. This becomes harder to do correctly as the program becomes more complex, especially if objects are passed across module boundaries, or if higher-order functions are used. In some languages it is impossible to determine the extent at compile-time. In these situations, a «garbage collector» can be used to «recycle» objects whose «life» has come to an end.

Opposites: «dynamic extent».

indexed fit

A class of «allocation mechanisms» that use an indexing data structure, such as a tree or hash table, to identify suitable «free blocks», according to the «allocation policy». For instance, a tree ordered by block size may be used to implement the «best fit» policy.

See also: «allocation mechanism»; «allocation policy»; «sequential fit»; «bitmapped fit».

Related publications:


indirect method

Indirect methods of «automatic memory management» are those in which the information necessary to determine whether an «object» can be «reclaimed» is not stored in or associated with that object, but is derived from other objects.

Indirect methods detect «garbage» by «tracing» «reachable» objects.

Indirect methods cannot always reclaim «memory(2)» as soon as it becomes «dead», because it may be necessary to inspect many other objects to determine this. However, not having to store and update information on each object may reduce the overhead for the «collector(1)». In «distributed garbage collection», this can reduce the amount of communication between processors.

Similar terms: «tracing garbage collection».
Opposites: «direct method».

Related publications:


infant mortality (for full details, see «generational hypothesis»)

Infant mortality or the generational hypothesis is the observation that, in most cases, young «objects» are much more likely to «die» than old objects.

inter-generational pointer

An inter-generational pointer is a «reference» that is stored in an «object» in one «generation» and references an object in another generation.

If the referent's generation is «condemned» and the referrer's generation is not, then the reference is important in two ways. First, the reference keeps the referent «alive», so the referrer must be «scanned» during the «collection». Second, the reference must always refer to the referent, so if the referent is moved, then the referrer must be updated.

During a collection, the only objects in non-condemned areas that must be scanned are the ones that contain inter-generational pointers. «Generational garbage collectors» make use of «write-barriers» and data structures like «entry tables(2)», «exit tables», and «remembered sets» to track those objects at run-time.

Inter-generational pointers can cause «floating garbage»: even if both referrer and referent die, the inter-generational pointer will stop the referent from being reclaimed until the referrer's generation is condemned.

interior pointer (also known as derived pointer)

An interior pointer is a pointer to «memory(2)» occupied by an «object» which does not point to the start location. Also called a derived pointer when it's derived from a «base pointer».

A «pointer» to an object will usually take as its value the «address» of the start of that object.

It is common to have interior pointers into string buffers or to embedded structures. A «suballocator» may place a «header» at the start of each object and pass on an interior pointer.

Relevance to memory management: In a system where interior pointers are used, the «garbage collector» must be able to «mark» an object as «reachable» without being told the start of the object. In a system where interior pointers are not used, the collector should either ignore them (in particular, if it is «scanning» «conservatively») and not retain «garbage» because of them, or possibly report them as bugs.

Opposites: «base pointer».

internal fragmentation

Internal «fragmentation» is where the «memory manager» «allocates» more for each allocation than is actually requested. There are three reasons for this: «padding»; «buddy system»; «in-band headers».

See also: «external fragmentation».

invalid page fault

An exception when using «virtual memory(1)» resulting from an access to a virtual memory location for which no translation is defined.

This is usually an error, often, anachronistically, known as a «segmentation violation».

Similar terms: «bus error».
See also: «page fault».

inverted page table, inverted page-table

In a «virtual memory(1)» system, conventional «page tables» have an entry for every «page» in the «virtual address space». An inverted page table has only as many entries as there are pages in «physical memory(1)», and uses a hash lookup to translate «virtual addresses» to «physical addresses» in nearly constant time.

The entire virtual address space of each process is described in an auxiliary structure, typically a B*-tree, that can efficiently store contiguous, sparse, or large «address space» descriptions. This auxiliary structure may itself be paged to avoid permanently consuming «physical memory(1)» resources.

Inverted page tables are ideal for schemes that store information about «objects» in the high-order bits of their «address». Such schemes may perform poorly with conventional page tables as the sparse address space may cause the page table structures to become so large as to compete with the program «working set» for «physical memory(1)».

Historical note: The Lisp Machine was an early workstation that used an inverted page table with hardware lookup. The Alpha, UltraSPARC®, and PowerPCTM architectures all include inverted page tables. Some implementations of these architectures have hardware-assisted lookup.


K

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

kB (for full details, see «kilobyte»)

A kilobyte is 1024 «bytes(1)».

key object

Definition not yet available. Please see our feedback page for submission information.

kilobyte (also known as kB)

A kilobyte is 1024 «bytes(1)».

See «byte(1)» for general information on this and related quantities.

The standard abbreviation is "kB", but "KB" is often used by people unfamiliar with the metric system.


L

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

large object area

An «allocation mechanism» designed to optimize the management of large «objects» by separating them from small ones.

Large objects, typically objects one or more orders of magnitude larger than the «virtual memory(1)» «page» of a platform, can be costly to «allocate», initialize, and «recycle». By segregating those objects into a separate area, they can be managed using specific mechanisms that would be inefficient for smaller objects but which can reduce the cost of manipulating large ones.

Some example mechanisms:

leaf object (also known as atomic object)

A leaf object is an «object» that does not «reference» any other objects.

In a typed language, the compiler can often determine at compile time that certain types can be represented as leaf objects. Usually these types are either a «scalar data type» or a «vector data type» of scalars with bounded magnitude.

Relevance to memory management: If leaf objects can be identified, a «garbage collector» can make certain optimizations: leaf objects do not have to be «scanned» for references nor are «barriers(1)» needed to detect and maintain references in the object.

leak (for full details, see «memory leak»)

A memory leak is where «allocated» «memory(2)» is not «freed» although it is never used again.

life (for full details, see «lifetime»)

The lifetime or extent of an «object» is the time for which the object is «live».

lifetime (also known as extent, life)

The lifetime or extent of an «object» is the time for which the object is «live».

See also: «dynamic extent»; «indefinite extent».

LIFO-ordered first fit

The «allocation policy» that always uses the most-recently «freed» suitable «free block». Commonly implemented by pushing freed blocks on the front of a «free block chain», and then using «first fit» allocation on this chain. «free(1)» can be very quick, depending on the «coalescing» policy.

This policy may suffer from severe «fragmentation» in the presence of short-lived large objects of a single size. As smaller objects are allocated, the free block chain fills up with fragments a little smaller than the large object size.

See also: «first fit»; «FIFO-ordered first fit»; «address-ordered first fit».

Related publications:


limited-field reference count (also known as sticky reference count)

A «reference counting» technique whereby the field used to store the number of «references» to an «object» has a limited size. In particular, the field is not large enough to represent the maximum possible number of references to an object.

Using the observation that most objects are not referenced a great number of times, some systems that use reference counts only store the count accurately up to a certain maximum value. If an object has more references than the maximum then the count "sticks" at the maximum and is never decremented. Such objects are expected to be rare, but their «storage» can never be «reclaimed» using reference counting. A separate (infrequently run) «tracing garbage collector» is often employed to reclaim this storage.

A degenerate form of limited-field reference counting is «one-bit reference counting» where an object is considered to be referenced either exactly once or many times.

linear addressing

In linear addressing, «addresses» form a single, continuous «address space». This term is used mostly in opposition to «segmented addressing».

Opposites: «segmented addressing».

live (also known as alive, active)

«Memory(2)» or an «object» is live if the program will read from it in future. The term is often used more broadly to mean «reachable».

It is not possible, in general, for «garbage collectors» to determine exactly which «objects» are still live. Instead, they use some approximation to detect objects that are provably «dead», such as those that are not «reachable».

Similar terms: «reachable».
Opposites: «dead».
See also: «undead».

load

To transfer data from «memory(2)» to a processor's «registers».

Load can also be used in the more general sense of moving data from a part of the «memory hierarchy» that is slow to access to one that is fast to access (For example, "it takes about 3 ms for the «virtual memory(1)» system to load a «page» from disk on this system"). When used in this sense, the qualified term «cache(2)» load is common.

LOAD (or an abbreviation) is also commonly used in many processor architectures as the mnemonic name for the machine code instructions that are used primarily to make data accessible to the CPU (by loading the data into registers usually). In RISC architectures it is common for the load instructions to be the only means of making data accessible to the CPU; in CISC architectures it is common for a wide variety of instructions to implicitly or explicitly load data from memory.

Opposites: «store(1)».

locality of reference

Locality of reference is the extent to which successive accesses of nearby «memory(1)» «locations» are nearby in time; for example, a program that reads all the elements of a contiguous array in turn or that repeatedly uses the same memory variable has good locality of reference.

Good locality of reference interacts well with «virtual memory(1)» and «memory caches», as it reduces the «working set» and improves the «hit rate».

There are a number of specialized senses of locality of reference in certain fields such as distributed systems; these are not covered in depth here.

Relevance to memory management: A «mutator» may exhibit predictable properties such as accessing in turn «objects» which were «allocated» in turn, or accessing in turn objects which have «references» to each other. An intelligent «allocator» or «copying garbage collector» can use this observation to improve locality of reference.

Related publications:


location (for full details, see «memory location»)

Each separately-«addressable» unit of «memory(2)» in which data can be stored is called a memory location. Usually, these hold a «byte(2)», but the term can refer to «words».

logical address (for full details, see «virtual address»)

In a «virtual memory(1)» system, the «addresses» that application programs deal with are known as virtual addresses.

longword (for full details, see «doubleword»)

A doubleword is a unit of memory consisting of two adjacent «words». In digital's Alpha architecture, it's called a longword.


M

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

machine word (for full details, see «word»)

Almost all processor architectures have a characteristic data size that is handled most efficiently. This is known as the word size, and data of that size are known as words. The word size is usually a power of two multiple of «bytes(2)».

main memory (also known as memory(3), primary storage)

The main memory (or primary storage) of a computer is «memory(1)» that is wired directly to the processor, consisting of «RAM» and possibly «ROM».

These terms are used in contrast to mass storage devices and «cache memory» (although we may note that when a program accesses main memory, it is often actually interacting with a cache).

Main memory is the middle level of the «memory hierarchy»: it is slower and cheaper than «caches(1)», but faster and more expensive than «backing store».

It is common to refer only to the main memory of a computer; for example, "This box has 16 MB of memory" and "Word for Windows® requires 32 MB".

Historical note: Main memory used to be called «core», and is now likewise often called «RAM».

Similar terms: «RAM»; «core»; «physical memory(1)».

malloc

A function in the standard C library that performs «dynamic allocation» of «memory(2)».

Many people use "malloc" as a verb to mean "allocate dynamically".

Similar terms: «allocate».
Opposites: «free(2)».

manual memory management

In some systems or languages, it is up to the application program to manage all the bookkeeping details of «allocating» «memory(2)» from the «heap» and «freeing» it when no longer required; this is known as manual «memory management».

Manual memory management may be appropriate for small programs, but it does not scale well in general, nor does it encourage modular or object-oriented programming.

To quote Ian Joyner's C++?? : A Critique of C++:

This is the most difficult bookkeeping task C++ programmers face, that leads to two opposite problems: firstly, an object can be «deallocated» prematurely, while valid «references» still exist («dangling pointers»); secondly, «dead» objects might not be deallocated, leading to memory filling up with dead objects («memory leaks»). Attempts to correct either problem can lead to overcompensation and the opposite problem occurring. A correct system is a fine balance.

Historical note: Manual memory management was common in early languages, but «garbage collection» has been around since the late 1950s, in languages like Lisp. Most modern languages use «automatic memory management», and some older languages have «conservative garbage collection» extensions.

Opposites: «automatic memory management».

mapped (also known as committed)

A range of «virtual addresses» is said to be mapped (committed on Windows®) if there is «physical memory(2)» associated with the range.

Note that, in some circumstances, the «virtual memory(1)» system could actually «overcommit» mapped memory.

Opposites: «unmapped».
See also: «mapping»; «memory mapping»; «mmap».

mapping

A mapping is a correspondence between a range of «virtual addresses» and some «memory(1)» (or a «memory-mapped» object). The physical location of the memory will be managed by the «virtual memory(1)» system.

Each «page» in a mapping could be «paged out» or «paged in», and the locations it occupies in «main memory» and/or «swap space» might change over time.

The «virtual address space» can contain of a complex set of mappings. Typically, parts of the address space are «mapped» (have a mapping assigned), others are «reserved» but unmapped, and most of it is entirely «unmapped».

Virtual memory with different kinds of mappings
Diagram: Virtual memory with different kinds of mappings

See also: «backing store».

mark-compact

Mark-compact collection is a kind of «tracing garbage collection» that operates by «marking» «reachable» «objects», then «compacting» the marked objects (which must include all the «live» objects).

The mark phase follows «reference» chains to mark all reachable objects; the compaction phase typically performs a number of sequential passes over «memory(2)» to move objects and update references. As a result of compaction, all the marked objects are moved into a single contiguous «block» of memory (or a small number of such blocks); the memory left unused after compaction is «recycled».

Mark-compact collection can be regarded as a variation of «mark-sweep collection», with extra effort spent to eliminate the resulting «fragmentation». Compaction also allows the use of more efficient «allocation mechanisms», by making large free blocks available.

Related publications:


mark-sweep, mark-and-sweep

Mark-sweep collection is a kind of «tracing garbage collection» that operates by «marking» «reachable» «objects», then «sweeping» over «memory(2)» and «recycling» objects that are unmarked (which must be «unreachable»), putting them on a «free list».

The mark phase follows «reference» chains to mark all reachable objects; the sweep phase performs a sequential («address»-order) pass over memory to recycle all unmarked objects. A mark-sweep «collector(1)» doesn't move objects.

Historical note: This was the first GC algorithm, devised by McCarthy for Lisp.

See also: «mark-compact».

Related publications:


marking

Marking is the first phase ("the mark phase") of the «mark-sweep» algorithm or «mark-compact» algorithm. It follows all «references» from a set of «roots» to mark all the «reachable» «objects».

Marking follows «reference» chains and makes some sort of mark for each object it reaches.

Marking is often achieved by setting a bit in the object, though any conservative representation of a predicate on the «location» of the object can be used. In particular, storing the mark bit within the object can lead to poor «locality of reference».

See also: «sweep»; «compact».

MB (for full details, see «megabyte»)

A megabyte is 1024 «kilobytes», or 1048576 «bytes(1)».

megabyte (also known as MB)

A megabyte is 1024 «kilobytes», or 1048576 «bytes(1)».

See «byte(1)» for general information on this and related quantities.

memoization (for full details, see «caching(3)»)

Caching is a heuristic that stores answers to questions asked in the past in a cache or a table, in order that they may be more quickly answered in the future. This process is also called memoization and tabling (by the Prolog community).

memory(1) (also known as storage, store(2))

memory or storage (or store) is where data and instructions are stored. For example, «caches(1)», «main memory», floppy and hard disks are all storage devices.

These terms are also used for the capacity of a system to store data, and may be applied to the sum total of all the storage devices attached to a computer.

Historical note: "Store" is old-fashioned, but survives in expressions such as "«backing store»".

memory(2)

Memory refers to «storage» that can be accessed by the processor directly (using memory addressing instructions).

This could be «real memory(1)» or «virtual memory(1)».

memory(3) (for full details, see «main memory»)

The main memory (or primary storage) of a computer is «memory(1)» that is wired directly to the processor, consisting of «RAM» and possibly «ROM».

memory(4)

A memory «location»; for example, "My watch has 256 memories."

memory bandwidth

Memory bandwidth (by analogy with the term bandwidth from communication theory) is a measure of how quickly information (expressed in terms of bits) can be transferred between two places in a computer system.

Often the term is applied to a measure of how quickly the processor can obtain information from the «main memory» (for example, "My new bus design has a bandwidth of over 400 Megabytes per second").

memory cache (for full details, see «cache(1)»)

A processor's memory cache is a small piece of fast, but more expensive memory, usually «static memory(1)», used for copies of parts of «main memory». The cache is automatically used by the processor for fast access to any data currently «resident» there. Access to the cache typically takes only a few processor clock cycles, whereas access to «main memory» may take tens or even hundreds of cycles.

memory hierarchy (for full details, see «storage hierarchy»)

A typical computer has several different levels of «storage». Each level of storage has a different speed, cost, and size. The levels form a storage hierarchy, in which the topmost levels (those nearest the processor) are fastest, most expensive and smallest.

memory leak, space-leak (also known as leak, space leak)

A memory leak is where «allocated» «memory(2)» is not «freed» although it is never used again.

In «manual memory management», this usually occurs because «objects» become «unreachable» without being «freed».

In «tracing garbage collection», this happens when objects are «reachable» but not «live».

In «reference counting», this happens when objects are «referenced» but not «live». (Such objects may or may not be «reachable».)

Repeated memory leaks cause the memory usage of a process to grow without bound.

memory location (also known as location)

Each separately-«addressable» unit of «memory(2)» in which data can be stored is called a memory location. Usually, these hold a «byte(2)», but the term can refer to «words».

memory management (also known as storage management)

Memory management is the art and the process of coordinating and controlling the use of «memory(1)» in a computer system.

Memory management can be divided into three areas:

  1. Memory management hardware («MMUs», «RAM», etc.);
  2. Operating system memory management («virtual memory(1)», «protection»);
  3. Application memory management («allocation», «deallocation», «garbage collection»).

Memory management hardware consists of the electronic devices and associated circuitry that store the state of a computer. These devices include RAM, MMUs (memory management units), «caches(1)», disks, and processor «registers». The design of memory hardware is critical to the performance of modern computer systems. In fact, «memory bandwidth» is perhaps the main limiting factor on system performance.

Operating system memory management is concerned with using the memory management hardware to manage the resources of the «storage hierarchy» and allocating them to the various activities running on a computer. The most significant part of this on many systems is «virtual memory(1)», which creates the illusion that every process has more memory than is actually available. OS memory management is also concerned with «memory protection» and security, which help to maintain the integrity of the operating system against accidental damage or deliberate attack. It also protects user programs from errors in other programs.

Application memory management involves obtaining «memory(2)» from the operating system, and managing its use by an application program. Application programs have dynamically changing storage requirements. The application «memory manager» must cope with this while minimizing the total CPU overhead, interactive pause times, and the total memory used.

While the operating system may create the illusion of nearly infinite memory, it is a complex task to manage application memory so that the application can run most efficiently. Ideally, these problems should be solved by tried and tested tools, tuned to a specific application.

The Memory Management Reference is mostly concerned with application memory management.

See also: «automatic memory management»; «manual memory management».

Other links:

Memory Management Unit (for full details, see «MMU»)

The MMU (Memory Management Unit) is a hardware device responsible for handling «memory(2)» accesses requested by the main processor.

memory manager

The memory manager is that part of the system that manages «memory(2)», servicing «allocation» requests, and «recycling» memory, either «manually» or «automatically».

The memory manager can have a significant effect on the efficiency of the program; it is not unusual for a program to spend 20% of its time managing memory.

Similar terms: «allocator»; «collector(1)».
See also: «memory management».

memory mapping (also known as file mapping)

Memory mapping is the technique of making a part of the «address space» appear to contain an "object", such as a file or device, so that ordinary «memory(2)» accesses act on that object.

The object is said to be mapped to that range of addresses. (The term "object" does not mean a program «object». It comes from UNIX® terminology on the «mmap»(2) man page.)

An address space with a range mapped to part of an object
Diagram: An address space with a range mapped to part of an object

Memory mapping uses the same mechanism as «virtual memory(1)» to "trap" accesses to parts of the «address space», so that data from the file or device can be «paged in» (and other parts «paged out») before the access is completed.

Historical note: File mapping is available on most modern UNIX® systems, and also on recent versions of the Windows® operating system such as Windows 95® and Windows NT®. However, it has a much longer history. In Multics, it was the primary way of accessing files.

See also: «mapped».

memory protection (for full details, see «protection»)

Many operating systems support protection of «memory(2)» «pages». Individual pages may be protected against a combination of read, write or execute accesses by a process.

misaligned (for full details, see «unaligned»)

An «address» is unaligned or misaligned if it does not comply with some «alignment» constraint on it.

miss

A miss is a lookup failure in any form of «cache(3)», most commonly at some level of a «storage hierarchy», such as a «cache(1)» or «virtual memory(1)» system.

The cost of a miss in a virtual memory system is considerable -- it may be five orders of magnitude more costly than a hit. In some systems, such as multi-process operating systems, other work may be done while a miss is serviced.

Opposites: «hit».
See also: «miss rate».

miss rate

At any level of a «storage hierarchy», the miss rate is the proportion of accesses which «miss».

Because misses are very costly, each level is designed to minimize the miss rate. For instance, in «caches(1)», miss rates of about 0.01 may be acceptable, whereas in «virtual memory(1)» systems, acceptable miss rates are much lower (say 0.00005). If a system has a miss rate which is too high, it will spend most of its time servicing the misses, and is said to «thrash».

Miss rates may also be given as a number of misses per unit time, or per instruction.

Opposites: «hit rate».

mmap

mmap is a system call provided on many UNIX® systems to create a «mapping» for a range of «virtual addresses».

MMU (also known as Memory Management Unit)

The MMU (Memory Management Unit) is a hardware device responsible for handling «memory(2)» accesses requested by the main processor.

This typically involves translation of «virtual addresses» to «physical addresses», «cache(1)» control, bus arbitration, «memory protection», and the generation of various exceptions. Not all processors have an MMU.

See also: «virtual memory(1)»; «page fault»; «segmentation violation».

mostly-copying garbage collection, mostly copying garbage collection

A type of «semi-conservative» «tracing garbage collection» which permits «objects» to «move» if no «ambiguous references» point to them.

The techniques used are a hybrid of «copying garbage collection» and «mark-sweep».

Mostly-copying garbage collectors share many of the benefits of copying collectors, including «compaction». Since they support ambiguous references they are additionally suitable for use with uncooperative compilers, and may be an efficient choice for multi-threaded systems.

Related publications:


mostly-exact garbage collection (for full details, see «semi-conservative garbage collection»)

A variant of «conservative garbage collection» which deals with «exact references» as well as «ambiguous references».

mostly-precise garbage collection (for full details, see «semi-conservative garbage collection»)

A variant of «conservative garbage collection» which deals with «exact references» as well as «ambiguous references».

moving garbage collector (also known as moving memory manager)

A memory manager (often a «garbage collector») is said to be moving if «allocated» «objects» can move during their lifetimes.

Relevance to memory management: In the garbage collecting world this will apply to «copying» collectors and to «mark-compact» collectors. It may also refer to «replicating» collectors.

Similar terms: «copying garbage collection».

moving memory manager (for full details, see «moving garbage collector»)

A memory manager (often a «garbage collector») is said to be moving if «allocated» «objects» can move during their lifetimes.

mutable

Any «object» which may be changed by a program is «mutable». Opposite of «immutable».

Opposites: «immutable».

mutator

In a «garbage-collected» system, the part that executes the user code, which «allocates» «objects» and modifies, or mutates, them.

For purposes of describing «incremental garbage collection», the system is divided into the mutator and the «collector(2)». These can be separate threads of computation, or interleaved within the same thread.

The user code issues allocation requests, but the allocator code is usually considered part of the collector. Indeed, one of the major ways of scheduling the other work of the collector is to perform a little of it at every allocation.

While the mutator mutates, it implicitly «frees» «storage» by overwriting «references».

Historical note: This term is due to Dijkstra et al.

Opposites: «collector(2)».

Related publications:



N

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

natural alignment

Natural alignment is an «alignment» constraint such that all «objects» must be aligned to an address that is a multiple of their size.

Natural alignment is not usually required for objects larger than a «word» or «grain», which usually only need to be word- or grain-aligned.

See also: «alignment»; «padding».

nepotism

In «generational garbage collection» nepotism is the tendency for «dead» «objects» in old «generations» to preserve younger dead objects that are referenced by them. In other words, dead parents can cause their children to get promoted.

This happens when an object gets «promoted» to an old generation and dies there, but does not get «reclaimed» because the generation it is in does not get considered for garbage collection very often. The old object might refer to objects in younger generations that are also dead; until the old object is reclaimed the younger objects will be preserved by virtue of the «reference» from the older, assumed alive, object.

This is a form of «floating garbage» introduced by partitioning the objects into generations.

next fit

A variant of the «first fit» «allocation mechanism» that uses a roving pointer on a circular «free block chain». The pointer is advanced along the chain when searching for a fit. Thus each allocation begins looking where the previous one finished. The rationale is to avoid creating an accumulation of small fragments at the head of the free block chain, which would have to be examined on every allocation.

There are several variants, according to the order of blocks on the free block chain. The most common variant is address-ordered next fit.

This has a tendency to spread related objects out in memory, and also gives quite poor «locality» for the allocator (as the roving pointer rotates around memory, the free blocks touched are those least-recently used).

See also: «first fit»; «allocation mechanism».

Related publications:


node

In a «graph», a node is a representation of an «object» at the junction of zero or more «edges».

Opposites: «edge».
See also: «graph».

nursery generation (for full details, see «nursery space»)

In «generational garbage collection», the nursery «generation» or space is the area used for new «allocation».

nursery space (also known as nursery generation)

In «generational garbage collection», the nursery «generation» or space is the area used for new «allocation».

The size of the nursery space must be chosen carefully. Often it is related to the size of «physical memory(1)».


O

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

object (also known as cell)

In «memory management», we use the term object or cell to mean a contiguous «block» of «memory(2)» forming a single logical structure.

Objects are the units of «allocation», «deallocation», etc. No connection to an object-oriented system is implied.

off-white

In a «treadmill» «garbage collector», the «color» off-white is used to describe «objects» which are «free(3)».

Opposites: «white»; «gray»; «black».
See also: «treadmill»; «color».

one-bit reference count

The one-bit «reference count» is a heuristic mechanism that lets a program test, at low cost, whether an «object» is «dead».

The one-bit reference count is a special case of the «limited-field reference count». A single bit in an object, called the MRB (Multiple Reference Bit), is cleared when the object is «allocated». Whenever another «reference» to the object is created, the bit is set. Thus, MRB=0 indicates that there is exactly one reference to the object, and MRB=1 indicates that there may be more than one reference to the object.

The MRB can be stored in the reference rather than in the object; doing so reduces the number of memory accesses due to MRB checking and setting. When a reference is copied, the copy's MRB is set. If the MRB in the old reference is 0, it also needs to be set. Setting the MRB in the old reference requires that the program knows the location the old reference came from, and that it can prove that location has not since been overwritten with other data.

The one-bit reference count is used by a compiler to augment an object lifetime analysis. When compile-time analysis predicts that a particular object may be dead (typically because the variable that references the object is dead), the compiler can generate code that will check the object's MRB at run-time. If the MRB is 0, then the object is dead.

Using a one-bit reference count does have a cost: the MRB uses space that could sometimes be put to other use, and the MRB must be set every time the number of references to the object increases. The one-bit reference count is cheaper than other kinds of reference counting, however, since the space cost is only one bit and the reference count is not adjusted when references are destroyed.

Historical note: The one-bit reference count was suggested by Friedman and Wise The One-Bit Reference Count. Storing the MRB in the reference was suggested by Stoye, Clarke, and Norman Some Practical Methods for Rapid Combinator Reduction.

Related publications:


out-of-band header

In some «memory managers», each «allocated» «block» has additional information (such as the size of the block or a «tag») stored in a separate block; this is called an out-of-band header.

Opposites: «in-band header».

overcommit

In some circumstances, although a range of «virtual addresses» has been «mapped» as far as the user program is concerned, the «physical storage» might not be allocated until it is accessed. This is called overcommitting.

Overcommitting shares «swap space» resources more flexibly, especially when crude «suballocators» are involved, but it can lead to an out-of-resource error during a «memory(2)» access; few environments deal with this situation gracefully.

UNIX® systems such as IRIX® and AIXTM can do this on «sbrk» and «mmap» calls.

overwriting error (also known as bounds error)

An overwriting or bounds error occurs when the programmer intends his program to write to a particular «block» of «memory(1)», but a program error causes the program to write outside the bounds of that block.

See also: «fencepost».


P

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

padding

Padding is redundant «memory(2)» within the memory «allocated» to an «object». It is usually inserted because of «alignment» restrictions on the fields of the object or on the object itself.

Padding is a form of «internal fragmentation».

page

A «virtual memory(1)» system usually deals with «memory(1)» «blocks» of fixed size as units for «paging». These are known as pages.

Pages are often 4 «kB» or 8 kB in size. This size is determined by the addressing hardware of the machine.

page fault, page-fault

An exception when accessing «virtual memory(1)», usually resulting in a «page» being fetched from disk.

A page fault is an exception occurring during the translation of «virtual addresses» to «physical addresses». "Page fault" usually means an access to a page that has been «paged out» and hence requires fetching from disk, but it is sometimes also used to mean «invalid page fault» or «protection fault».

See also: «paging»; «paged in»; «paged out»; «read fault»; «write fault».

page marking, page-marking

Page marking is a form of «card-marking» where the «card» is the same size as a «page»

page protection (for full details, see «protection»)

Many operating systems support protection of «memory(2)» «pages». Individual pages may be protected against a combination of read, write or execute accesses by a process.

page table

In a «virtual memory(1)» system, it is common to map between «virtual addresses» and «physical addresses» by means of a data structure called a page table.

The «page» number of an address is usually found from the most significant bits of the address; the remaining bits yield the offset of the «location» within the page. The page table is normally indexed by page number and contains information on whether the page is currently in «main memory», and where it is in main memory or on disk.

Conventional page tables are sized to the virtual «address space» and store the entire virtual address space description of each process. Because of the need to keep the virtual-to-physical translation time low, a conventional page table is structured as a fixed, multi-level hierarchy, and can be very inefficient at representing a sparse virtual address space, unless the allocated pages are carefully aligned to the page table hierarchy.

See also: «inverted page table».

paged in

In a «virtual memory(1)» system, «memory(2)» is described as paged in if it is available in «physical memory(1)».

Similar terms: «swapped in».
Opposites: «paged out».
See also: «paging».

paged out

In a «virtual memory(1)» system, «memory(2)» is described as paged out if it is not available in «physical memory(1)».

Similar terms: «swapped out».
Opposites: «paged in».
See also: «paging».

paging

In a «virtual memory(1)» system, paging is the act of transferring «pages» between «physical memory(1)» and «backing store» (usually disk).

When pages need to be paged out, a heuristic is used to select ones that will not be needed soon; "least recently used" is a popular one.

Similar terms: «swapping».
See also: «paged in»; «paged out».

palimpsest

A «block» of «memory(2)» that has been «allocated», «freed» (or «reclaimed»), and then allocated again. Such memory may contain data from the previous use if portions of it remain uninitialised.

This commonly occurs on the «stack», especially if the compiler allocates large «stack frames» in anticipation of allocating data structures on the stack.

If the palimpsest is being «scanned» «conservatively», such left-over data may cause «unreachable» «objects» to appear «reachable» and thus become «floating garbage». If it is scanned «precisely», such left-over data, if treated as «pointers», is a bug.

parallel garbage collection (also known as concurrent garbage collection)

A parallel or concurrent «collector(2)» executes simultaneously with the «mutator», usually on a multi-processor machine.

Concurrent «GC» must cope with the mutator changing «objects» while collection occurs. The problem is similar to that of «incremental GC», but harder. The solution typically involves «barriers(1)».

Similar terms: «incremental».
See also: «replicating garbage collector».

Related publications:


perfect fit

If an «allocation» request is satisfied exactly from a «free block» with no «fragmentation», this is said to be a «perfect fit».

See also: «free block»; «allocation mechanism»; «best fit».

phantom reachable, phantomly reachable

In JavaTM, an object is phantom reachable if it is neither «strongly» nor «softly» nor «weakly reachable» and has been «finalized» and there is a path from the «roots» to it that contains at least one «phantom reference».

When the Java «collector(1)» determines that an object is phantom reachable, the «reference objects» containing the phantom references are enqueued.

The Java specification says that the phantom reference is not cleared when the reference object is enqueued, but actually, there's no way in the language to tell whether that has been done or not. In some implementations, JNI weak global references are weaker than phantom references, and provide a way to access phantom reachable objects.

See also: «reachability».

Other links:

phantom reference

In JavaTM terminology, phantom reference is used to mean a «reference» encapsulated in a «reference object» of class PhantomReference.

Phantom references form one of three kinds of «weak reference(1)» in Java. They are handy for performing clean-ups after an object has «died» and been «finalized».

See also: «phantom reachable».

Other links:

physical address (also known as absolute address)

Physical «addresses» are used to index into «physical memory(1)». On some systems, they are called absolute addresses.

In a «virtual memory(1)» system the application program handles «virtual addresses» and these are translated to physical addresses by the «MMU».

Opposites: «virtual address».

physical address space

The physical «address space» is the space of «physical addresses».

Opposites: «virtual address space».

physical memory(1) (also known as real memory(2))

Physical memory is «memory(1)» that is wired to directly to the processor, addressable by «physical address».

This term is basically synonymous to «main memory», but is used in contrast to «virtual memory(1)» and «backing store».

While modern computers usually have lots of «virtual memory(1)», performance is still closely related to the quantity of physical memory available. If a system has insufficient physical memory, it may «thrash».

Similar terms: «main memory».

physical memory(2) (also known as physical storage)

Physical memory is «memory(1)» on physical storage devices, such as «RAM» or disks.

This term is often contrasted to «virtual address space» that might not be mapped to any actual storage.

Similar terms: «memory(1)».

physical storage (for full details, see «physical memory(2)»)

Physical memory is «memory(1)» on physical storage devices, such as «RAM» or disks.

pig in the python (also known as pig in the snake)

In a «generational» collector, when a large and long-lived «object» is «allocated» in «nursery space», collection effort will be wasted as that object survives and is «promoted» from «generation» to generation. This is especially noticeable in a «copying collector», where the large object will be copied many times. This difficulty is similar to that of a python which swallows its prey whole and is somewhat immobilized as it digests it.

Modern collectors permit objects to be allocated directly into appropriate generations or pools to avoid this problem. Long-lived objects can be allocated directly into long-term generations. Large objects can be allocated directly into pools with special support for large objects (such as copying by remapping, incremental copying, or not copying at all).

See also: «generational garbage collection».

pig in the snake (for full details, see «pig in the python»)

In a «generational» collector, when a large and long-lived «object» is «allocated» in «nursery space», collection effort will be wasted as that object survives and is «promoted» from «generation» to generation. This is especially noticeable in a «copying collector», where the large object will be copied many times. This difficulty is similar to that of a python which swallows its prey whole and is somewhat immobilized as it digests it.

placement policy (for full details, see «allocation policy»)

The concrete policy used by an «allocator» for choosing a «free block» to satisfy an «allocation» request.

pointer

Pointer data types represent a reference to an «object» or a «location».

Pointers may be specialized by the type of the object referred to.

Typically, pointers are represented by an «address», but they can be more complicated when they need to carry more information, e.g., when the referent is smaller than a «word», an offset within the word might be needed.

Similar terms: «reference»; «address».
See also: «tag».

precise garbage collection (for full details, see «exact garbage collection»)

«Garbage collection» is exact (or precise) if it deals only with «exact references».

precise reference (for full details, see «exact reference»)

An exact or precise or sure reference is a value the «collector(1)» knows is a «reference».

precise root (for full details, see «exact root»)

An exact or precise root is a «root» that contains only «exact references».

premature free (also known as use after free)

A premature free or use after free occurs when «memory(2)» is «deallocated», but is later accessed.

Under «manual memory management», this usually occurs when one part of a program decides it has finished using a memory «block», and is unaware that another part of the program is still using it. This is rare under «automatic memory management».

See also: «double free».

premature promotion (for full details, see «premature tenuring»)

When a short-lived «object» «allocated» in a «generational garbage collector» is «promoted» (due to poor timing) into a less-frequently collected «generation». This prematurely tenured object may become «garbage» very soon after promotion, but will not be «reclaimed» for some time because it is now in a less frequently collected generation.

premature tenuring (also known as premature promotion)

When a short-lived «object» «allocated» in a «generational garbage collector» is «promoted» (due to poor timing) into a less-frequently collected «generation». This prematurely tenured object may become «garbage» very soon after promotion, but will not be «reclaimed» for some time because it is now in a less frequently collected generation.

This problem is essentially due to quantization error -- all objects in a generation are treated as if they have the same age, even though they range from as old as the previous promotion cycle to new-born.

Modern «collectors(1)» offer several remedies for premature tenuring: If the client program knows that it is entering a phase that will create many short-lived objects, it can forestall all promotion until it knows it is done with those objects -- thus no objects will be prematurely promoted, they will all be seen as garbage. Another solution is to create «buckets» within generations to more accurately classify objects by age and only promote those which have reached a certain minimum.

primary storage (for full details, see «main memory»)

The main memory (or primary storage) of a computer is «memory(1)» that is wired directly to the processor, consisting of «RAM» and possibly «ROM».

promotion (also known as tenuring)

Promotion or tenuring is the act of moving an «object» from its current «generation» to an older one (one that contains objects that are expected to survive longer).

"Tenuring" is used particularly about promotion to the oldest generation.

See also: «generational garbage collection».

protection (also known as memory protection, page protection)

Many operating systems support protection of «memory(2)» «pages». Individual pages may be protected against a combination of read, write or execute accesses by a process.

A process which attempts a protected access will trigger a «protection fault». Protection is typically implemented in hardware by the «MMU» as part of the support for «virtual memory(1)» .

Pages can be protected for a number of reasons: a «generational» or «incremental» «garbage collector» may want to place «barriers(1)» on pages; an operating system may want to protect pages for security, or to implement "copy-on-write" or "demand-zero-filled" pages.

See also: «read fault»; «write fault».

Related publications:


protection exception (for full details, see «protection fault»)

A protection fault is an exception or trap which occurs when a process attempts to access «memory(2)» which has been «protected».

protection fault (also known as protection exception, protection violation)

A protection fault is an exception or trap which occurs when a process attempts to access «memory(2)» which has been «protected».

Relevance to memory management: Some «garbage collectors» use handlers for protection faults to provide «barriers(1)».

See also: «segmentation violation»; «General Protection Fault».

protection violation (for full details, see «protection fault»)

A protection fault is an exception or trap which occurs when a process attempts to access «memory(2)» which has been «protected».


Q

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

quadword

A quadword is a unit of memory consisting of four adjacent «words».

In digital's Alpha architecture, a quadword for 64 bits is actually the natural word size, but the term word is still used for the 16-bit unit, for compatibility with PDP-11.

See also: «doubleword»; «longword».


R

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

RAM, random access memory

RAM (Random Access Memory) is a type of «physical memory(2)» that can be read from and written to.

Similar terms: «main memory».
See also: «ROM»; «static RAM»; «dynamic RAM».

raw (for full details, see «unwrapped»)

A value is unwrapped or raw if it is not encoded with type information.

reachable

An «object» is reachable if it is «referred» to by a «root», or is referred to by a reachable object; that is, if it can be reached from the roots by following «references».

Reachability is used as an approximation to «liveness» in «tracing garbage collection».

In JavaTM, the «reference objects» together with ordinary references and «finalization» generate a hierarchy of reachability that guides the «collector(1)» on what to do when an object is about to «die». There are six strengths:

Basically, an object is only as reachable as the weakest link in the strongest path from the roots. Note that the Java specification's description of the reachabilities is a bit patchy, but that's what it intends. It is unspecified where Java Native Interface's weak global references fit into this.

Similar terms: «live».
Opposites: «unreachable».

Other links:

read barrier, read-barrier

A read «barrier(1)» is a block on reading from certain «memory(2)» «locations» by certain threads or processes.

Relevance to memory management: Read barriers are used for «incremental» or «concurrent» «garbage collection».

See also: «write barrier».

read fault

An exception which occurs when reading from an address in «virtual memory(1)».

This is probably either a «page fault», an «invalid page fault» or a «protection fault».

Similar terms: «segmentation violation».
See also: «write fault».

real memory(1)

A system with no «virtual memory(1)» capability can be said to have real memory.

Historical note: On older architectures, programs could only directly access data in real memory. Where this was inefficient, they had to store data on disk, and sometimes had alternate portions of program image called overlays.

Opposites: «virtual memory(1)».

real memory(2) (for full details, see «physical memory(1)»)

Physical memory is «memory(1)» that is wired to directly to the processor, addressable by «physical address».

reclaim

Reclaiming an «object» or the «storage» occupied by it is making it available for reuse after the object is no longer needed.

This word is usually used only in connection with «automatic memory management».

Similar terms: «recycle».

recycle

Recycling «storage» means making it available for reuse after it has been occupied by an «object» that is no longer needed.

In simple cases, this might simply involve adding a «memory(2)» «block» to the «free list». Another possibility is «unmapping» memory so that the «backing store» can be allocated to another process.

Similar terms: «reclaim».

Other links:

reference

In memory management, a reference is the general term for a link from one «object» to another. Some programming languages have more specific meanings for the term.

The terms "«pointer»" and "reference" are often interchangeable, but some programming languages differentiate the two in subtle ways.

Similar terms: «address»; «pointer».

reference counting

Reference counting systems perform «automatic memory management» by keeping a count in each «object», usually in a «header», of how many «references» there are to the object. Objects to which there are no references cannot be accessed by the «mutator»; they are therefore «dead» and may be «reclaimed».

The reference count is incremented for each new reference, and is decremented if a reference is overwritten, or if the referring object is recycled. If a reference count falls to zero, then the object is no longer required and can be recycled.

There are four main problems with simple reference counting:

Garbage with non-zero reference counts
Diagram: Garbage with non-zero reference counts

Reference counting has the advantage that it can reclaim objects promptly, and for this reason it is often used to reclaim non-cyclic data structures in file systems, databases and operating system kernels. When there is a possibility of cyclic data structures, reference counting is sometimes used together with a «tracing garbage collector» that runs infrequently. Such combinations are generally less efficient than using a tracing collector by itself, but the promptness of reference counting may be important.

Pauses due to reference counting are typically fairly short, and it may be appropriate as a form of «incremental garbage collection». But removing a single reference may cause the recycling of a large number of objects at once, so it is not suited to real-time systems where minimum pause times must be guaranteed. There are more complex variations of the technique that address this problem.

Reference counting is often used because it can be implemented without any support from the language or compiler. In C++ this can be encapsulated in a class, using a «smart pointer». However, it would normally be more efficient to use a tracing garbage collector instead. The performance of reference counting can be improved substantially with compiler support, using refinements such as «deferred reference counting», which has been successfully used in Smalltalk and other languages.

Despite the problems, reference counting is often used for «distributed garbage collection». This is because refinements such as «weighted reference counting» require less inter-process communication than «tracing».

See also: «limited-field reference count»; «one-bit reference count».

reference object

In JavaTM, a reference object (java.lang.ref.Reference) encapsulates a «reference» to some other object, in order to make the «garbage collector» handle it specially. In particular, a Java program can use this to detect when the referent becomes «unreachable».

Basically, the encapsulated reference is a «weak reference(1)»; it will be cleared by the «collector(1)» when all other references to the referent have disappeared. However, in order to better control what happens at the end of an object's «lifetime», Java 1.2 provides three classes of reference objects, each with its own peculiarities: SoftReference, WeakReference, and PhantomReference. Each of these classes has its uses in managing memory. The reference objects together with ordinary references and «finalization» generate a hierarchy of «reachability» (q.v.) that guides the collector on what to do when an object is about to «die».

A reference object can be registered with a queue, and it will be enqueued when the collector determines that the referent is «softly», «weakly» or «phantom reachable», as the case may be. A program can use these queues to perform some action when an object is dying. This allows finer control than the older «finalization» mechanism alone.

Historical note: This feature was introduced in Java 1.2 (confusingly, part of the JavaTM 2 Platform).

See also: «soft reference»; «weak reference(2)»; «phantom reference».

Other links:

Related publications:


region inference

Region inference is a technique for determining when «objects» become «dead» (even if they are «reachable») by a static analysis of the program.

Region inference infers a region for each object. When a region dies, all the objects in it are known to be «dead», whether reachable or not. Regions obey a strict «stack» discipline; that is, when a region dies, all younger regions also die. In this way, region inference occupies a middle ground between «stack allocation» and «heap allocation».

Related publications:


register

Definition not yet available. Please see our feedback page for submission information.

register set partitioning

Run-time systems for «garbage-collected» languages sometimes partition the set of machine «registers» a priori into two categories: those always «traced» and updated by the «garbage collector» and those ignored by it.

The former are always maintained in a format understood by the collector; the latter are never used to hold «references» to collectable «objects». More complicated schemes are also possible.

This partitioning provides a separation of concerns between the compiler and the «garbage collector». The compiler can generate code that produces values the garbage collector would not be able to handle (say, because they have no «tags»), as long as those values are kept in the ignored registers. The garbage collector can trust that the registers it looks at always contain valid data, and can perform «exact garbage collection».

Register set partitioning increases the demand for registers (register pressure), but may reduce the amount of «boxing» needed.

relocation

Relocating means moving data from one location to another and updating all «references».

Relocation is often performed to avoid «external fragmentation».

Program loading sometimes relocates code and «static» data.

Similar terms: «moving».
See also: «compaction»; «moving memory manager».

remembered set

A remembered set is the technique of keeping a separate list of interesting «references» between two sets of «objects», so you don't have to find them by «scanning».

Many «memory management» algorithms depend on partitioning the objects and require special handling for references between partitions. Keeping track of such references in a remembered set eliminates the need to scan the originating partition to find them.

A typical use in «generational garbage collection» is remembering «references» from an older «generation» to a younger one.

Similar terms: «entry table(2)».

Related publications:


replicating garbage collector

A variant of «copying garbage collection», which does not destroy the original «object» when making a copy.

This is useful in an «incremental» or «concurrent» «collector(1)», as no «read-barrier» is required; the «mutator» can continue to use old objects. The collector uses a «write-barrier» to replicate the writes to the new copies.

See also: «copying garbage collection»; «broken heart».

Related publications:


reserved

In a «virtual memory(1)» system, it is usually possible to hold range of «virtual addresses» reserved without making it «mapped».

Reserving addresses prevents other components of the program using the same addresses, without consuming «swap space». This technique is often used in «BIBOP» schemes, where one might want to reserve a large amount of «address space» but only sparsely map it.

On some systems there are special calls for reserving; on others one can create «mappings» that don't need «backing store», e.g., on some Unix® systems, «mmap» /dev/zero with no access.

See also: «mapping».

resident

In a «cache(2)» system, that part of the cached storage which currently has a copy in the cache is called resident. Ideally, the «working set» should be resident.

See also: «cache(2)»; «storage hierarchy»; «resident set».

resident set

In a «virtual memory(1)» system, a process' resident set is that part of a process' «address space» which is currently in «main memory». If this does not include all of the process' «working set», the system may «thrash».

ROM, read-only memory

ROM (read-only memory) is a type of «physical memory(2)» that can be read from, but not written to. The contents of ROM are usually set in the factory.

See also: «RAM».

root

In «tracing garbage collection», a root holds a «reference» or set of references to «objects» that are a priori «reachable». The «root set» is used as the starting point in determining all reachable data.

Roots basically comprise the references in the state of the «mutator». Typical roots are global variables, other «static» data, and the «control stack».

See also: «weak root»; «strong root»; «ambiguous root»; «exact root».

root set

The root set is the collection of «roots» that the «mutator» declares to the «collector(2)».

See also: «garbage collection».


S

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

sbrk

sbrk is a UNIX® library function that adjusts the limit of the data segment; this limit is known as the break.

sbrk returns the previous value of the break, so sbrk(0) is a common idiom for getting the current value.

Note that, if you use «brk», you probably can't safely use sbrk as well, because it may store the last value of the break in a private variable.

scalar data type

A scalar data type is a type that is representable in a single dimension and whose objects have only magnitude as value.

Examples of scalar data types include: integers, floating-point numbers, enumerations, and characters.

Relevance to memory management: The objects of a scalar data type are «leaf objects». Scalar data types with bounded magnitude can be represented compactly using «value objects».

Historical note: Because compact representation solves many memory management issues, many older programming languages only offered bounded scalar data types. For example, the int type in C is defined to have a magnitude that can be represented by a «word».

See also: «vector data type»; «algebraic data type»; «value object»; «leaf object».

scan

The examination of an «object» or an area of «memory(2)» to find «references», typically as part of «tracing».

Scanning examines memory that has been decided to be non-«garbage», to find references to objects that have been «condemned».

scavenging garbage collection (for full details, see «copying garbage collection»)

Copying garbage collection is a kind of «tracing garbage collection» that operates by «relocating» «reachable» «objects» (this is sometimes called scavenging) and then «reclaiming» objects that are left behind, which must be «unreachable» and therefore «dead».

SDRAM

Synchronous Dynamic Random Access Memory. A high performance variant of «DRAM».

SDRAM uses an external clock signal to synchronize its data input and output. It is capable of achieving very high data rates for linear access to memory.

segmentation violation

A segmentation violation occurs when an attempt is made to access «memory(2)» whose «address» is well-formed, but to which access cannot be granted. This might be due to either a «protection fault» or an «invalid page fault».

The term is sometimes used more loosely as a synonym for any memory access error, including a «bus error».

Similar terms: «general protection fault»; «read fault»; «write fault».

segmented addressing

In segmented addressing, «addresses» are in two parts: a segment identifier and an offset into that segment.

Each segment has a base address and a limit. If the offset is greater than the limit, the address is invalid (see «segmentation violation»). Otherwise, the offset is added to the segment's base address, giving the unsegmented address. Segment identifiers may be implicit; for instance, they may be obtained from a current segment register.

Segmentation may be layered on top of «virtual memory(1)», in which case the unsegmented address is a «virtual address», or not, in which case it is a «physical address».

Note that, in segmented architectures, you can have a two-dimensional «address space».

Segments are a feature of some processor architectures and operating systems. This description does not cover all possible variations on segmentation.

Historical note: Segment terminology may be used on unsegmented systems for historical reasons. For instance, UNIX processes have text segments, even when running on an unsegmented system.

Opposites: «linear addressing».

segregated fit

One of the «segregated free list» class of «allocation mechanisms». There is an array of «free lists», each holding «free blocks» of a particular range of sizes. The «allocator» identifies the appropriate free list and allocates from it (often using a «sequential fit» mechanism such as «first fit»). If this fails, a larger block is taken from another list and split.

The details of the mechanism depend on the division of sizes between free lists. See «exact segregated fit» and «strict segregated fit».

This implements a «good fit» «allocation policy».

See also: «segregated free list»; «allocation mechanism»; «free list»; «exact segregated fit»; «strict segregated fit».

Related publications:


segregated free list, segregated free-list

A class of «allocation mechanism» which divides the «free list» into several subsets, according to the size of the «free blocks». A «freed» or «coalesced» block is placed on the appropriate list. An allocation request is serviced from the appropriate list.

This class of mechanism implements a «good fit» or «best fit» policy.

Variations within this class include «simple segregated storage», «segregated fit», and «buddy systems».

Related publications:


semi-conservative garbage collection (also known as mostly-precise garbage collection, mostly-exact garbage collection)

A variant of «conservative garbage collection» which deals with «exact references» as well as «ambiguous references».

For example, references from the «root set» might be ambiguous, but «objects» on the «heap» might be fully described and precisely «scanned».

See also: «mostly-copying garbage collection».

Related publications:


semi-space

When an area of «memory(2)» is divided into two parts for the purposes of «copying garbage collection», the parts are known as semi-spaces, or sometimes just spaces.

Each semi-space is a contiguous area of memory. Semi-spaces are usually used for «two space collection», but can be used for «generational collection».

The semi-space where «objects» reside at the start of the collection is known as the old semi-space; the new semi-space is where objects will reside, and where new objects will be «allocated», when the collection is complete.

See also: «two space collector».

semi-space collector (for full details, see «two-space collector»)

A two-space «collector(1)» is a simple form of a «copying garbage collector». The available «memory(2)» is divided into two halves, called «semi-spaces». «Objects» are allocated in one semi-space until it is full. The «reachable» objects are then copied into the other semi-space (usually using a «Cheney scan») and the old semi-space is «reclaimed». «Allocation» continues in the new semi-space until it is full, at which point the process is repeated in reverse.

sequential fit

A class of «allocation mechanisms» that maintain the «free list» as a single linear list of «free blocks» (a «free block chain»). Sequential fit mechanisms include «first fit» and «next fit».

To quote Dynamic Storage Allocation: A Survey and Critical Review:

The list is often doubly-linked and/or circularly linked. Typically, sequential fit algorithms use Knuth's boundary tag technique, and a doubly-linked list to make «coalescing» simple and fast. ... In considering sequential fits, it is probably most important to keep strategy and policy issues in mind. The classic linear-list implementations may not scale well to large «heaps», in terms of time costs; as the number of free blocks grows the time to search the list may become unacceptable. More efficient and scalable techniques are available, using totally or partially ordered trees, or «segregated fits».

See also: «bitmapped fit»; «indexed fit».

Related publications:


sequential store buffer (also known as SSB)

A sequential store buffer is a technique for dividing the cost of a «write-barrier» by remembering which «objects» are modified and updating «remembered sets» (and so on) at a later stage.

This turns out to be extremely efficient on pipelined architectures with branch prediction.

shared memory

«Memory locations» are shared if they are in the range of multiple «address spaces».

simple object

In the PostScript® language, simple objects are the «unboxed» objects.

Unlike a «composite object», a simple object contains all its data in the object itself.

Similar terms: «unboxed».
Opposites: «composite object».

simple segregated storage

A «segregated free list» «allocation mechanism» which divides «storage» into «pages» or other areas and only allocates «objects» of a single size, or small range of sizes, within each area. This makes allocation fast and avoids «headers», but may lead to high «external fragmentation», as unused parts of areas cannot be reused for other object sizes.

Related publications:


smart pointer

A smart pointer is an instance of a C++ class that encapsulates a «pointer» and performs «reference counting».

By overloading certain operators it is possible for the class to present the illusion of being a pointer, so that operator*, operator->, etc. can be used as normal. Reference counting allows the objects that are referred to using the smart pointer class to have their «storage» automatically «reclaimed» when they are no longer «referenced». It is a common technique used when trying to solve «memory management» problems in C++ applications.

However, reference counting is not always an appropriate memory management technique and smart pointers can be hard to implement properly in C++. A «tracing garbage collector» might be worth considering.

Related publications:


snap-out (also known as transport snap-out)

In a «copying collector», when there is a «reference» to an «object» that was «condemned», but has been «transported», snap-out is the adjustment of that reference to point to the preserved copy.

Typically the first transport leaves a «forwarding pointer» that enables the snap-out.

Snap-out
Diagram: Snap-out

See also: «broken heart».

snapshot-at-the-beginning, snapshot at the beginning

Snapshot-at-the-beginning algorithms for «tracing», «incremental GC» note changes made by the «mutator» to the «graph» of «objects» and update the «collector(2)» state to make it trace relevant «edges» that the mutator deletes.

In order for the collector to miss a «reachable» «object», the following two conditions need to hold at some point during tracing:

  1. The mutator stores a «reference» to a «white» object into a «black» object.
  2. All paths from any «gray» objects to that white object are destroyed.

Snapshot-at-the-beginning algorithms ensure the second condition cannot occur, by causing the collector to process any reference that the mutator overwrites and that might be part of such a path.

They are so called because they keep track of references that existed at the beginning of the «collection cycle». Note that this does not mean all modifications need to be seen by the collector, only those needed to complete tracing without missing a reachable object (see Barrier techniques for incremental tracing for details), nor does it mean that it won't trace some references created during the collection.

Historical note: This distinction between incremental-update and snapshot-at-the-beginning was first introduced for write-barrier algorithms, but it applies to any type of tracing algorithm.

Opposites: «incremental-update».
See also: «tri-color marking»; «weak tri-color invariant»; «barrier(1)».

Related publications:


soft reference

In JavaTM terminology, soft reference is used to mean a «reference» encapsulated in a «reference object» of class SoftReference.

Soft references form one of three kinds of «weak reference(1)» in Java. They are handy for building «caches(3)» that are automatically flushed when memory is low.

See also: «softly reachable».

Other links:

softly reachable

In JavaTM, an object is softly reachable if it is not «strongly reachable» and there is a path from the «roots» to it that contains at least one «soft reference» but no «weak(2)» or «phantom references».

When the Java «collector(1)» determines that an object is softly reachable, it has the option of clearing the soft references involved, which will usually allow the object to be «recycled». The idea is that they will only be cleared if the process is running short of «memory(2)». If it is done, all soft references involved are cleared, so that the object is no longer softly reachable, and any affected «reference objects» which are registered with a queue are enqueued.

See also: «reachability»; «weakly reachable»; «phantom reachable».

Other links:

space leak (for full details, see «memory leak»)

A memory leak is where «allocated» «memory(2)» is not «freed» although it is never used again.

spaghetti stack (for full details, see «cactus stack»)

A cactus stack is a «stack» with branches. When diagrammed, its shape resembles that of a saguaro cactus.

split

To divide a «free block» into two smaller free blocks in the process of satisfying an allocation request.

Deciding when to split a block is an important aspect of an «allocation policy».

Opposites: «coalesce».
See also: «coalesce»; «allocation policy»; «free block».

SRAM (for full details, see «static memory(1)»)

Static «memory(2)» or static RAM (SRAM) is a type of «physical memory(2)» that does not need to be refreshed periodically to avoid losing state.

SSB (for full details, see «sequential store buffer»)

A sequential store buffer is a technique for dividing the cost of a «write-barrier» by remembering which «objects» are modified and updating «remembered sets» (and so on) at a later stage.

stack

A stack is a LIFO (last in, first out) collection: «objects» may be pushed onto the stack, and popped off it in reverse order of pushing.

When people say "the stack", they usually mean the «control stack» supported by the OS and/or the processor.

Relevance to memory management: «Stack allocation» is an important technique. Control stacks are central to the performance of the system and often require special handling.

Historical note: The terms "stack", "push", and "pop" are taken from the spring-loaded dish stack found in cafeterias and salad bars where removing the top plate causes the others to rise up, exposing the next one, and adding a plate causes the spring to compress, leaving only that plate accessible.

So originally, the latest item was the "top", "down the stack" meant towards earlier items, and "up" towards later ones, but today many use "up" and "down" in the opposite sense.

Similar terms: «control stack».
See also: «data stack»; «cactus stack».

stack allocation

Stack allocation means run-time «allocation» and «deallocation» of «storage» in last-in/first-out order.

Typically, stack allocation is performed on top of the main «stack», but one can have a separate «data stack» for this purpose as well, as in Forth, or even multiple ones, as in the PostScript® language.

Allocation and deallocation are typically fast, since they can be done simply by adding or subtracting the size of the «block» from the stack pointer.

Using only stack allocation, without heap allocation, is somewhat restrictive, as only objects whose size is known at compile-time can be returned from a procedure.

Some programming languages (such as some versions of Lisp and C) provide program-controlled stack «allocation» and «deallocation» of dynamic extent objects for efficiency, despite its being unsafe.

Similar terms: «automatic storage duration».
Opposites: «heap allocation»; «static allocation».
See also: «region inference»; «dynamic extent».

stack frame (also known as stack record)

A stack frame or record is an «activation record» that is stored on the «stack».

In a register-based architecture, where the current activation record may be partially stored in registers, there may be hardware instructions that facilitate storing registers on the stack when another activation record is made current. Such instructions may prescribe a particular layout for activation records.

Relevance to memory management: Hardware support for saving and restoring registers, for stacks and for stack addressing may limit or otherwise prescribe the size and type of data that can be stored in a stack frame. Knowledge of the layout of each stack frame may assist a «garbage collector» in finding «roots».

Similar terms: «activation record».
See also: «stack».

stack record (for full details, see «stack frame»)

A stack frame or record is an «activation record» that is stored on the «stack».

static allocation

Static allocation means «allocation» of «storage» before the program starts and retention until the end.

The locations of «objects» are basically decided at compile-time, although they might be «relocated» at load-time. This implies the sizes of the objects must be known then.

Using only static allocation is restrictive, as sizes of data structures can't be dynamically varied, and procedures cannot be recursive. However, it is also fast and eliminates the possibility of running out of memory. For this reason, this scheme is sometimes used in real-time systems.

Historical note: The first high-level language, Fortran, only had static allocation to begin with. Later languages usually offer heap and/or stack allocation, but static allocation is often available as an option.

Similar terms: «static storage duration».
Opposites: «stack allocation»; «heap allocation».
See also: «region inference»; «static memory(2)».

static memory(1) (also known as static RAM, SRAM)

Static «memory(2)» or static RAM (SRAM) is a type of «physical memory(2)» that does not need to be refreshed periodically to avoid losing state.

Static memory is typically faster than «dynamic memory», or requires essentially no power to preserve its state, but rarely both. These benefits result in static RAM being used for «cache(1)» memory, and also in portable, low-power applications (such as PDAs). It is, however, more expensive than dynamic RAM and requires more transistors, making dynamic RAM the choice for large amounts of memory (the «main memory» of desktop machines, for example).

Opposites: «dynamic memory».

static memory(2)

The «memory(2)» where «statically allocated» objects are stored is sometimes known as static memory. In the context of «garbage collection», the term is used mean memory used to store «static objects».

See also: «static storage duration».

static object

A static «object» is non-«moving». That is, it is not «relocated» by a «memory manager»; its «address» does not change.

static RAM (for full details, see «static memory(1)»)

Static «memory(2)» or static RAM (SRAM) is a type of «physical memory(2)» that does not need to be refreshed periodically to avoid losing state.

static storage duration

In C and C++, the static keyword applied to a file scope variable or function means it is local to the file; the static keyword applied to a function or a block scope variable means it is «allocated» and initialized once only.

Objects declared locally in blocks with the static keyword are «allocated» in «static memory(2)», and initialized once (usually by the compiler/linker) instead of each time the block is entered.

Static variables within functions retain their value between function invocations, and therefore must form part of the «root set» of any «collector(1)».

Opposites: «automatic storage duration».
See also: «lifetime».

sticky reference count (for full details, see «limited-field reference count»)

A «reference counting» technique whereby the field used to store the number of «references» to an «object» has a limited size. In particular, the field is not large enough to represent the maximum possible number of references to an object.

storage (for full details, see «memory(1)»)

memory or storage (or store) is where data and instructions are stored. For example, «caches(1)», «main memory», floppy and hard disks are all storage devices.

storage hierarchy (also known as memory hierarchy)

A typical computer has several different levels of «storage». Each level of storage has a different speed, cost, and size. The levels form a storage hierarchy, in which the topmost levels (those nearest the processor) are fastest, most expensive and smallest.

Levels typically include processor «registers», possibly some levels of «cache(1)», «main memory», and possibly some levels of «backing store».

Each level is commonly used as a «cache(2)» for the next level. For instance, «virtual memory(1)» systems use main memory as a cache for backing store.

Storage hierarchy with relative speed, cost, and typical size
Diagram: Storage hierarchy with relative speed, cost, and typical size

storage level

One level in a «storage hierarchy», for instance a «cache(1)», «main memory», «backing store», and so on.

See also: «storage hierarchy».

storage management (for full details, see «memory management»)

Memory management is the art and the process of coordinating and controlling the use of «memory(1)» in a computer system.

store(1)

To transfer data from a processor's «registers» to «memory(2)».

Store can also be used in the more general sense of transferring data from a part of the «memory hierarchy» that is fast to access to one that is slow to access.

STORE (or an abbreviation) is also commonly used in many processor architectures as the mnemonic for the machine code instructions that store data into memory.

Opposites: «load».

store(2) (for full details, see «memory(1)»)

memory or storage (or store) is where data and instructions are stored. For example, «caches(1)», «main memory», floppy and hard disks are all storage devices.

strict segregated fit

A «segregated fit» «allocation mechanism» which has only one block size on each «free list». A requested block size is rounded up to the next provided size, and the first block on that list is returned. The sizes must be chosen so that any block of a larger size can be «split» into a number of smaller sized blocks. «Buddy systems» are a special case of strict segregated fit allocators.

See also: «buddy system»; «segregated fit»; «segregated free list»; «allocation mechanism».

Related publications:


strong reference

In a «tracing garbage collector», a strong reference is a «reference» that keeps the «object» it refers to «alive».

A strong reference is the usual sort of reference; The term is usually used to draw a contrast with «weak reference(1)».

Opposites: «weak reference(1)».
See also: «strong root».

strong root

A strong root is a «root» such that all «references» in it are «strong references».

A strong root is the usual sort of root; The term is usually used to draw a contrast with «weak root».

Opposites: «weak root».

strong tri-color invariant, strong tri-colour invariant, strong tricolor invariant, strong tricolour invariant

The strong «tri-color invariant» is the property of a «reference» «graph» that there is no «edge» from a «black» «node» to a «white» node.

By preserving this property throughout «tri-color marking», a «tracing» algorithm can ensure that the «collector(2)» will not miss reachable objects, even if the «mutator» manipulates the graph during the collection. This invariant can also be used to ensure that a «copying garbage collector» doesn't confuse the mutator. Mutator actions might need to change the «color» of the nodes affected in order to preserve the invariant (see Barrier techniques for incremental tracing for details).

Algorithms using this invariant are «incremental-update» algorithms.

Similar terms: «tri-color invariant».
See also: «barrier(1)»; «weak tri-color invariant».

Related publications:


strongly reachable

In JavaTM, an object is strongly reachable, if there is a path from the «roots» to it that contains only «strong references», i.e., no «reference objects».

See also: «reachability»; «softly reachable»; «weakly reachable»; «phantom reachable».

Other links:

suballocator

A suballocator is an «allocator» functioning on top of another allocator.

Suballocators work by «allocating» large «blocks» and «splitting» them for use, or by «recycling» blocks locally.

Application programmers sometimes write their own suballocators when faced with an inefficient or inadequate «memory manager». Suballocators can take advantage of special knowledge of program behavior, but are less efficient in general than fixing the underlying allocator, mainly because «memory management» is a global issue for an application, and a global strategy can make a big difference. For example, different suballocators can interact catastrophically with each other and with the «virtual memory(1)» system, causing the application's memory requirements to grow unnecessarily due to «fragmentation».

subgraph

A subgraph S of a «graph» G is a graph such that all the «nodes» in S are also in G and all the «edges» in S are also in G; that is, it is a part of a graph.

sure reference (for full details, see «exact reference»)

An exact or precise or sure reference is a value the «collector(1)» knows is a «reference».

swap space

«Backing store» used by a «swapping» system.

See also: «swapping»; «backing store».

swapped in

A process or «page» is swapped in if it is available in «physical memory(1)». This usually applies to the entire program image.

Similar terms: «paged in».
Opposites: «swapped out».
See also: «swapping».

swapped out

A process or «page» is swapped out if it is not available in «physical memory(1)». This usually applies to the entire program image.

Similar terms: «paged out».
Opposites: «swapped in».
See also: «swapping».

swapping

Historically, swapping was the technique of moving entire program images to disk (or drum) and back into «physical memory(1)», an early form of «virtual memory(1)». Nowadays, it is used as a synonym for «paging».

Similar terms: «paging».
See also: «swapped in»; «swapped out».

sweeping

Sweeping is the second phase ("the sweep phase") of the «mark-sweep» algorithm (q.v.). It performs a sequential (address-order) pass over memory to «recycle» unmarked blocks.

Sweeping typically gathers all unmarked blocks into one or more «free lists».

See also: «marking».


T

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

tabling (for full details, see «caching(3)»)

Caching is a heuristic that stores answers to questions asked in the past in a cache or a table, in order that they may be more quickly answered in the future. This process is also called memoization and tabling (by the Prolog community).

tag

A tag is a piece of information associated with an «object» or «reference» that allows the representation of the object to be determined.

Tags are often used to represent types in the implementation of a dynamically-typed language. In statically-typed languages, types are usually implicit and not permitted to change at run-time, so tagging is rarely required.

One of the simplest forms of tag is a «word» at the beginning of the object that points to a block of information about the object's «format».

Example of a tag-word at the start of an object
Diagram: Example of a tag-word at the start of an object

Another common form of tagging is to «align» objects and keep information in the least significant bits of the «address».

Example of reference tagging, using the least significant bits
Diagram: Example of reference tagging, using the least significant bits

In C, when a structure contains a union, it is common to add a field to the structure to indicate which union member is currently being used. This field is known as a discriminator, and is a form of tag. Analogues occur in other languages, sometimes with compiler or run-time support.

See also: «tagged architecture»; «header».

Related publications:


tagged architecture

A tagged architecture is a hardware architecture where each memory «word» is divided into a "data" and a «tag» section. The data section is sufficiently large to contain a memory «address» and the tag section is used to describe how the data section is to be interpreted (that is, it encodes the type of the data).

Relevance to memory management: Tagged architectures greatly simplify the implementation of a memory manager because each word of memory is self-describing.

Historical note: The Lisp Machine is an example of a tagged architecture.

TB(1) (for full details, see «terabyte»)

A terabyte is 1024 «gigabytes», or 1099511627776 «bytes(1)».

TB(2) (for full details, see «TLB»)

The translation lookaside buffer or address translation cache is small piece of associative «memory(1)» within a processor which caches part of the translation from «virtual addresses» to «physical addresses».

tenuring (for full details, see «promotion»)

Promotion or tenuring is the act of moving an «object» from its current «generation» to an older one (one that contains objects that are expected to survive longer).

terabyte (also known as TB(1))

A terabyte is 1024 «gigabytes», or 1099511627776 «bytes(1)».

See «byte(1)» for general information on this and related quantities.

termination (for full details, see «finalization»)

In «garbage-collected» languages, it is often necessary to perform actions on some «objects» after they are no longer in use and before their «memory(2)» can be «recycled». These actions are known as finalization or termination.

thrash

A «cache(2)» is said to «thrash» when its «miss rate» is too high, and it spends most of its time servicing «misses». Thrashing is bad for performance, particularly «virtual memory(1)» thrashing, because the relative cost of a miss is so high: it may slow a machine down by a factor of a hundred or more.

Thrashing is typically caused by a process or system having a «working set» which is larger than its «cache(1)» or «main memory». It may also be caused by a failure of «cache policy». A system with an inflexible cache policy may thrash even when the working set is quite small.

For instance, a virtual memory system which has four megabytes of «physical memory(1)» but which has a working set of ten megabytes will «thrash» badly.

Related publications:


threatened set (also known as condemned set)

Condemned «objects» are those which are candidates for «recycling» within a «collection cycle».

At the start of a collection cycle, the «collector(1)» may choose to condemn some objects (the condemned set or threatened set) but not to condemn others (the «immune set»). Objects that are not condemned are assumed to be «alive» and behave as «roots» for the purposes of that collection cycle.

Many simple «tracing garbage collection» algorithms begin by condemning all objects, but «generational garbage collectors» will condemn individual «generations» or combinations of generations. Often young generations are condemned but older ones are not, because objects in older generations are less likely to have become «unreachable».

In collectors using «tri-color marking», at the start of a collection cycle the condemned set is exactly the set of objects that the collector colors «white».

Opposites: «immune set».

TLB, translation lookaside buffer (also known as TB(2), translation buffer, ATC, address translation cache)

The translation lookaside buffer or address translation cache is small piece of associative «memory(1)» within a processor which caches part of the translation from «virtual addresses» to «physical addresses».

In a «virtual memory(1)» system there is a translation from «virtual addresses» to «physical addresses». This translation can often be very large and complex and the data structures that implement the translation (often a «page-table») can be too large to store efficiently on the processor. Instead, a few elements of the translation are stored in the TLB; the processor can access the TLB extremely quickly. If a required translation for a particular virtual address is not present in the TLB then a TLB miss is taken and the address is resolved using the more general mechanism.

trace

In «tracing garbage collection», tracing is the process of following the «graph» from all «roots» to all «reachable» data.

Similar terms: «scan».

tracing garbage collection

Tracing garbage collection is «garbage collection» based on «reachability».

Tracing garbage collection relies on the fact that if an «object» is not «reachable», there is no way the «mutator» could ever access it, and therefore it cannot be «alive». In each «collection cycle», some or all of the objects are «condemned» and the «graph» is «traced» to find which of the condemned objects are reachable. Those that were not reachable may be «reclaimed».

translation buffer (for full details, see «TLB»)

The translation lookaside buffer or address translation cache is small piece of associative «memory(1)» within a processor which caches part of the translation from «virtual addresses» to «physical addresses».

transport

In a «copying collector», transporting is preventing an «object» in the «condemned set» from being collected by copying it and adjusting the «reference» by which it was discovered to point to the new copy.

See also: «scavenging»; «snap-out».

transport snap-out (for full details, see «snap-out»)

In a «copying collector», when there is a «reference» to an «object» that was «condemned», but has been «transported», snap-out is the adjustment of that reference to point to the preserved copy.

treadmill

Henry Baker has devised an «incremental» non-«moving» «garbage collector» that uses a circular doubly-linked list, called the treadmill, to implement «tri-color marking».

Every «object» is on the list. The list has four sections corresponding to «colors». The «black», «gray» and «white» sections are used for tri-color marking, and an additional «off-white» section is used for «free(3)» objects. The color of an object is changed by unlinking it from the list and relinking it to a different part of the list.

A treadmill
Diagram: A treadmill

Related publications:


tri-color invariant, tri-colour invariant, tricolor invariant, tricolour invariant

The term "tri-color invariant" is used to refer to any of a number of properties of a «reference» «graph» that are preserved throughout a «tri-color marking» algorithm to ensure the correctness.

There are two important ones: the «strong tri-color invariant» and the «weak tri-color invariant». When people say "the tri-color invariant" they probably mean the strong one.

Related publications:


tri-color marking, tri-colour marking, tricolor marking, tricolour marking

Tri-color marking is a «tracing garbage collection» algorithm that assigns a «color» («black», «white», or «gray») to each «node» in the «graph». It is basic to «incremental garbage collection».

Initially all nodes are colored white. The distinguished «root set» is colored gray. The «collector(2)» proceeds to discover the «reachable» nodes by finding an «edge» from a gray node to a white node and coloring the white node gray. Hence each tracing step involves choosing a gray node and graying its white children.

When all the edges from a gray node lead only to other gray (or black) nodes, the node is colored black. When no gray nodes remain, the reachable part of the graph has been discovered and any nodes that are still white may be «recycled».

The «mutator» is free to access any part of the graph and allocate new nodes while the «collector(2)» is determining the reachable nodes, provided the «tri-color invariant» is maintained, by changing the colors of the nodes affected, if necessary.

Historical note: "Tri-color marking" is the term used to describe an algorithm developed in 1975 by E. W. Dijkstra and others, as an exercise in proving cooperating programs correct. They chose as their problem a «parallel garbage collector», with the intent of illustrating cooperating sequential processes with a large shared data space but minimal exclusion and synchronization constraints.

Although the algorithm developed in the paper is not necessarily the most efficient algorithm for a «collector(1)», it has been generally accepted to be correct -- an important feature not all garbage collectors can claim. A number of other garbage collection algorithms have been shown to be isomorphic to the tri-color marking algorithm and thus are also believed to be correct.

See also: «barrier(1)».

Related publications:


two-space collector, two space collector (also known as semi-space collector)

A two-space «collector(1)» is a simple form of a «copying garbage collector». The available «memory(2)» is divided into two halves, called «semi-spaces». «Objects» are allocated in one semi-space until it is full. The «reachable» objects are then copied into the other semi-space (usually using a «Cheney scan») and the old semi-space is «reclaimed». «Allocation» continues in the new semi-space until it is full, at which point the process is repeated in reverse.

The main disadvantage of a two-space collector is that it only makes use of half of the available memory. This can be tolerable in a «virtual memory(1)» system if the «garbage collector» is written carefully to preserve «locality of reference». Other forms of copying garbage collector, such as «generational garbage collectors», have much lower overheads.

Allocation
Diagram: Allocation

Allocation space is full
Diagram: Allocation space is full

Copying garbage collection
Diagram: Copying garbage collection

Allocation continues
Diagram: Allocation continues

See also: «flip».

type-accurate garbage collection (for full details, see «exact garbage collection»)

«Garbage collection» is exact (or precise) if it deals only with «exact references».


U

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

unaligned (also known as misaligned)

An «address» is unaligned or misaligned if it does not comply with some «alignment» constraint on it.

For example, typically double precision floating point numbers occupy 8 «bytes(1)» and have an alignment of 4 bytes; that is, their address must be a multiple of four. If a program tries to access such a number using an address that is not a multiple of four, a «bus error» will result.

Opposites: «aligned».
See also: «alignment»; «bus error».

unboxed

Unboxed «objects» are represented by an encoding of the data itself, and not by a «pointer» to that data.

Representations are typically chosen so that unboxed values are the same size as the pointer part of a «boxed» object. Sometimes the value is «tagged» to distinguish it from a boxed object. The entire object is duplicated when the object is passed around, so updates to it, if allowed, only affect one copy.

Similar terms: «immediate data».
Opposites: «boxed».

Related publications:


undead

An undead object is an «object» that cannot be proven to be «dead» by the «garbage collector», but whose «liveness» is dubious.

For example, an «ambiguous reference» to an object on a «page» may mark the entire page as «reachable». No further data is collected about that page. The other objects on the page will survive, even though their reachability has not been determined. They are undead.

unmapped (also known as free(4))

A range of «virtual addresses» is said to be unmapped (free on Windows®) if there is no «physical memory(2)» associated with the range.

An unmapped range may or may not be «reserved».

Opposites: «mapped».

unreachable

An «object» is unreachable if there is no «reference» chain to it from any «root».

An object will become unreachable when the «mutator» overwrites its last (direct or indirect) reference to the object.

Similar terms: «dead».
Opposites: «reachable»; «live».
See also: «reachable»; «garbage collection».

unsure reference (for full details, see «ambiguous reference»)

An ambiguous or unsure «reference» is a value that is potentially a reference, but the «collector(1)» cannot prove that it is.

unwrapped (also known as raw)

A value is unwrapped or raw if it is not encoded with type information.

In a dynamically-typed language, the compiler may sometimes be able to pick a more compact or efficient representation for a value if it can prove that the type can be determined at compile-time. This is a particularly useful optimization for numeric values such as integers or floats.

Opposites: «wrapped».
See also: «boxed»; «tag»; «value object».

Related publications:


use after free (for full details, see «premature free»)

A premature free or use after free occurs when «memory(2)» is «deallocated», but is later accessed.


V

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

value object (also known as immutable object)

A value object or immutable object is an «object» whose identity depends solely upon its value or magnitude.

In a typed language, the compiler can often determine at compile time that certain types can be represented as value objects. Usually these types are a «scalar data type» with bounded magnitude.

Relevance to memory management: If value objects can be identified, the compiler and the memory manager can make certain optimizations: Value objects can be represented as «immediate data» to minimize storage overhead, they can be replicated to improve «locality», and a «vector data type» of value objects can be represented as a «leaf object».

Historical note: Some programming languages expose representational details such as the use of value objects. In Lisp, for example, numbers are often represented as value objects but not always as immediate data. The EQ predicate of Lisp tests if two objects are the identical representation, whereas the EQL predicate tests if two objects represent the same type and value (are computationally identical). Because the choice of representation is an optimization, exposing it at the language level could cause programs to behave differently under different compilers or optimization settings. Modern languages, such as DylanTM hide this representational distinction, permitting the compiler greater freedom in optimization.

Similar terms: «immediate data».
See also: «immutable».

Related publications:


value type

Definition not yet available. Please see our feedback page for submission information.

vector data type

A vector data type is an aggregate type of more than one dimension whose objects have a value for each dimension, where each dimension is of the same type.

Examples of vector data types include: strings, arrays, and lists.

Relevance to memory management: Vector data types are seldom represented using «value objects», but may be represented using «leaf objects» if they are an aggregate of a type that can be represented by «value objects». «Scanning» information for vectors can be compactly encoded in terms of the aggregated type and the vector dimension.

See also: «scalar data type»; «algebraic data type»; «value object»; «leaf object».

virtual address (also known as logical address)

In a «virtual memory(1)» system, the «addresses» that application programs deal with are known as virtual addresses.

The virtual addresses used by the application program are translated by the virtual memory system (often using «TLB»s and «page-tables») to «physical addresses». It is the physical address that is used to retrieve the contents from the «memory(3)».

Opposites: «physical address».

virtual address space

The virtual «address space» is the space of «virtual addresses».

On «virtual memory(1)» systems, user processes see the virtual address space, and commonly have a separate virtual address space each, so that they map the same addresses to different data. These systems often have «shared memory» as well.

Opposites: «physical address space».

virtual memory(1) (also known as VM(1))

In a virtual memory (VM) system, the program code deals with «virtual addresses». Upon use, the virtual address is translated by the «MMU» to obtain a «physical address» that is used to access «physical memory(1)».

Some operating systems can simulate having more «memory(2)» than is available as «main memory», by storing part of the data in «backing store», typically on disk. If the «page» referenced by the virtual address is not currently in main memory, a «page fault» occurs, triggering an operating system handler that «swaps in» the page. Some other page might be «swapped out» to make room.

Each process typically has its own separate «virtual address space» with its own «mappings» and «protections».

Example of the relationship between the virtual address spaces of two processes, physical memory, and backing store
Diagram: Example of the relationship between the virtual address spaces of two processes, physical memory, and backing store

Virtual memory technology can be used in many useful memory management techniques, such as «barriers(1)», copy-on-write, and «memory mapping».

"Virtual" means never knowing where your next byte is coming from.

Opposites: «real memory(1)».
See also: «paging»; «paged in»; «paged out»; «swapping»; «swap space»; «mapped»; «reserved»; «unmapped»; «shared memory».

VM(1) (for full details, see «virtual memory(1)»)

In a virtual memory (VM) system, the program code deals with «virtual addresses». Upon use, the virtual address is translated by the «MMU» to obtain a «physical address» that is used to access «physical memory(1)».

VM(2)

In the PostScript® language, VM is the «storage» where the values of the «composite objects» reside.

VM is short for "virtual memory", but this has nothing to do with the usual sense of the phrase (see «virtual memory(1)»).


W

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

weak reference(1)

In «tracing garbage collection», a weak reference is a «reference» that does not keep the «object» it refers to «alive».

A weak reference does not keep the referent alive, but it will continue to refer to the object as long as it remains otherwise alive. When only weak references to the object remain, the weak references can be deleted ("splatted" or "cleared") and the object «reclaimed».

JavaTM offers three kinds of weak references, called «soft references», «weak references(2)», and «phantom references», in order of increasing weakness.

Opposites: «strong reference».
See also: «weak root».

weak reference(2)

In JavaTM terminology, weak reference is used to mean a «reference» encapsulated in a «reference object» of class WeakReference.

Weak references form one of three kinds of «weak reference(1)» in Java. They are handy for associating extra data with objects when you cannot store it in the objects themselves.

See also: «weakly reachable».

Other links:

weak root

A weak root is a «root», such that all «references» in it are «weak references(1)»; that is, they do not affect the «liveness» of the «objects» referred to.

Opposites: «strong root».

weak tri-color invariant, weak tri-colour invariant, weak tricolor invariant, weak tricolour invariant

The weak «tri-color invariant» is the property of a «reference» «graph» that all «white» «nodes» pointed to by a «black» node are also «reachable» from some «gray» node through a chain of white nodes.

By preserving this property throughout «tri-color marking», a «tracing» algorithm can ensure that the «collector(2)» will not miss reachable objects, even if the «mutator» manipulates the graph during the collection. Mutator actions might need to change the «color» of the nodes affected in order to preserve the invariant (see Barrier techniques for incremental tracing for details).

Algorithms using this invariant are «snapshot-at-the-beginning» algorithms.

See also: «barrier(1)»; «strong tri-color invariant».

Related publications:


weakly reachable

In JavaTM, an object is weakly reachable if it is neither «strongly» nor «softly reachable» and there is a path from the «roots» to it that contains at least one «weak reference(2)» but no «phantom references».

When the Java «collector(1)» determines that an object is weakly reachable, it clears all the weak references involved, and declares the object «finalizable». (Operationally, finalization works as if it was implemented by a class of "final references" that stand between weak and phantom references.) Also, the «reference objects» containing the weak references are enqueued, if they were registered with a queue.

See also: «reachability»; «phantom reachable».

Other links:

weighted buddies

A «buddy system» «allocation mechanism» using two series of size classes: «binary buddies» (2, 4, 8, ...) and three-times-power-of-two (3, 6, 12, ...). A block that is in the latter series may be «split» in two different ways. Thus a block of size 12 may be split into two blocks of size 6 or one block of size 4 and one block of size 8. The same applies for «coalescing». This gives this system more flexibility than a regular buddy system.

See also: «buddy system»; «allocation mechanism»; «binary buddies».

Related publications:


weighted reference counting

A technique for «reference counting» which is in common use for «distributed garbage collection» because of the low level of inter-process communication it requires.

Inter-process «references» to «objects» are counted, but instead of simply counting the number of references, each reference is given a weight. When an object is created, the initial pointer to it is assigned a weight, which is usually a power of 2 for easy division. The object records the sum of all the weights of all of its references. Whenever a reference is copied, its weight is divided equally between the new and original copies. Since this operation preserves the weighted reference sum, there is no need for communication with the object at this time. When a reference is deleted, the weighted reference sum is decremented by the weight of the reference. This is communicated to the object by sending it a message. When the object detects that the weighted reference sum has dropped to zero, it may be «reclaimed». The algorithm is tolerant of communication protocols which don't guarantee order of arrival of deletion messages.

white

In a «tri-color marking» scheme, white «objects» are objects that were «condemned» at the beginning of the «collection cycle» and have not been shown to be «reachable». When «tracing» is complete, white objects will be subject to «reclamation».

Opposites: «gray»; «black».

word (also known as machine word)

Almost all processor architectures have a characteristic data size that is handled most efficiently. This is known as the word size, and data of that size are known as words. The word size is usually a power of two multiple of «bytes(2)».

Often the platform's word size is used to characterize the architecture by quoting the number of bits in it. For example, a 32-bit platform has a word size of four bytes and a 64-bit platform has eight-byte words (assuming 8-bit bytes). Typically, «pointers» are the size of a word, and traditionally this determined the word size. Nowadays, word size is usually driven by the need for more accuracy and range in mathematical calculations.

Historical note: In the past, the convenience of dealing with powers of two was not as significant, and word sizes such as 36- or 72-bits were not unknown.

See also: «alignment»; «grain».

working set

The working set of a program or system is that «memory(2)» or set of «addresses» which it will use in the near future.

This term is generally used when discussing «miss rates» at some «storage level»; the time scale of "near future" depends upon the cost of a «miss». The working set should fit in the storage level; otherwise the system may «thrash».

See also: «resident set»; «cache(2)»; «storage hierarchy».

Related publications:


worst fit

The «allocation policy» that always allocates from the largest «free block». Commonly implemented using a size-ordered «free block chain» (largest first).

In practice, this tends to work quite badly because it eliminates all large blocks, so large requests cannot be met.

See also: «allocation policy»; «first fit»; «best fit».

Related publications:


wrapped

A value is wrapped if it is encoded with type information.

Opposites: «unwrapped».
See also: «wrapper»; «boxed»; «tag».

Related publications:


wrapper

A wrapper is that part of a «wrapped» representation that is copied when the value is passed by value.

The wrapper does not include parts of the representation that are accessed indirectly, and are not copied when the value is passed.

For instance, a Lisp implementation might use the top two bits of a value representation as a «tag» to distinguish between integers and «cons(1)» cells, setting these bits to 01 for a «pointer» to a cons cell and 11 for an integer. Then the wrapped value of the number 4 would have binary representation 11000...00100, and the wrapper for this number is the whole of this wrapped value. The pointer to a cons cell stored at location 4 would have binary representation 01000...00100. The wrapped value of the cons cell is the combination of this pointer and the cons cell in memory itself. The wrapper of the cons cell is just the pointer; when the cons cell is passed as a function argument, just the pointer is passed.

See also: «wrapped»; «boxed».

Related publications:


write barrier, write-barrier

A write «barrier(1)» is a block on writing to certain «memory(2)» «locations» by certain threads or processes.

Relevance to memory management: Write barriers are used for «incremental» or «concurrent» «garbage collection». They are also used to maintain «remembered sets» for «generational» «collectors(1)».

See also: «read barrier».

write fault

An exception which occurs when writing to an address in «virtual memory(1)».

This is probably either a «page fault», an «invalid page fault» or a «protection fault».

Similar terms: «segmentation violation».
See also: «read fault».


Z

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

ZCT (for full details, see «zero count table»)

A zero count table (ZCT) is used in «deferred reference counting» to record «objects» whose «reference counts» have dropped to zero but which have not been processed to see if they can be «reclaimed».

zero count table (also known as ZCT)

A zero count table (ZCT) is used in «deferred reference counting» to record «objects» whose «reference counts» have dropped to zero but which have not been processed to see if they can be «reclaimed».


A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help