The Memory Management Glossary
T

 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.


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.

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