.. _glossary-c:

=============================
Memory Management Glossary: C
=============================

.. include:: alphabet.txt

.. glossary::

    cache (1)

        .. aka:: *memory cache*, *cache memory*.

        A processor's memory cache is a small piece of fast, but more
        expensive memory, usually :term:`static memory (1)`, used for
        copies of parts of :term:`main memory`. The cache is
        automatically used by the processor for fast access to any
        data currently :term:`resident` there. Access to the cache
        typically takes only a few processor clock cycles, whereas
        access to :term:`main memory` may take tens or even hundreds
        of cycles.

        What part of main memory is resident in a cache, and the
        mechanisms by which it is kept consistent, are quite varied.
        See :term:`cache policy`.

        Some systems have more than one level of cache. "Level 1
        cache" is the fastest, smallest :term:`storage level`, "level
        2" the next fastest, and so on.

        .. seealso:: :term:`storage hierarchy`, :term:`cache (2)`.

    cache (2)

        A cache is any small, fast piece of :term:`memory (1)`, used
        for copies of data that normally reside in a larger, slower
        piece of storage. The cache is used to speed up access to data
        :term:`resident` in the slower storage.

        In a typical cache, recently used data is :term:`resident` in
        the cache (although the details of this depend on the
        :term:`cache policy`). A :term:`cache (1)` is the most common
        example of a cache(2).

        .. seealso:: :term:`storage hierarchy`.

    cache memory

        .. see:: :term:`cache (1)`.

    cache policy

        Any :term:`cache (3) <caching (3)>` uses a *cache policy* to
        decide which data to store. A cache policy is an attempt to
        predict the future, so that the cache will provide swift
        responses to future requests.

        Cache policy may be implemented in hardware, software, or a
        combination of both. Some systems allow programs to influence
        cache policy, by giving hints or directions about future use
        of data.

        There are three main aspects of cache behavior which the cache
        policy can affect:

        1. Fetch policy. This determines which data is fetched into
           the cache, usually as a result of receiving a request for
           data that isn't cached.

        2. Eviction policy. This determines which data is discarded
           from the cache to provide space for newly fetched data.

        3. Write policy This determines how and when modifications to
           cached data are synchronized with the underlying storage.

        .. seealso:: :term:`cache (1)`, :term:`cache (2)`, :term:`cache (3) <caching (3)>`.

        .. bibref:: :ref:`Baker (1991) <BAKER91>`, :ref:`Wilson et al. (1992) <WLM92>`, :ref:`Zorn (1991) <ZORN91>`.

    caching (3)

        .. aka:: *memoization*, *tabling*.

        *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 :term:`Prolog`
        community).

        A "look-ahead cache" attempts to store answers to questions
        that will be asked soon. A :term:`cache (2)` is a common
        example of a cache(3).

    cactus stack

        .. aka:: *spaghetti stack*.

        A cactus stack is a :term:`stack` with branches. When
        diagrammed, its shape resembles that of a `saguaro cactus
        <http://www.azstarnet.com/%7Efosnp/factsaboutsaguaros.html>`_.

        In languages that support :term:`continuations`,
        :term:`activation records` can have :term:`indefinite extent`.
        One technique for implementing continuations is not to copy
        the activation records that are captured, but rather to create
        a fork in the stack below the captured :term:`stack frames`,
        so that new frames appear as a parallel branch. Often the
        process of forking is done lazily: captured frames are only
        duplicated if they are modified.

    card

        A card is a division of memory, all cards being of equal size
        (in a particular area of discourse). A card is usually bigger
        than a :term:`word` and smaller than a :term:`page`. Cards are
        used in a technique called :term:`card marking` whereby
        :term:`dirty bits` (which record which portions of old
        generations have been written into) are maintained for each
        card. Often the use of cards will also entail the use of a
        :term:`crossing map`.

    card marking

        A technique for managing :term:`pointer` :term:`stores (1)`
        into old :term:`generations` (which in turn is used to track
        :term:`inter-generational pointers`). Each generation is
        divided into a number of equal-sized :term:`cards`, and when a
        generation is written into, the particular card written to is
        recorded (often by using a :term:`bitmap`). Subsequently, when
        :term:`scanning <scan>` an older generation in order to
        collect a younger generation, only the recorded cards (in the
        old generation) need to be scanned.

        .. seealso:: :term:`generational garbage collection`.

        .. bibref:: :ref:`Azagury et al. (1998) <AKPY98>`, :ref:`Hosking & Hudson (1993) <HH93>`, :ref:`Sobalvarro (1988) <SOBALVARRO88>`.

    cell

        .. see:: :term:`object`.

    Cheney collector

        .. aka:: *Cheney scan*.

        A Cheney collector uses the :term:`tospace` of a
        :term:`two-space collector` as a queue of objects remaining to
        be :term:`scanned <scan>`, thus eliminating the need for
        recursion when :term:`tracing <trace>` the :term:`graph` of
        :term:`objects`.

        .. bibref:: :ref:`Cheney (1970) <CHENEY70>`.

    Cheney scan

        .. see:: :term:`Cheney collector`.

    clamped state

        .. mps:specific::

            One of the three states an :term:`arena` can be in (the
            others being the :term:`unclamped state` and the
            :term:`parked state`). In the clamped state, no object
            motion occurs and the staleness of :term:`location
            dependencies` does not change. However, a :term:`garbage
            collection` may be in progress. Call
            :c:func:`mps_arena_clamp` to put an arena into the clamped
            state.

    client arena

        .. mps:specific::

            An :term:`arena class` that gets its :term:`memory (2)`
            from the :term:`client program`. See
            :ref:`topic-arena-client`.

    client object

        .. mps:specific::

            A :term:`formatted object` that contains data from the
            :term:`client program`. One of three types of formatted
            objects, the other two being :term:`forwarding objects`
            and :term:`padding objects`.

    client program

        .. see:: :term:`mutator`

    closure

        A closure is a function or procedure that is saved along with
        the current bindings from enclosing blocks for later
        invocation.

        Some programming languages, such as :term:`ALGOL`, permit
        nested blocks to access the local variables of enclosing
        blocks. :term:`Lisp`-like languages further permit such an
        inner block (in particular a function or procedure) to be
        saved for later invocation. The act of saving such an inner
        block along with the current bindings of variables in the
        enclosing blocks that are referenced by the inner block, is
        called *closing over* or *capturing* those variables. The
        object created is termed *a closure*. A closure is invoked
        just like the function from which it was built, passing
        whatever parameters the function accepts, but when the
        function executes, the variables that belong to enclosing
        blocks will have the bindings that were in effect when the
        closure was created.

        .. relevance::

            A closure is typically implemented by saving both the
            function and any :term:`activation records` that contain
            variables referenced by the function. The closure creates
            additional implicit :term:`references` to the bindings
            closed over and hence must be accounted for in any memory
            management scheme. The closure itself is an object that
            must be managed and may have either :term:`dynamic extent`
            or :term:`indefinite extent` depending on whether it is
            only used by inner blocks of the creating block or passed
            out of the creating block.

        .. seealso:: :term:`continuation`.

    coalesce

        Coalescing is the act of merging two adjacent :term:`free
        blocks`.

        Coalescing reduces :term:`external fragmentation`, but is not
        totally effective.

        Coalescing can be done as soon as blocks are freed, or it can
        be deferred until some time later (known as :term:`deferred
        coalescing`), or it might not be done at all.

        :ref:`Wilson et al. (1995) <WIL95>` has details about
        fragmentation, and which coalescing strategies are effective
        under what circumstances.

    collect

        An :term:`object` is collected when it is :term:`reclaimed` by
        a :term:`garbage collector`.

        .. similar:: :term:`reclaim`.

    collection

        .. see:: :term:`collection cycle`.

    collection cycle

        .. aka:: *collection*.

        A collection cycle is a single complete execution of a
        :term:`tracing garbage collection` algorithm.

        Each collection cycle includes (not necessarily in strict
        order) choosing a :term:`condemned set`; :term:`scanning
        <scan>` :term:`roots` and :term:`objects` that have not been
        condemned; :term:`tracing <trace>` the object graph to find
        all condemned objects that are :term:`reachable`; and
        :term:`reclaiming <reclaim>` those that were not reachable.

        In non-incremental garbage collection, the :term:`mutator`
        pauses at the start of a collection cycle and cannot continue
        until it is complete. In :term:`incremental <incremental
        garbage collection>` and :term:`parallel <parallel garbage
        collection>` garbage collection, a collection cycle can be
        interleaved with, or simultaneous to, mutator activity.

    collector (1)

        .. see:: :term:`garbage collector`.

    collector (2)

        In a :term:`garbage-collected <garbage collection>` system,
        the part that executes the garbage collection code, which
        discovers unused :term:`memory (1)` and :term:`reclaims` it.

        For purposes of describing :term:`incremental garbage
        collection`, the system is divided into the :term:`mutator`
        and the *collector*. These can be separate threads of
        computation, or interleaved within the same thread.

        .. historical::

            This term is due to :ref:`Dijkstra et al. (1976)
            <DLMSS76>`.

        .. opposite:: :term:`mutator`.

    color
    colour

        In a :term:`tri-color marking` scheme, each :term:`node` has a
        one of three colors: :term:`black`, :term:`white`, or
        :term:`gray`. In a :term:`treadmill`, nodes may also be
        colored :term:`off-white`.

    commit limit

        .. mps:specific::

            The commit limit is a limit on the :term:`committed
            <mapped>` :term:`memory (2)` that the :term:`arena` will
            obtain from the operating system. It can be changed by
            calling :c:func:`mps_arena_commit_limit_set`.

    committed (1)

        .. see:: :term:`mapped`.

    committed (2)

        .. mps:specific::

            A block has been *committed* if it is fully initialized
            and is under the management of the MPS, as opposed to a
            block that is merely *reserved*. See
            :ref:`topic-allocation-point-protocol`.

    compactifying

        .. see:: :term:`compaction`.

    compaction

        .. aka:: *compactifying*.

        Compaction is the process of :term:`moving <moving garbage
        collector>` :term:`live` :term:`objects` to eliminate
        :term:`dead` space between them. Some people call this
        *compactifying*, to distinguish it from techniques for
        compressing data structures.

        Compaction is used to avoid :term:`external fragmentation` and
        to increase :term:`locality of reference`.

    composite object

        In the :term:`PostScript` language, *composite objects* are
        the :term:`boxed` objects.

        Unlike a :term:`simple object`, the main data (what PostScript
        calls *the value*) in a composite object are stored
        separately, in :term:`VM (2)`. Several composite objects can
        share the same value.

        .. similar:: :term:`boxed`.

        .. opposite:: :term:`simple object`.

    comprehensive

        A :term:`collector (1)` is *comprehensive* if all
        :term:`garbage` (or, all :term:`unreachable` :term:`objects`)
        is :term:`reclaimed` in one :term:`collection cycle`.

        .. seealso:: :term:`garbage collection`.

    concurrent garbage collection

        .. see:: :term:`parallel garbage collection`.

    condemned set

        .. aka:: *threatened set*.

        *Condemned* :term:`objects` are those which are
        candidates for :term:`recycling <recycle>` within a
        :term:`collection cycle`.

        At the start of a collection cycle, the :term:`collector (1)`
        may choose to condemn some objects (the *condemned set* or
        *threatened set*) but not to condemn others (the :term:`immune
        set`). Objects that are not condemned are assumed to be
        :term:`live` and behave as :term:`roots` for the
        purposes of that collection cycle.

        Many simple :term:`tracing garbage collection` algorithms
        begin by condemning all objects, but :term:`generational
        garbage collectors <generational garbage collection>` will
        condemn individual :term:`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
        :term:`unreachable`.

        In collectors using :term:`tri-color marking`, at the start of
        a collection cycle the condemned set is exactly the set of
        objects that the collector colors :term:`white`.

        .. opposite:: :term:`immune set`.

    connected

        :term:`Objects` are connected if and only if one
        contains a :term:`reference` to the other.

        .. seealso:: :term:`graph`.

    cons (1)

        In :term:`Lisp`, ``cons`` is a primitive operation creating a
        list element (from English "CONStruct"). By extension, a
        *cons* is the element created.

        .. link::

            `Function CONS in the Common Lisp HyperSpec <http://www.lispworks.com/documentation/lw60/CLHS/Body/f_cons.htm>`_.

    cons (2)

        .. see:: :term:`allocate`.

    conservative garbage collection

        In conservative :term:`garbage collection`, the layout of
        :term:`objects` and :term:`roots` is not
        known, instead the :term:`collector (1)` assumes that any
        field that looks like a :term:`pointer` *might* be a
        :term:`reference`.

        Conservative collectors can work with programs where
        information about the :term:`memory (2)` layout is not
        available, because, for example, the language doesn't support
        :term:`garbage collection`.

        A conservative collector doesn't need to know the
        :term:`format` of the objects, it just needs some idea of
        where the object boundaries are. It regards any field value
        that looks like a pointer to an object (or, sometimes, into
        the middle of one), as preventing the :term:`recycling
        <recycle>` of that object. It can't :term:`move <moving
        garbage collector>` objects, because then the references to
        the moved objects would need to be updated, and such
        :term:`ambiguous references` must not be modified, in case
        they weren't pointers after all. Therefore, conservative
        collectors are usually :term:`mark-sweep collectors
        <mark-sweep>`.

        Because references are ambiguous, some objects may be retained
        despite being actually :term:`unreachable`. In practice, this
        happens rarely, and refinements such as :term:`black-listing
        <blacklisting>` can further reduce the odds.

        .. opposite:: :term:`exact garbage collection`.

        .. seealso:: :term:`ambiguous root`, :term:`semi-conservative garbage collection`, :term:`interior pointer`.

        .. bibref:: :ref:`Boehm & Weiser (1988) <BW88>`, :ref:`Boehm (1993) <BOEHM93>`.

    constant root

        .. mps:specific::

            A :term:`root` that the :term:`client program` promises
            not change after it is registered, by specifying the
            :term:`root mode` :c:macro:`MPS_RM_CONST` when calling a
            registration function such as :c:func:`mps_root_create`.

    constructor (1)

        A constructor is a function or method that :term:`allocates` and initializes an :term:`object`.

        .. opposite:: :term:`destructor (1)`.

    constructor (2)

        In :term:`C++`, a *constructor* is a member function that is
        used to initialize a newly-:term:`allocated` object.

        The actual allocation of :term:`memory (2)` is performed by
        ``operator new`` or the compiler (for :term:`static <static
        allocation>` and :term:`stack allocation`), and the new
        :term:`block` is then passed to the appropriate constructor.

        .. seealso:: :term:`destructor (2)`.

    continuation

        A continuation is the data required to restore an execution
        context after invocation of another context, typically as a
        subroutine.

        .. relevance::

            If continuations can be represented as first-class
            objects, as in :term:`Scheme`, the execution contexts can
            no longer be stored on a :term:`stack`, instead, (at least
            some) :term:`activation records` have
            to be :term:`heap-allocated <heap allocation>`.

        .. seealso:: :term:`closure`.

    control stack

        .. aka:: *activation stack*, *execution stack*.

        A :term:`stack` that stores :term:`activation records`, particularly subroutine return
        information, is known as a *control stack*.

        Typically the control stack is supported and used by the
        hardware architecture and the operating system, limiting the
        types and sizes of :term:`objects` that can be stored
        on it. Often, only one type of object, a :term:`stack frame`,
        is permitted, and the layout of that is defined by the
        hardware architecture.

        .. relevance::

            Theoretically, a control stack is simply an array of
            activation records, and hence just another object managed
            by the :term:`memory manager`. In practice, the control
            stack is central to the performance of the hardware
            architecture and may require special treatment. In
            particular, it may not be accessible as ordinary
            :term:`memory (2)`, or it may have its own :term:`cache
            (2)` with specific updating requirements.

        .. similar:: :term:`stack`.

        .. seealso:: :term:`data stack`.

    cool

        .. mps:specific::

            A :term:`variety` in which most MPS functions
            :term:`assert <assertion>` that their data structures are
            valid, even functions on the :term:`critical path`. See
            :ref:`guide-build`. Compare :term:`hot` and :term:`rash`.

    copy method

        .. mps:specific::

            A copy method is one of the methods in an :term:`object
            format`. Formerly, the MPS called this method to copy a
            :term:`formatted object` during :term:`moving garbage
            collection <moving garbage collector>`. Now it just copies
            the bytes and the copy method is ignored.

    copying garbage collection

        .. aka:: *scavenging garbage collection*.

        Copying garbage collection is a kind of :term:`tracing garbage
        collection` that operates by :term:`relocating <relocation>`
        :term:`reachable` :term:`objects` (this is sometimes called
        *scavenging*) and then :term:`reclaiming <reclaim>` objects
        that are left behind, which must be :term:`unreachable` and
        therefore :term:`dead`.

        A copying garbage collection relies on being able to find and
        correct all :term:`references` to copied objects.

        .. figure:: ../diagrams/copying.svg
            :align: center
            :alt: Diagram: Copying garbage collection.

            Copying garbage collection.

        .. similar:: :term:`moving <moving garbage collector>`.

        .. seealso:: :term:`broken heart`, :term:`forwarding pointer`, :term:`two-space collector`.

    core

        A historical synonym for :term:`main memory`, deriving from
        the *cores* or ferrite rings which were once the main
        technology used to implement it.

        .. similar:: :term:`main memory`.

    creation space

        In :term:`generational garbage collection`, when
        :term:`generations` are divided into
        :term:`buckets`, the creation space is where new
        :term:`objects` are created in each generation.

        This term is sometimes used as a synonym for :term:`nursery space`.

        .. opposite:: :term:`aging space`.

        .. seealso:: :term:`generational garbage collection`.

    critical path

        .. mps:specific::

            The sequence of operations on which the MPS spends the
            majority of its time, consisting of :term:`scanning
            <scan>`, :term:`fixing <fix>`, :term:`marking` and
            :term:`copying <copying garbage collection>`. See
            :ref:`topic-critical`.

    crossing map

        Where :term:`memory (2)` has already been divided into some
        fixed-sized unit (for example, :term:`pages` or
        :term:`cards`), a crossing map records where
        :term:`objects` lie across the boundaries of the
        fixed-sized units. In other words, which fixed-sized units do
        not start with the beginning of an object.

        A system which implements :term:`remembered sets` by
        :term:`page marking` or :term:`card marking` needs to scan all
        the :term:`pointers` in the page or card. If the system can
        not :term:`scan` partial objects (or requires information in
        the object :term:`header <in-band header>` in order to scan a
        partial object), a crossing map is necessary to find the
        beginning of the first object in the unit.

        .. relevance::

            In a sense, a crossing map is an optimization of
            :term:`tagged architecture`. It represents the minimum
            information necessary to determine how to interpret any
            word of memory.

    cyclic data structure

        A data structure is cyclic if some of its :term:`references`
        form a loop; that is, there's an :term:`object` that can be
        reached by following references from itself.
