Memory Management Glossary: I¶
- immediate data¶
- immune set¶
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.
- immutable object¶
- in-band header¶
Also known as
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.
- in parameter¶
A function parameter that supplies data from the caller to the function. (The usual case in C.)
- in/out parameter¶
In the MPS
In/out parameters are given names ending with
_io. See Interface conventions.
- 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.
In the MPS
The MPS uses incremental collection, except for collections started by calling
- incremental update¶
Incremental-update algorithms for tracing, incremental garbage collection 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.
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 Pirinen (1998) for details).
They are so called because they incrementally update the collector’s view of the graph to track changes made by the mutator.
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.
- indefinite extent¶
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 lifetime has come to an end.
- 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.
- 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 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.
- infant mortality¶
- inline allocation(1)¶
Allocation of objects by inline code, that is, without calling an allocation function. This is vital for performance in languages that allocate many small objects.
In the MPS
This is achieved by the Allocation point protocol.
- inline allocation(2)¶
- inter-generational pointer¶
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 cycle. 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
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.
- internal fragmentation¶
- invalid page fault¶
An exception when using virtual memory 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.
- inverted page table¶
- inverted page-table¶
In a virtual memory 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).
The Lisp Machine was an early workstation that used an inverted page table with hardware lookup. The UltraSPARC, PowerPC, and IA-64 architectures all include inverted page tables. Some implementations of these architectures have hardware-assisted lookup.
- is-forwarded method¶