The Memory Management Glossary
I

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

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

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.


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.

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