.. _glossary-g:

=============================
Memory Management Glossary: G
=============================

.. include:: alphabet.txt

.. glossary::

    garbage

        Garbage consists of :term:`objects` that are
        :term:`dead`.

        In :term:`tracing garbage collection`, the term is sometimes
        used to mean objects that are known to be dead; that is,
        objects that are :term:`unreachable`.

    garbage collection

        .. aka:: *GC*.

        Garbage collection (GC), also known as *automatic memory
        management*, is the automatic :term:`recycling <recycle>` of
        :term:`dynamically allocated <heap allocation>` :term:`memory
        (2)`. Garbage collection is performed by a :term:`garbage
        collector` which recycles memory that it can prove will never
        be used again. Systems and languages which use garbage
        collection can be described as *garbage-collected*.

        Garbage collection is a tried and tested memory management
        technique that has been in use since its invention in the
        1950s. It avoids the need for the programmer to
        :term:`deallocate <free (1)>` memory :term:`blocks`
        explicitly, thus avoiding a number of problems: :term:`memory
        leaks`, :term:`double frees`, and :term:`premature frees`. The
        burden on the programmer is reduced by not having to
        investigate such problems, thereby increasing productivity.

        Garbage collection can also dramatically simplify programs,
        chiefly by allowing modules to present cleaner interfaces to
        each other: the management of object storage between modules
        is unnecessary.

        It is not possible, in general, for a :term:`garbage
        collector` to determine exactly which :term:`objects` are
        still :term:`live`. Even if it didn't depend on future input,
        there can be no general algorithm to prove that an object is
        live (cf. the Halting Problem). All garbage collectors use
        some efficient approximation to liveness. In :term:`tracing
        garbage collection`, the approximation is that an object can't
        be live unless it is :term:`reachable`. In :term:`reference
        counting`, the approximation is that an object can't be live
        unless it is :term:`referenced`. Hybrid algorithms are also
        possible. Often the term *garbage collection* is used narrowly
        to mean only tracing garbage collection.

        There is a large body of published work on particular and
        general garbage collection algorithms.

        .. historical::

            Garbage collection was first invented by John McCarthy in
            1958 as part of the implementation of :term:`Lisp`.

        Other significant languages offering garbage collection
        include :term:`Java`, :term:`ML`, :term:`Modula-3`,
        :term:`Perl`, :term:`Prolog`, and :term:`Smalltalk`. Major
        applications using garbage collection include Emacs and
        AutoCAD; usually, you can't tell whether an application does
        or not, but these have extension languages that expose the
        fact.

        .. similar:: :term:`automatic memory management`.

        .. opposite:: :term:`manual memory management`.

        .. seealso:: :term:`conservative garbage collection`, :term:`copying garbage collection`, :term:`distributed garbage collection`, :term:`generational garbage collection`, :term:`incremental garbage collection`, :term:`parallel garbage collection`.

        .. bibref:: :ref:`McCarthy (1960) <MCCARTHY60>`.

    garbage collector

        .. aka:: *collector*.

        A (garbage) collector is (an implementation of) a
        :term:`garbage collection` algorithm.

        This term is often used when referring to particular
        implementations or algorithms, for example, "the
        Boehm-Demers-Weiser *collector*".

    GB

        .. see:: :term:`gigabyte`.

    GC

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

    General Protection Fault

        .. aka:: *GPF*.

        A General Protection Fault on the Windows platforms is the
        equivalent of a :term:`segmentation violation` on Unix.

    generation

        A generation is a set of :term:`objects` of similar
        *age*.

        A :term:`generational garbage collector <generational garbage
        collection>` will typically divide the set of all objects into
        generations, and :term:`condemn <condemned set>` all the
        objects in a generation together. Rather than allowing whole
        generations to age, the :term:`collector (1)` can
        :term:`promote <promotion>` objects into older generations as
        they survive successive :term:`collection cycles <collection
        cycle>`.

        New objects are usually allocated in the youngest or
        :term:`nursery generation`, but if we know that particular
        objects will be long-lived, we might want to allocate them
        directly in an older generation. Thus, more loosely, a
        generation is a set of objects which have similar expected
        :term:`lifetimes`.

        .. seealso:: :term:`bucket`.

        .. mps:specific::

            The :term:`client program` specifies the generational
            structure of a :term:`pool` using a :term:`generation
            chain`. See :ref:`topic-collection`.

    generation chain

        .. mps:specific:: 

            A data structure that specifies the structure of the
            :term:`generations` in a :term:`pool`. See
            :ref:`topic-collection`.

    generation scavenging

        .. see:: :term:`generational garbage collection`.

    generational garbage collection

        .. aka:: *generation scavenging*.

        Generational garbage collection is :term:`tracing garbage
        collection` that makes use of the :term:`generational
        hypothesis`. :term:`Objects` are gathered together in
        :term:`generations`. New objects are allocated in
        the *youngest* or *nursery* generation, and :term:`promoted
        <promotion>` to *older* generations if they survive. Objects
        in older generations are :term:`condemned <condemned set>`
        less frequently, saving CPU time.

        It is typically rare for an object to refer to a younger
        object. Hence, objects in one generation typically have few
        :term:`references` to objects in younger
        generations. This means that the :term:`scanning <scan>` of
        old generations in the course of collecting younger
        generations can be done more efficiently by means of
        :term:`remembered sets`.

        In some purely functional languages (that is, without update),
        all references are backwards in time, in which case remembered
        sets are unnecessary.

        .. seealso:: :term:`remembered set`.

    generational hypothesis

        .. aka:: *infant mortality*.

        *Infant mortality* or *the generational hypothesis* is the
        observation that, in most cases, young :term:`objects` are
        much more likely to :term:`die <dead>` than old objects.

        Strictly, the hypothesis is that the probability of death as a
        function of age falls faster than exponential decay (inverse
        hyper-exponential), but this strict condition is not always
        required for techniques such as :term:`generational garbage
        collection` to be useful.

    gigabyte

        .. aka:: *GB*.

        A gigabyte is 1024 :term:`megabytes`, or 1073741824
        :term:`bytes (1)`.

        See :term:`byte (1)` for general information on this and
        related quantities.

    good fit

        The class of :term:`allocation policies` which approximate
        :term:`best fit`. Strict best fit may be costly to implement
        (depending on the details of the :term:`allocation
        mechanism`), so some implementors approximate it, choosing a
        block which is close in size to the allocation request.

        .. seealso:: :term:`best fit`, :term:`allocation policy`, :term:`next fit`, :term:`worst fit`.

        .. bibref:: :ref:`Wilson et al. (1995) <WIL95>`.

    GPF

        .. see:: :term:`General Protection Fault`.

    grain

        The grain of a platform is the smallest :term:`alignment` that
        is sufficient to accommodate all data accesses on that
        platform. Often this is a :term:`word` or a small multiple of
        a word. Double precision floating point numbers often have the
        strictest alignment requirements.

        .. seealso:: :term:`alignment`, :term:`word`.

    graph

        A graph is a set of :term:`nodes` together with a set
        of :term:`edges` connecting nodes.

        If the edges have direction like arrows (for example,
        :term:`references` in a graph of :term:`objects`), then the
        graph is said to be a *directed graph*.

        .. figure:: ../diagrams/graph.svg
            :align: center
            :alt: Ten white circles (the nodes of this graph), some of them joined by arrows (the edges of the graph). Most of the edges point in one direction, but one edge points both ways. Seven of the nodes are connected in one component, and three in another.

            Directed graph.

        .. relevance::

            Graphs are used to model :term:`reachability <reachable>`
            for :term:`tracing garbage collection`. The
            :term:`objects` are considered to form a graph, with the
            nodes of the graph being the objects and the edges of the
            graph being the references from one object to another.
            Usually, there is a single, distinguished :term:`root` to
            which the :term:`mutator` has *direct* access, and the
            nodes strongly connected to it are the reachable modes.

    gray
    grey

        In a :term:`tri-color marking` scheme, gray :term:`objects`
        are objects that are proved or assumed (see
        :term:`generational <generational garbage collection>` and
        :term:`condemn <condemned set>`) to be :term:`reachable`, but
        have not yet been :term:`scanned <scan>`.

        More precisely, gray objects have been noted reachable, but
        must still be visited by the :term:`collector (2)` in order to
        process their children.

        .. similar:: :term:`gray list`.

        .. opposite:: :term:`black`, :term:`white`.

    gray list
    grey list

        The gray list is the set of :term:`objects` that a
        :term:`tracing garbage collector <tracing garbage collection>`
        has noted :term:`reachable`, but hasn't :term:`scanned <scan>`
        yet.

        The gray list is so called because it corresponds to the set
        of :term:`gray` objects in the :term:`tri-color marking` model
        of graph tracing. The gray list changes as the garbage
        collector progresses.

        Each gray object is :term:`scanned <scan>`, and all
        :term:`white` objects referred to by it become gray and are
        added to the list. Scanning a gray object turns it
        :term:`black`. When the gray list is empty, the tracing is
        finished, and white objects may be :term:`reclaimed
        <reclaim>`.

        The representation of the gray list is a key part of garbage
        collector design. The size of the list is potentially
        proportional to the size of the :term:`heap`, and the
        operation of finding the next gray object to scan must be
        cheap.

        .. seealso:: :term:`Cheney scan`.