[9e7c20]: gc.xmlf Maximize Restore History

Download this file

gc.xmlf    564 lines (553 with data), 25.7 kB

<?xml version="1.0"?><!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.4//EN" "http://www.oasis-open.org/docbook/xml/4.4/docbookx.dtd">
<book lang="en">
 <chapter id="Memory-management">
  <title>Memory Management</title>
  <para>The following sections only apply to the &ECL; original garbage collector.
  If &ECL; is not compiled with <literal>--disable-boehm</literal>, then an alternative,
  less restrictive garbage collector is installed, with the disadvantage
  that many of the following functions <literal>#'room</literal>, <literal>si:*gc-verbose*</literal>,
  &hellip; do no longer work.</para>

  <section id="Implementation-types">
   <title>Implementation Types</title>
   <para>Each &ECL; object belongs to one of the 22 <emphasis>implementation types</emphasis>.  The
   implementation types are shown in Table 4-1 with the corresponding Common-Lisp
   data types.  In the table, the compiled functions are divided into three
   implementation types; <literal>cfun</literal> is the type of compiled functions without
   environment, <literal>cclosure</literal> is the type of compiled functions with environment
   (i.e., the type of compiled closures) and <literal>gfun</literal> is the type of compiled
   generic functions of CLOS.</para>
   <para>Table 4-1  Implementation Types</para>
   <informaltable>
    <tgroup cols="2">
     <colspec colwidth="42*"></colspec>
     <colspec colwidth="77*"></colspec>
     <tbody>
      <row>
       <entry><emphasis role="bold"><emphasis>Implementation Type</emphasis></emphasis></entry>
       <entry><emphasis role="bold"><emphasis>Common-Lisp Data Type</emphasis></emphasis></entry>
      </row>
      <row>
       <entry><literal>cons</literal></entry>
       <entry><literal>cons</literal></entry>
      </row>
      <row>
       <entry><literal>fixnum</literal></entry>
       <entry><literal>fixnum</literal></entry>
      </row>
      <row>
       <entry><literal>bignum</literal></entry>
       <entry><literal>bignum</literal></entry>
      </row>
      <row>
       <entry><literal>ratio</literal></entry>
       <entry><literal>ratio</literal></entry>
      </row>
      <row>
       <entry><literal>short-float</literal></entry>
       <entry><literal>short-float</literal></entry>
      </row>
      <row>
       <entry><literal>long-float</literal></entry>
       <entry><literal>long-float (= double-float = single-float)</literal></entry>
      </row>
      <row>
       <entry><literal>complex</literal></entry>
       <entry><literal>complex</literal></entry>
      </row>
      <row>
       <entry><literal>character</literal></entry>
       <entry><literal>character</literal></entry>
      </row>
      <row>
       <entry><literal>symbol</literal></entry>
       <entry><literal>symbol</literal></entry>
      </row>
      <row>
       <entry><literal>package</literal></entry>
       <entry><literal>package</literal></entry>
      </row>
      <row>
       <entry><literal>hash-table</literal></entry>
       <entry><literal>hash-table</literal></entry>
      </row>
      <row>
       <entry><literal>array</literal></entry>
       <entry><literal>(and array (not vector))</literal></entry>
      </row>
      <row>
       <entry><literal>vector</literal></entry>
       <entry><literal>(and vector (not string) (not bit-vector))</literal></entry>
      </row>
      <row>
       <entry><literal>string</literal></entry>
       <entry><literal>string</literal></entry>
      </row>
      <row>
       <entry><literal>bit-vector</literal></entry>
       <entry><literal>bit-vector</literal></entry>
      </row>
      <row>
       <entry><literal>structure</literal></entry>
       <entry><literal>structure</literal></entry>
      </row>
      <row>
       <entry><literal>stream</literal></entry>
       <entry><literal>stream</literal></entry>
      </row>
      <row>
       <entry><literal>random-state</literal></entry>
       <entry><literal>random-state</literal></entry>
      </row>
      <row>
       <entry><literal>readtable</literal></entry>
       <entry><literal>readtable</literal></entry>
      </row>
      <row>
       <entry><literal>cfun</literal></entry>
       <entry><literal>compiled-function  without environment</literal></entry>
      </row>
      <row>
       <entry><literal>cclosure</literal></entry>
       <entry><literal>compiled-function  with environment</literal></entry>
      </row>
      <row>
       <entry><literal>gfun</literal></entry>
       <entry><literal>none (CLOS generic-function)</literal></entry>
      </row>
      <row>
       <entry><literal>instance</literal></entry>
       <entry><literal>none (CLOS instance)</literal></entry>
      </row>
      <row>
       <entry><literal>thread</literal></entry>
       <entry><literal>none (thread)</literal></entry>
      </row>
      <row>
       <entry></entry>
      </row>
     </tbody>
    </tgroup>
   </informaltable>
   <para>Each object is represented by a cell allocated in the heap area of the
   interpreter.  The size of the cell is determined by the implementation type of
   the object.</para>
   <para>The implementation types are classified according to the size of the cells for
   the objects of the type, as shown in Table 4-2.  The size of the cells in the
   same type class is the same.</para>
   <para>Table 4-2  Classification of Implementation Types</para>
   <informaltable>
    <tgroup cols="2">
     <colspec colwidth="28*"></colspec>
     <colspec colwidth="43*"></colspec>
     <tbody>
      <row>
       <entry>1</entry>
       <entry><literal>CONS BIGNUM RATIO COMPLEX STRUCTURE</literal></entry>
      </row>
      <row>
       <entry>2</entry>
       <entry><literal>SHORT-FLOAT RANDOM-STATE READTABLE</literal></entry>
      </row>
      <row>
       <entry>3</entry>
       <entry><literal>LONG-FLOAT CFUN CCLOSURE</literal></entry>
      </row>
      <row>
       <entry>4</entry>
       <entry><literal>SYMBOL</literal></entry>
      </row>
      <row>
       <entry>5</entry>
       <entry><literal>PACKAGE</literal></entry>
      </row>
      <row>
       <entry>6</entry>
       <entry><literal>ARRAY HASH-TABLE VECTOR BIT-VECTOR STREAM</literal></entry>
      </row>
      <row>
       <entry>7</entry>
       <entry><literal>STRING</literal></entry>
      </row>
      <row>
       <entry>8</entry>
       <entry><literal>PATHNAME</literal></entry>
      </row>
     </tbody>
    </tgroup>
   </informaltable>
   <para>For objects of the (implementation) types <literal>readtable</literal>, <literal>symbol</literal>,
   <literal>package</literal>, <literal>array</literal>, <literal>hash-table</literal>, <literal>vector</literal>,
   <literal>bit-vector</literal>, <literal>stream</literal>, <literal>cclosure</literal>, <literal>string</literal>, <literal>cfun</literal>,
   and <literal>structure</literal> (or <literal>instance</literal>), the cell is simply a header of the
   object.  The body of the object is allocated separately from the cell and is
   managed in a different manner.  The memory space occupied by the body of such
   an object is called a <firstterm>block</firstterm>.  A block is either <firstterm>contiguous</firstterm> or
   <firstterm>relocatable</firstterm> depending on the area in which it is allocated.  The
   difference between the two areas will be explained below.  Table 4-3 lists
   these types, along with the contents of the body and the kind of the block.</para>
   <para>Table 4-3  Types with Bodies</para>
   <informaltable>
    <tgroup cols="3">
     <colspec colwidth="27*"></colspec>
     <colspec colwidth="27*"></colspec>
     <colspec colwidth="28*"></colspec>
     <tbody>
      <row>
       <entry><literal>readtable</literal></entry>
       <entry><literal>read table</literal></entry>
       <entry><literal>contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>symbol</literal></entry>
       <entry><literal>symbol name</literal></entry>
       <entry><literal>relocatable</literal></entry>
      </row>
      <row>
       <entry><literal>package</literal></entry>
       <entry><literal>hash table</literal></entry>
       <entry><literal>contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>array</literal></entry>
       <entry><literal>array body</literal></entry>
       <entry><literal>relocatable or contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>hash-table</literal></entry>
       <entry><literal>hash table</literal></entry>
       <entry><literal>relocatable</literal></entry>
      </row>
      <row>
       <entry><literal>vector</literal></entry>
       <entry><literal>vector body</literal></entry>
       <entry><literal>relocatable or contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>bit-vector</literal></entry>
       <entry><literal>bit-vector body</literal></entry>
       <entry><literal>relocatable or contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>stream</literal></entry>
       <entry><literal>I/O buffer</literal></entry>
       <entry><literal>contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>cclosure</literal></entry>
       <entry><literal>code</literal></entry>
       <entry><literal>contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>string</literal></entry>
       <entry><literal>string body</literal></entry>
       <entry><literal>relocatable or contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>cfun</literal></entry>
       <entry><literal>code</literal></entry>
       <entry><literal>contiguous</literal></entry>
      </row>
      <row>
       <entry><literal>structure</literal></entry>
       <entry><literal>structure body</literal></entry>
       <entry><literal>relocatable</literal></entry>
      </row>
      <row>
       <entry><literal>instance</literal></entry>
       <entry><literal>instance slots</literal></entry>
       <entry><literal>relocatable</literal></entry>
      </row>
      <row>
       <entry><literal>thread</literal></entry>
       <entry><literal>thread data</literal></entry>
       <entry><literal>contiguous</literal></entry>
      </row>
     </tbody>
    </tgroup>
   </informaltable>
   <para>Usually, the body of an array, a vector, a bit-vector, or a string is allocated
   as a relocatable block.  In &ECL;, the function <literal>make-array</literal> takes an
   extra keyword argument <replaceable>:static</replaceable>.  If the <replaceable>:static</replaceable> argument is supplied
   with a non-() value, then the body of the array is allocated as a
   contiguous block.</para>
  </section>

  <section id="Heap-and-relocatable-areas">
   <title>Heap and Relocatable Areas</title>
   <para>The memory space of &ECL; is divided into two parts: the heap area and the
   relocatable area.  Both areas occupy a contiguous space in the memory.</para>
   <para>Cells of &ECL; objects are allocated in the heap.  &ECL; divides the heap
   into pages (1 page = 2048 bytes), and each page consists of cells in the same
   type class (see Table 4-2).  Cells in different type classes are allocated in
   different pages.  Some blocks are also allocated in the heap: They are called
   contiguous blocks.  The pages for contiguous blocks contain only contiguous
   blocks.  Thus each page in the heap is either a page for cells in a particular
   type class, or a page for contiguous blocks.  Blocks not in the heap are called
   relocatable blocks and are allocated in the relocatable area.</para>
   <para>The user may specify the maximum number of pages that can be allocated for each
   type class by calling the &ECL; specific function <literal>allocate</literal>.  There is
   also a limit on the number of pages for contiguous blocks; the limit can be
   altered by calling the &ECL; specific function
   <literal>allocate-contiguous-pages</literal> size of the relocatable area is specified by
   the &ECL; specific function <literal>allocate-relocatable-pages</literal>.  See Section
   4.4 for these functions.</para>
   <para>In some installations of &ECL;, the total amount of memory that &ECL; can
   use is limited.  In such cases, the entire memory may become exhausted before
   the maximum number of pages for each type class, for contiguous blocks, or for
   the relocatable area have been allocated.</para>
   <para>The heap lies in a part of memory with lower address than the relocatable area
   and there is a &ldquo;hole&rdquo; between the two areas (see Figure 4-1).  On request for
   a new page of heap, the page with the lowest address in the hole is used.  When
   the hole is exhausted, the relocatable area is shifted toward the higher
   address space and a new hole of an appropriate size is created between the two
   areas.</para>
   <para>Figure 4-1  Heap and Relocatable Area</para>
   <screen><![CDATA[
   Lower address                         Higher address
   +--------------+-------------------+---------------+
   + HEAP         |   HOLE            | RELOCATABLE   |
   +--------------+-------------------+---------------+
   ]]></screen>
  </section>

  <section id="The-garbage-collector">
   <title>The Garbage Collector</title>
   <para>&ECL; uses a <emphasis>conservative garbage collection</emphasis> technique for collecting
   the C stack and a type accurate technique for areas containing Lisp objects.
   Scanning conservatively the C stack, looking for potential pointers to Lisp
   objects, ensures that no live Lisp objects get collected, even if they are
   passed to external procedures in C or some other language.  This approach
   greatly simplifies integration of Lisp and C code, since it is not necessary to
   protect Lisp object form collection when a foreign function is invoked.</para>
   <para>The garbage collector of &ECL; has three levels according to what it
   collects:</para>
   <orderedlist numeration="arabic">
    <listitem>
     <para>cells</para>
    </listitem>
    <listitem>
     <para>cells and relocatable blocks</para>
    </listitem>
    <listitem>
     <para>cells, relocatable blocks and contiguous blocks.</para>
    </listitem>
   </orderedlist>
   <para>In levels 2 and 3, the relocatable area is shifted to the higher address space
   to reserve an appropriate number of pages in the hole.</para>
   <para>For each type class, &ECL; keeps a free list of unused cells, and when the
   free list is exhausted, a new page is allocated, or the garbage collector is
   invoked, depending on whether the maximum number of pages for that class have
   been allocated or not.</para>
   <para>The garbage collector does not compact the heap.  That is, cells and
   contiguous blocks are never moved to another place.  Moreover, once a page is
   allocated for a particular type class or for contiguous blocks, that page will
   never be freed for other classes, even if the entire page becomes garbage.</para>
   <para>On the other hand, the relocatable area is compacted during level 2 and
   level 3 of garbage collection.  A relocatable block is really relocatable.</para>
   <para>The garbage collector is automatically invoked in one of the following
   situations.  The number in the parentheses indicates the level of garbage
   collection that is performed.</para>
   <orderedlist numeration="arabic">
    <listitem>
     <para>The free list of a certain type class is exhausted
     after the maximum number of pages have been allocated for that type class (1).</para>
    </listitem>
    <listitem>
     <para>The hole is exhausted (2).</para>
    </listitem>
    <listitem>
     <para>The relocatable area is exhausted after the maximum number of
     pages have been allocated for the relocatable area (2).</para>
    </listitem>
    <listitem>
     <para>The contiguous blocks are exhausted after the maximum number of
     pages have been allocated for contiguous blocks (3).</para>
    </listitem>
   </orderedlist>
   <para>The garbage collector is also invoked by the following &ECL; specific
   function.</para>
   <blockquote>
    <screen><indexterm role="fn"><primary>system</primary></indexterm>&mdash; Function: <function>system</function> <varname>gc</varname> <varname>x</varname></screen>
    <para>The garbage collector is invoked with the level specified by <replaceable>x</replaceable>.  If
    <replaceable>x</replaceable> is (), the garbage collector is invoked for level 1 garbage
    collection.  If <replaceable>x</replaceable> is <replaceable>T</replaceable>, it is invoked for level 3 garbage
    collection.  Otherwise, it is invoked for level 2 garbage collection.  If
    <literal>sys:*gc-verbose*</literal> is non-(), then it print messages at the start and
    end of each garbage collection.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="vr"><primary>*gc-verbose*</primary></indexterm>&mdash; Variable: <varname>*gc-verbose*</varname>[<type>system</type>] <type>This</type> <varname>variable</varname> <type>controls</type> <varname>whether</varname> <type>to</type> <varname>print</varname> <type>messages</type></screen>
    <para>at the start and end of each garbage collection.  If <literal>sys:*gc-verbose*</literal> is
    (), <literal>gc</literal> fore goes printing any messages.  The default value is <literal>T</literal>.</para>
   </blockquote>
  </section>

  <section id="Allocation-functions">
   <title>Allocation Functions</title>
   <para>The following functions are used to set or inspect the (maximum)
   number of pages for each type class, for contiguous blocks, or for
   relocatable blocks.</para>
   <blockquote>
    <screen><indexterm role="fn"><primary>allocate</primary></indexterm>&mdash; extensions: <function>allocate</function> <varname>type</varname> <varname>number</varname></screen>
    <para>Sets the maximum number of pages for the type class of the implementation type
    <replaceable>type</replaceable> to <replaceable>number</replaceable>.  If more than <replaceable>number</replaceable> pages have already been
    allocated, an error is signalled.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="fn"><primary>allocated-pages</primary></indexterm>&mdash; sys: <function>allocated-pages</function> <varname>type</varname></screen>
    <para>Returns the number of pages currently allocated for the type class of the
    implementation type <replaceable>type</replaceable>.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="fn"><primary>maximum-allocatable-pages</primary></indexterm>&mdash; sys: <function>maximum-allocatable-pages</function> <varname>type</varname></screen>
    <para>Returns the current maximum number of pages for type class of the
    implementation type <replaceable>type</replaceable>.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="fn"><primary>allocate-contiguous-pages</primary></indexterm>&mdash; sys: <function>allocate-contiguous-pages</function> <varname>number</varname></screen>
    <para>Sets the maximum number of pages for contiguous blocks to <replaceable>number</replaceable>.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="fn"><primary>allocated-contiguous-pages</primary></indexterm>&mdash; sys: <function>allocated-contiguous-pages</function></screen>
    <para>Returns the number of pages allocated for contiguous blocks.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="fn"><primary>maximum-contiguous-pages</primary></indexterm>&mdash; sys: <function>maximum-contiguous-pages</function></screen>
    <para>Returns the current maximum number of pages for contiguous blocks.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="fn"><primary>allocate-relocatable-pages</primary></indexterm>&mdash; sys: <function>allocate-relocatable-pages</function> <varname>number</varname></screen>
    <para>Sets the maximum number of pages for relocatable blocks to <replaceable>number</replaceable>.  The
    relocatable area is expanded to <replaceable>number</replaceable> pages immediately.
    Therefore,&ldquo;the current maximum number&rdquo; and &ldquo;the number of pages allocated&rdquo;
    have the same meanings for relocatable blocks.</para>
   </blockquote>
   <blockquote>
    <screen><indexterm role="fn"><primary>allocated-relocatable-pages</primary></indexterm>&mdash; sys: <function>allocated-relocatable-pages</function></screen>
    <para>Returns the number of pages allocated for relocatable blocks.</para>
   </blockquote>
   <para>If the pages for a particular type class are exhausted after the maximum number
   of pages for that class have been allocated, and if there remain no free cells
   (actually, if there remain very few cells), &ECL; behaves as directed by the
   argument that was initially passed to the &ECL; specific function <literal>(si::ignore-maximum-pages)</literal>.  If the
   value is (), then &ECL; signals a correctable error and enters the break loop.
   The user can reset the maximum number by calling <literal>allocate</literal> and then
   continue the execution of the program by typing <replaceable>:r</replaceable>.</para>
   <para>Example:</para>
   <para><screen>
    &gt;(make-list 100000)

    Correctable error: The storage for CONS is exhausted.
    Currently, 531 pages are allocated.
    Use ALLOCATE to expand the space.
    Signalled by MAKE-LIST.

    Broken at FUNCALL.
    &gt;&gt;(ALLOCATE 'CONS 1000)
    t

    &gt;&gt;:r

    (nil nil nil nil nil nil nil nil nil nil ............
   </screen></para>
   <para>The user can also reset the maximum number of pages for relocatable blocks and
   for contiguous blocks in a similar manner.  On the other hand, if the value of
   <literal>(si::ignore-maximum-pages)</literal> is non-(), then &ECL; automatically
   increments the maximum number of pages for the class by 50 percent.  The
   initial value of <literal>(si::ignore-maximum-pages)</literal> is <replaceable>T</replaceable>.</para>
  </section>

  <section id="Storage-information">
   <title>Storage Information</title>
   <blockquote>
    <screen><indexterm role="fn"><primary>room</primary></indexterm>&mdash; Function: <function>room</function> <varname>&amp;optional x</varname></screen>
    <para>The function <literal>room</literal> prints the storage information.  The argument
    <replaceable>x</replaceable>  is simply ignored and
    the output of <literal>room</literal>  is always in the same
    format.  <literal>room</literal>  prints the following information:</para>
   </blockquote>
   <itemizedlist mark="bullet">
    <listitem>
     <para>for each type class</para>
     <itemizedlist mark="bullet">
      <listitem>
       <para>the number of pages so-far allocated for the type class</para>
      </listitem>
      <listitem>
       <para>the maximum number of pages for the type class</para>
      </listitem>
      <listitem>
       <para>the percentage of used cells to cells so-far allocated</para>
      </listitem>
      <listitem>
       <para>the number of times the garbage collector has been
       called to collect cells of the type class</para>
      </listitem>
      <listitem>
       <para>the implementation types that belong to the type class</para>
      </listitem>
     </itemizedlist>
    </listitem>
    <listitem>
     <para>the number of pages actually allocated for contiguous blocks</para>
    </listitem>
    <listitem>
     <para>the maximum number of pages for contiguous blocks</para>
    </listitem>
    <listitem>
     <para>the number of times the garbage collector has been called to
     collect contiguous blocks</para>
    </listitem>
    <listitem>
     <para>the number of pages in the hole</para>
    </listitem>
    <listitem>
     <para>the maximum number of pages for relocatable blocks</para>
    </listitem>
    <listitem>
     <para>the number of times the garbage collector has been called to
     collect relocatable blocks</para>
    </listitem>
    <listitem>
     <para>the total number of pages allocated for cells</para>
    </listitem>
    <listitem>
     <para>the total number of pages allocated</para>
    </listitem>
    <listitem>
     <para>the number of available pages</para>
    </listitem>
    <listitem>
     <para>the number of pages &ECL; can use.</para>
    </listitem>
   </itemizedlist>
   <para>The number of times the garbage collector has been called is not shown, if the
   number is zero.</para>
   <para>In the following example, the maximum of <literal>531</literal> pages have already been
   allocated for the type class to which cons belongs, but only 16.9 percent of
   the cells are actually used.  The garbage collector was once invoked to collect
   cells in this type class.</para>
   <para><screen>
    &gt; (room)
    200/200   48.4%    CONS BIGNUM RATIO COMPLEX STRUCTURE
    1/5      7.4%    SHORT-FLOAT RANDOM-STATE READTABLE
    10/34    99.3%    LONG-FLOAT CFUN CCLOSURE
    47/64    71.9%    SYMBOL
    1/1      8.9%    PACKAGE
    2/69    81.8%    ARRAY HASH-TABLE VECTOR BIT-VECTOR STREAM
    16/40    95.9%    STRING
    1/1      6.8%    PATHNAME

    0/271            contiguous (1 blocks)
    127            hole
    40     3.4%    relocatable

    278 pages for cells
    445 total pages
    14709 pages available
    1230 pages in heap but not gc'd + pages needed for gc marking
    16384 maximum pages
   </screen></para>
  </section>
 </chapter>
</book>
<!-- Keep this comment at the end of the file
      Local variables:
      mode: nxml
      sgml-parent-document: "ecl.xml"
      sgml-indent-step: 1
      nxml-child-indent: 1
      nxml-outline-child-indent: 1
      fill-column: 79
      End:
-->