.. _glossary-t:
=============================
Memory Management Glossary: T
=============================
.. include:: alphabet.txt
.. glossary::
tabling
.. see:: :term:`caching (3)`.
tag
A tag is a piece of information associated with an
:term:`object` or :term:`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 :term:`word` at the
beginning of the object that points to a block of information
about the object's :term:`format`.
.. figure:: ../diagrams/tag-word.svg
:align: center
:alt: Diagram: Example of a tag-word at the start of an object.
Example of a tag-word at the start of an object.
Another common form of tagging is to :term:`align <alignment>`
objects and keep information in the least significant bits of
the reference.
.. figure:: ../diagrams/tag-ref.svg
:align: center
:alt: Diagram: Example of reference tagging, using the least significant bits.
Example of reference tagging, with objects aligned to
addresses that are multiples of four, and the tag stored
in the least significant two bits of the reference.
In :term:`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.
.. seealso:: :term:`tagged architecture`, :term:`in-band header`.
.. bibref:: :ref:`Gudeman (1993) <GUDEMAN93>`.
.. mps:specific::
See :ref:`topic-scanning-tag`.
tagged architecture
A tagged architecture is a hardware architecture where each
memory :term:`word` is divided into a "data" and a :term:`tag`
section. The data section is sufficiently large to contain a
memory :term:`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::
Tagged architectures greatly simplify the implementation
of a memory manager because each word of memory is
self-describing.
.. historical::
The :term:`Lisp Machine` was an example of a tagged
architecture.
tagged reference
A :term:`reference` containing a :term:`tag` in part of its
address, for example by :term:`aligning <alignment>` objects
and keeping the tag in the least significant bits of the
address.
.. mps:specific:: See :ref:`topic-scanning-tag`.
TB (1)
.. see:: :term:`terabyte`.
TB (2)
.. see:: :term:`translation lookaside buffer`.
telemetry filter
.. mps:specific::
A :term:`bitmap` indicating which events the MPS should
include in the :term:`telemetry stream`. It can be read or
changed by calling :c:func:`mps_telemetry_control`.
telemetry label
.. mps:specific::
An indentifier representing a string, returned from
:c:func:`mps_telemetry_intern`, that can be associated
with certain :term:`addresses`, and so appear in
the :term:`telemetry stream` attached to events concerning
those addresses. See :ref:`topic-telemetry`.
telemetry stream
.. mps:specific::
A sequence of events reported by the MPS to assist with
debugging and profiling. The events that appear in the
stream can be configured by setting the :term:`telemetry
filter`. See :ref:`topic-telemetry`.
tenuring
.. see:: :term:`promotion`.
terabyte
.. aka:: *TB*.
A terabyte is 1024 :term:`gigabytes`, or
1099511627776 :term:`bytes (1)`.
See :term:`byte (1)` for general information on this and
related quantities.
termination
.. see:: :term:`finalization`.
thrash
A :term:`cache (2)` is said to :term:`thrash` when its
:term:`miss rate` is too high, and it spends most of its time
servicing :term:`misses`. Thrashing is bad for
performance, particularly :term:`virtual memory`
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
:term:`working set` which is larger than its :term:`cache (1)`
or :term:`main memory`. It may also be caused by a failure of
:term:`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 :term:`physical memory (1)` but which has a working set of
ten megabytes will :term:`thrash` badly.
.. bibref:: :ref:`Denning (1968) <DENNING68>`, :ref:`Denning (1970) <DENNING70>`, :ref:`Denning & Schwartz (1972) <DS72>`.
thread
A thread of execution is a sequence of instructions that take
place sequentially. In a multi-threaded program, multiple
threads of execution operate in parallel, and are generally
asynchronous with respect to each other.
.. relevance::
Access to shared resources such as memory management
interface must be thread-safe. Each thread has its own
:term:`control stack` which may contain :term:`references`
to blocks on the heap.
.. mps:specific::
Threads are represented by values of type
:c:type:`mps_thr_t`, created by calling
:c:func:`mps_thread_reg`. In order for the MPS to find
references on the control of the thread, the thread must
be also be registered as a root by calling
:c:func:`mps_root_create_reg`. See :ref:`topic-thread`.
threatened set
.. see:: :term:`condemned set`.
TLB
.. see:: :term:`translation lookaside buffer`.
to space
tospace
.. aka:: *new space*, *newspace*.
In :term:`copying garbage collection`, the space to which
:term:`live` object are copied.
.. opposite:: :term:`fromspace`.
trace
In :term:`tracing garbage collection`, tracing is the process
of following the :term:`graph` from all :term:`roots`
to all :term:`reachable` data.
.. similar:: :term:`scan`.
tracing garbage collection
Tracing garbage collection is :term:`garbage collection` based
on :term:`reachability <reachable>`.
Tracing garbage collection relies on the fact that if an
:term:`object` is not :term:`reachable`, there is no way the
:term:`mutator` could ever access it, and therefore it cannot
be :term:`live`. In each :term:`collection cycle`, some or all
of the objects are :term:`condemned <condemned set>` and the
:term:`graph` is :term:`traced` to find which of the condemned
objects are reachable. Those that were not reachable may be
:term:`reclaimed`.
translation buffer
translation lookaside buffer
.. aka:: , *address translation cache*, *ATC*, *TB*.
The *translation lookaside buffer* or *address translation
cache* is small piece of associative :term:`memory (1)` within
a processor which caches part of the translation from
:term:`virtual addresses` to :term:`physical addresses`.
In a :term:`virtual memory` system there is a translation from
:term:`virtual addresses` to :term:`physical addresses`. This
translation can often be very large and complex and the data
structures that implement the translation (often a :term:`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.
transparent alias
transparent type
.. mps:specific::
In the MPS interface, a *transparent type* is an alias
defined using ``typedef``, and this is documented so that
the :term:`client program` can rely on that fact. For
example, :c:type:`mps_addr_t` is a transparent alias for
``void *``. See :ref:`topic-interface`.
.. opposite:: :term:`derived type`, :term:`opaque type`.
transport
In a :term:`copying collector <copying garbage collection>`,
transporting is preventing an :term:`object` in the
:term:`condemned set` from being collected by copying it and
adjusting the :term:`reference` by which it was discovered to
point to the new copy.
.. seealso:: :term:`scavenging <copying garbage collection>`, :term:`snap-out`.
transport snap-out
.. see:: :term:`snap-out`.
treadmill
Henry Baker devised an :term:`incremental <incremental garbage
collection>` non-:term:`moving <moving garbage collector>`
:term:`garbage collector` that uses a circular doubly-linked
list, called the *treadmill*, to implement :term:`tri-color
marking`.
Every :term:`object` is on the list. The list has four
sections corresponding to :term:`colors`. The
:term:`black`, :term:`gray` and :term:`white` sections are
used for tri-color marking, and an additional
:term:`off-white` section is used for :term:`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.
.. figure:: ../diagrams/treadmill.svg
:align: center
:alt: Diagram: A treadmill.
A treadmill. (Based on :ref:`Jones (2012) <JONES12>`.)
.. bibref:: :ref:`Baker (1992c) <BAKER92C>`.
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 :term:`reference` :term:`graph` that
are preserved throughout a :term:`tri-color marking` algorithm
to ensure the correctness.
There are two important ones: the :term:`strong tri-color
invariant` and the :term:`weak tri-color invariant`. When
people say "the tri-color invariant" they probably mean the
strong one.
.. bibref:: :ref:`Johnstone (1997) <JOHNSTONE97>`, :ref:`Pirinen (1998) <PIRINEN98>`.
tri-color marking
tri-colour marking
tricolor marking
tricolour marking
Tri-color marking is a :term:`tracing garbage collection`
algorithm that assigns a :term:`color` (:term:`black`,
:term:`white`, or :term:`gray`) to each :term:`node` in the
:term:`graph`. It is basic to :term:`incremental garbage
collection`.
Initially all nodes are colored white. The distinguished
:term:`root set` is colored gray. The :term:`collector (2)`
proceeds to discover the :term:`reachable` nodes by finding an
:term:`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
:term:`recycled`.
The :term:`mutator` is free to access any part of the graph
and allocate new nodes while the :term:`collector (2)` is
determining the reachable nodes, provided the :term:`tri-color
invariant` is maintained, by changing the colors of the nodes
affected, if necessary.
.. historical::
"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 :term:`parallel garbage
collector <parallel garbage collection>`, 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
:term:`collector (1)`, it has been generally accepted to be
correct: an important feature that 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.
.. seealso:: :term:`barrier (1)`.
.. bibref:: :ref:`Dijkstra et al. (1976) <DLMSS76>`.
two-space collector
two space collector
.. aka:: *semi-space collector*.
A two-space :term:`collector (1)` is a simple form of a
:term:`copying garbage collector <copying garbage
collection>`. The available :term:`memory (2)` is divided into
two halves, called :term:`semi-spaces`. :term:`Objects` are
allocated in one semi-space until it is full. The
:term:`reachable` objects are then copied into the other
semi-space (usually using a :term:`Cheney scan`) and the old
semi-space is :term:`reclaimed`. :term:`Allocation <allocate>`
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 :term:`virtual memory` system if the
:term:`garbage collector` is written carefully to preserve
:term:`locality of reference`. Other forms of copying garbage
collector, such as :term:`generational garbage collectors
<generational garbage collection>`, have much lower overheads.
.. figure:: ../diagrams/two-space.svg
:align: center
:alt: Diagram: Two-space collector.
Two-space collector.
.. seealso:: :term:`flip`.
type-accurate garbage collection
.. see:: :term:`exact garbage collection`.
type punning
Interpreting a value of one type as if it were a value of
another (for example, via a type cast in :term:`C`),
especially if such interpretation is not defined by the
language standard. For example, interpreting a value of type
``T**`` (pointer to pointer to ``T``) as ``U**`` is undefined.
.. mps:specific:: See :ref:`topic-interface`.