.. _glossary-l:

=============================
Memory Management Glossary: L
=============================

.. include:: alphabet.txt

.. glossary::

    large object area

        An :term:`allocation mechanism` designed to optimize the
        management of large :term:`objects` by separating
        them from small ones.

        Large objects, typically objects one or more orders of
        magnitude larger than the :term:`virtual memory`
        :term:`page` of a platform, can be costly to :term:`allocate`,
        initialize, and :term:`recycle`. By segregating those objects
        into a separate area, they can be managed using specific
        mechanisms that would be inefficient for smaller objects but
        which can reduce the cost of manipulating large ones.

        Some example mechanisms:

        1. In a :term:`copying collector <copying garbage collection>`
           large objects can be managed separately using a
           :term:`mark-and-sweep collector <mark-sweep>` to avoid
           copying costs. See :ref:`Ungar (1988) <UNGAR88>`.

        2. By aligning large objects on page boundaries, they can be
           :term:`compacted <compaction>` or copied by adjusting their
           :term:`mapping` in :term:`virtual memory`. See
           :ref:`Withington (1991) <WITHINGTON91>`.

        3. Large objects may be split into a header and a body, where
           the header is fixed size and the bulk of the object is in
           the body. See :ref:`Ungar (1988) <UNGAR88>`.

        4. By using a page-based :term:`read barrier`, large objects
           can be initialized incrementally. For example, each page of
           the large object is initialized to zero when it is first
           read, rather than all at once at creation time.

        5. In a copying collector, large objects can be copied
           incrementally using a similar technique (the new copy is
           initialized from the old copy). See :ref:`Baker (1978)
           <BAKER78>`.

        6. Large objects are often :term:`leaf objects`,
           so do not need to be :term:`scanned <scan>`, or are known
           to have a fixed :term:`format` with only a few
           :term:`references` so they can be scanned more
           efficiently by a specialized scanner.

        7. Large objects often have longer than average
           :term:`lifetimes`, so are not allocated in a
           :term:`nursery space` of a :term:`generational garbage
           collector <generational garbage collection>`.

    large page

        .. see:: :term:`huge page`.

    leaf object

        .. aka:: *atomic object*.

        A leaf object is an :term:`object` that does not
        :term:`reference` any other objects.

        In a typed language, the compiler can often determine at
        compile time that certain types can be represented as leaf
        objects. Usually these types are either a :term:`scalar data
        type` or a :term:`vector data type` of scalars with bounded
        magnitude.

        .. relevance::

            If leaf objects can be identified, a :term:`garbage
            collector` can make certain optimizations: leaf objects do
            not have to be :term:`scanned <scan>` for references nor
            are :term:`barrier (1)` needed to detect
            and maintain references in the object.

    leak

        .. see:: :term:`memory leak`.

    life

        .. see:: :term:`lifetime`.

    lifetime

        .. aka:: *extent*, *life*.

        The lifetime or extent of an :term:`object` is the time for
        which the object is :term:`live`.

        .. seealso:: :term:`dynamic extent`, :term:`indefinite extent`.

    LIFO-ordered first fit

        The :term:`allocation policy` that always uses the
        most-recently :term:`freed (1)` suitable :term:`free block`.
        Commonly implemented by pushing freed blocks on the front of a
        :term:`free block chain`, and then using :term:`first fit`
        allocation on this chain. :term:`free (1)` can be very quick,
        depending on the :term:`coalescing <coalesce>` policy.

        This policy may suffer from severe :term:`fragmentation` in
        the presence of short-lived large objects of a single size. As
        smaller objects are allocated, the free block chain fills up
        with fragments a little smaller than the large object size.

        .. seealso:: :term:`FIFO-ordered first fit`, :term:`address-ordered first fit`.

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

    limited-field reference count

        .. aka:: *sticky reference count*.

        A :term:`reference counting` technique whereby the field used
        to store the number of :term:`references` to an
        :term:`object` has a limited size. In particular, the field is
        not large enough to represent the maximum possible number of
        references to an object.

        Using the observation that most objects are not referenced a
        great number of times, some systems that use reference counts
        only store the count accurately up to a certain maximum value.
        If an object has more references than the maximum then the
        count "sticks" at the maximum and is never decremented. Such
        objects are expected to be rare, but their :term:`memory (1)`
        can never be :term:`reclaimed` using reference counting. A
        separate (infrequently run) :term:`tracing garbage collector
        <tracing garbage collection>` is often employed to reclaim
        this storage.

        A degenerate form of limited-field reference counting is
        :term:`one-bit reference counting <one-bit reference count>`
        where an object is considered to be referenced either exactly
        once or many times.

    linear addressing

        In linear addressing, :term:`addresses` form a
        single, continuous :term:`address space`. This term is used
        mostly in opposition to :term:`segmented addressing`.

        .. opposite:: :term:`segmented addressing`.

    live

        .. aka:: *alive*, *active*.

        :term:`Memory (2)` or an :term:`object` is live if the program
        will read from it in future. The term is often used more
        broadly to mean :term:`reachable`.

        It is not possible, in general, for :term:`garbage collectors`
        to determine exactly which :term:`objects` are still live.
        Instead, they use some approximation to detect objects that
        are provably :term:`dead`, such as those that are not
        :term:`reachable`.

        .. similar:: :term:`reachable`.

        .. opposite:: :term:`dead`.

        .. seealso:: :term:`undead`.

    load

        To transfer data from :term:`memory (2)` to a processor's
        :term:`registers`.

        Load can also be used in the more general sense of moving data
        from a part of the :term:`memory hierarchy` that is slow to
        access to one that is fast to access (For example, "it takes
        about 3 ms for the :term:`virtual memory` system to load a
        :term:`page` from disk on this system"). When used in this
        sense, the qualified term :term:`cache (2)` load is common.

        ``LOAD`` (or an abbreviation) is also commonly used in many
        processor architectures as the mnemonic name for the machine
        code instructions that are used primarily to make data
        accessible to the CPU (by loading the data into registers
        usually). In RISC architectures it is common for the load
        instructions to be the only means of making data accessible to
        the CPU; in CISC architectures it is common for a wide variety
        of instructions to implicitly or explicitly load data from
        memory.

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

    locality of reference

        Locality of reference is the extent to which successive
        accesses of nearby :term:`memory (1)` :term:`locations <memory
        location>` are nearby in time; for example, a program that
        reads all the elements of a contiguous array in turn or that
        repeatedly uses the same memory variable has good locality of
        reference.

        Good locality of reference interacts well with :term:`virtual
        memory` and :term:`memory caches <cache (1)>`, as it reduces
        the :term:`working set` and improves the :term:`hit rate`.

        There are a number of specialized senses of locality of
        reference in certain fields such as distributed systems; these
        are not covered in depth here.

        .. relevance::

            A :term:`mutator` may exhibit predictable properties such
            as accessing in turn :term:`objects` which were
            :term:`allocated` in turn, or accessing in turn objects
            which have :term:`references` to each other. An
            intelligent :term:`allocator` or :term:`copying garbage
            collector <copying garbage collection>` can use this
            observation to improve locality of reference.

        .. bibref:: :ref:`Grunwald et al. (1993) <GZH93>`, :ref:`Wilson et al. (1992) <WLM92>`.

    location

        .. see:: :term:`memory location`.

    location dependency

        .. mps:specific::

            A *location dependency* records the fact that the
            :term:`client program` depends on the bit patterns of some
            :term:`references` (and not merely on the
            identity of the :term:`block` to which the reference
            refers), and provides a function
            (:c:func:`mps_ld_isstale`) to find out whether any of
            these references have been changed because a block has
            been :term:`moved <moving garbage collector>`. See
            :ref:`topic-location`.

    lock free

        A multi-threaded program is *lock free* if all schedules for
        the threads make progress: in particular, no schedule leads to
        deadlock. This is most easily implemented by avoiding taking
        locks.

    logical address

        .. see:: :term:`virtual address`.

    longword

        .. see:: :term:`doubleword`.

