Memory Management Glossary: 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
- 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 term
- immune set
The set of objects which are not condemned.
Opposite term
- 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.
Opposite term
See also
- immutable object
See
- 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.
Opposite term
See also
In the MPS
In-band headers are supported by some pool classes and the size of the header is specified by passing the
MPS_KEY_FMT_HEADER_SIZEkeyword argument tomps_fmt_create_k().A pointer to the first word after the in-band header is called a client pointer.
- in parameter
A function parameter that supplies data from the caller to the function. (The usual case in C.)
Opposite term
- in/out parameter
A function parameter that is both an in parameter an 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.
Similar term
Opposite term
See also
Related publications
In the MPS
The MPS uses incremental collection, except for collections started by calling
mps_arena_collect().- 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.
In order for the collector to miss a reachable object, the following two conditions need to hold at some point during tracing:
The mutator stores a reference to a white object into a black object.
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.
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.
Opposite term
See also
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 lifetime has come to an end.
Opposite term
- 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 publication
- 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 term
Opposite term
Related publication
- 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)
Allocation of child objects inside their parent, as opposed to allocating child objects on the heap and storing pointers to them in the parent.
- 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 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
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.
Opposite term
- 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
- 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.
Similar term
See also
- 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).
Historical note
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
In the MPS
A format method that is called by a moving pool to determine if a formatted object is a forwarding object, and if so, to return the address where the object was moved to. See
mps_fmt_isfwd_t.
