libstdc++-v3/docs/html/20_util/allocator.html

   1 <?xml version="1.0" encoding="ISO-8859-1"?>
   2 <!DOCTYPE html
   3           PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   4           "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   5
   6 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   7 <head>
   8    <meta name="AUTHOR" content="pme@gcc.gnu.org (Phil Edwards) and bkoz@gcc.gnu.org (Benjamin Kosnik)" />
   9    <meta name="KEYWORDS" content="c++, libstdc++, g++, allocator, memory" />
  10    <meta name="DESCRIPTION" content="Allocators and allocation" />
  11    <meta name="GENERATOR" content="emacs and ten fingers" />
  12    <title>Allocators and allocation</title>
  13 <link rel="StyleSheet" href="../lib3styles.css" type="text/css" />
  14 <link rel="Start" href="../documentation.html" type="text/html"
  15   title="GNU C++ Standard Library" />
  16 <link rel="Bookmark" href="howto.html" type="text/html"
  17   title="General Utilities" />
  18 <link rel="Copyright" href="../17_intro/license.html" type="text/html" />
  19 </head>
  20 <body>
  21
  22 <h1 class="centered"><a name="top">Allocators and allocation</a></h1>
  23
  24 <p class="fineprint"><em>
  25    The latest version of this document is always available at
  26    <a href="http://gcc.gnu.org/onlinedocs/libstdc++/20_util/allocator.html">
  27    http://gcc.gnu.org/onlinedocs/libstdc++/20_util/allocator.html</a>.
  28 </em></p>
  29
  30 <p><em>
  31    To the <a href="http://gcc.gnu.org/libstdc++/">libstdc++-v3 homepage</a>.
  32 </em></p>
  33
  34 <!-- ####################################################### -->
  35 <hr />
  36 <p> The C++ Standard encapsulates memory management characteristics
  37    for strings, container classes, and parts of iostreams in a
  38    template class called <code>std::allocator</code>.
  39 </p>
  40
  41 <h3 class="left">
  42   <a name="standard_requirements">Standard requirements</a>
  43 </h3>
  44    <p>The C++ standard only gives a few directives in this area:
  45    </p>
  46    <ul>
  47      <li>When you add elements to a container, and the container must allocate
  48          more memory to hold them, the container makes the request via its
  49          <code>Allocator</code> template parameter.  This includes adding
  50          chars to the string class, which acts as a regular STL container
  51          in this respect.
  52      </li>
  53      <li>The default <code>Allocator</code> of every container-of-T is
  54          <code>std::allocator&lt;T&gt;</code>.
  55      </li>
  56      <li>The interface of the <code>allocator&lt;T&gt;</code> class is
  57          extremely simple.  It has about 20 public declarations (nested
  58          typedefs, member functions, etc), but the two which concern us most
  59          are:
  60          <pre>
  61       T*    allocate   (size_type n, const void* hint = 0);
  62       void  deallocate (T* p, size_type n);</pre>
  63          (This is a simplification; the real signatures use nested typedefs.)
  64          The <code>&quot;n&quot;</code> arguments in both those functions is a
  65          <em>count</em> of the number of T's to allocate space for,
  66          <em>not their total size</em>.
  67      </li>
  68      <li>&quot;The storage is obtained by calling
  69          <code>::operator new(size_t)</code>, but it is unspecified when or
  70          how often this function is called.  The use of <code>hint</code>
  71          is unspecified, but intended as an aid to locality if an
  72          implementation so desires.&quot; [20.4.1.1]/6
  73       </li>
  74    </ul>
  75
  76    <p> Complete details cam be found in the C++ standard, look in
  77    [20.4 Memory].
  78    </p>
  79
  80 <h3 class="left">
  81   <a name="probs_possibilities">Problems and Possibilities</a>
  82 </h3>
  83    <p>The easiest way of fulfilling the requirements is to call operator new
  84       each time a container needs memory, and to call operator delete each
  85       time the container releases memory.  <strong>BUT</strong>
  86       <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html">this
  87       method is horribly slow</a>.
  88    </p>
  89    <p>Or we can keep old memory around, and reuse it in a pool to save time.
  90       The old libstdc++-v2 used a memory pool, and so do we.  As of 3.0,
  91       <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00136.html">it's
  92       on by default</a>.  The pool is shared among all the containers in the
  93       program:  when your program's std::vector&lt;int&gt; gets cut in half
  94       and frees a bunch of its storage, that memory can be reused by the
  95       private std::list&lt;WonkyWidget&gt; brought in from a KDE library
  96       that you linked against.  And we don't have to call operators new and
  97       delete to pass the memory on, either, which is a speed bonus.
  98       <strong>BUT</strong>...
  99    </p>
 100    <p>What about threads?  No problem:  in a threadsafe environment, the
 101       memory pool is manipulated atomically, so you can grow a container in
 102       one thread and shrink it in another, etc.  <strong>BUT</strong> what
 103       if threads in libstdc++-v3 aren't set up properly?
 104       <a href="../faq/index.html#5_6">That's been answered already</a>.
 105    </p>
 106    <p><strong>BUT</strong> what if you want to use your own allocator?  What
 107       if you plan on using a runtime-loadable version of malloc() which uses
 108       shared telepathic anonymous mmap'd sections serializable over a
 109       network, so that memory requests <em>should</em> go through malloc?
 110       And what if you need to debug it?
 111    </p>
 112
 113 <h3 class="left">
 114   <a name="stdallocator">Implementation details of <code>std::allocator</code></a>
 115 </h3>
 116    <p> The implementation of <code> std::allocator</code> has continued
 117       to evolve through successive releases. Here's a brief history.
 118    </p>
 119
 120 <h5 class="left">
 121   <a name="30allocator"> 3.0, 3.1, 3.2, 3.3 </a>
 122 </h5>
 123    <p> During this period, all allocators were written to the SGI
 124    style, and all STL containers expected this interface. This
 125    interface had a traits class called <code>_Alloc_traits</code> that
 126    attempted to provide more information for compile-time allocation
 127    selection and optimization. This traits class had another allocator
 128    wrapper, <code>__simple_alloc&lt;T,A&gt;</code>, which was a
 129    wrapper around another allocator, A, which itself is an allocator
 130    for instances of T. But wait, there's more:
 131    <code>__allocator&lt;T,A&gt;</code> is another adapter.  Many of
 132    the provided allocator classes were SGI style: such classes can be
 133    changed to a conforming interface with this wrapper:
 134    <code>__allocator&lt;T, __alloc&gt;</code> is thus the same as
 135    <code>allocator&lt;T&gt;</code>.
 136    </p>
 137
 138    <p> The class <code>std::allocator</code> use the typedef
 139    <code>__alloc</code> to select an underlying allocator that
 140    satisfied memory allocation requests. The selection of this
 141    underlying allocator was not user-configurable.
 142    </p>
 143
 144 <h5 class="left">
 145   <a name="34allocator"> 3.4 </a>
 146 </h5>
 147    <p> For this and later releases, the only allocator interface that
 148    is support is the standard C++ interface. As such, all STL
 149    containers have been adjusted, and all external allocators have
 150    been modified to support this change. Because of this,
 151    <code>__simple_alloc, __allocator, __alloc, </code> and <code>
 152    _Alloc_traits</code> have all been removed.
 153    </p>
 154
 155    <p> The class <code>std::allocator</code> just has typedef,
 156    constructor, and rebind members. It inherits from one of the
 157    high-speed extension allocators, covered below. Thus, all
 158    allocation and deallocation depends on the base class.
 159    </p>
 160
 161   <p> The base class that <code>std::allocator</code> is derived from
 162   is not user-configurable.
 163   </p>
 164
 165 <h5 class="left">
 166   <a name="benchmarks"> How the default allocation strategy is selected.</a>
 167 </h5>
 168    <p> It's difficult to pick an allocation strategy that will provide
 169    maximum utility, without excessively penalizing some behavior. In
 170    fact, it's difficult just deciding which typical actions to measure
 171    for speed.
 172    </p>
 173
 174    <p> Three synthetic benchmarks have been created that provide data
 175    that is used to compare different C++ allocators. These tests are:
 176    </p>
 177
 178    <ul>
 179      <li>Insertion. Over multiple iterations, various STL container
 180      objects have elements inserted to some maximum amount. A variety
 181      of allocators are tested.
 182      Test source <a
 183      href="http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc%2b%2b-v3/testsuite/performance/20_util/allocator/insert.cc?only_with_tag=MAIN">here.</a>
 184      </li>
 185
 186      <li>Insertion, clear, and re-insertion in a multi-threaded
 187      environment.  Over multiple iterations, several threads are
 188      started that insert elements into a STL container, then assign a
 189      null instance of the same type to clear memory, and then
 190      re-insert the same number of elements. Several STL containers and
 191      multiple allocators are tested. This test shows the ability of
 192      the allocator to reclaim memory on a pre-thread basis, as well as
 193      measuring thread contention for memory resources.
 194      Test source
 195     <a href="http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc%2b%2b-v3/testsuite/performance/20_util/allocator/insert_insert.cc">
 196     here.</a>
 197      </li>
 198
 199      <li>A threaded producer/consumer model.
 200      Test source
 201     <a href="http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc%2b%2b-v3/testsuite/performance/20_util/allocator/producer_consumer.cc">
 202     here.</a>
 203      </li>
 204    </ul>
 205
 206 <h5 class="left">
 207   <a name="forcenew"> Disabling memory caching.</a>
 208 </h5>
 209    <p> In use, <code>std::allocator</code> may allocate and deallocate
 210    using implementation-specified strategies and heuristics. Because of
 211    this, every call to an allocator object's <code> allocate</code>
 212    member function may not actually call the global operator new. This
 213    situation is also duplicated for calls to the <code>
 214    deallocate</code> member function.
 215    </p>
 216
 217    <p> This can be confusing.
 218    </p>
 219
 220    <p> In particular, this can make debugging memory errors more
 221    difficult, especially when using third party tools like valgrind or
 222    debug versions of <code> new</code>.
 223    </p>
 224
 225    <p> There are various ways to solve this problem. One would be to
 226    use a custom allocator that just called operators <code> new
 227    </code> and <code> delete</code> directly, for every
 228    allocation. (See include/ext/new_allocator.h, for instance.)
 229    However, that option would involve changing source code to use the a
 230    non-default allocator. Another option is to force the default
 231    allocator to remove caching and pools, and to directly allocate
 232    with every call of <code> allocate</code> and directly deallocate
 233    with every call of <code> deallocate</code>, regardless of
 234    efficiency. As it turns out, this last option is available,
 235    although the exact mechanism has evolved with time.
 236    </p>
 237
 238    <p> For GCC releases from 2.95 through the 3.1 series, defining
 239    <code>__USE_MALLOC</code> on the gcc command line would change the
 240    default allocation strategy to instead use <code> malloc</code> and
 241    <code> free</code>. See
 242    <a href="../23_containers/howto.html#3">this note</a>
 243    for details as to why this was something needing improvement.
 244    </p>
 245
 246    <p>Starting with GCC 3.2, and continued in the 3.3 series, to
 247       globally disable memory caching within the library for the
 248       default allocator, merely set GLIBCPP_FORCE_NEW (at this time,
 249       with any value) in the system's environment before running the
 250       program. If your program crashes with GLIBCPP_FORCE_NEW in the
 251       environment, it likely means that you linked against objects
 252       built against the older library.  Code to support this extension
 253       is fully compatible with 3.2 code if GLIBCPP_FORCE_NEW is not in
 254       the environment.
 255    </p>
 256
 257    <p> As it turns out, the 3.4 code base continues to use this
 258    mechanism, only the environment variable has been changed to
 259    GLIBCXX_FORCE_NEW.
 260    </p>
 261
 262 <h3 class="left">
 263   <a name="ext_allocators">Other allocators</a>
 264 </h3>
 265    <p> Several other allocators are provided as part of this
 266    implementation.  The location of the extension allocators and their
 267    names have changed, but in all cases, functionality is
 268    equivalent. Starting with gcc-3.4, all extension allocators are
 269    standard style. Before this point, SGI style was the norm. Because of
 270    this, the number of template arguments also changed. Here's a simple
 271    chart to track the changes.
 272    </p>
 273
 274 <table title="extension allocators" border="1">
 275   <tr>
 276     <th>Allocator (3.4)</th>
 277     <th>Header (3.4)</th>
 278     <th>Allocator (3.[0-3])</th>
 279     <th>Header (3.[0-3])</th>
 280   </tr>
 281   <tr>
 282     <td>__gnu_cxx::new_allocator&lt;T&gt;</td>
 283     <td>&lt;ext/new_allocator.h&gt;</td>
 284     <td>std::__new_alloc</td>
 285     <td>&lt;memory&gt;</td>
 286   </tr>
 287   <tr>
 288     <td>__gnu_cxx::malloc_allocator&lt;T&gt;</td>
 289     <td>&lt;ext/malloc_allocator.h&gt;</td>
 290     <td>std::__malloc_alloc_template&lt;int&gt;</td>
 291     <td>&lt;memory&gt;</td>
 292   </tr>
 293   <tr>
 294     <td>__gnu_cxx::debug_allocator&lt;T&gt;</td>
 295     <td>&lt;ext/debug_allocator.h&gt;</td>
 296     <td>std::debug_alloc&lt;T&gt;</td>
 297     <td>&lt;memory&gt;</td>
 298   </tr>
 299   <tr>
 300     <td>__gnu_cxx::__pool_alloc&lt;bool, int&gt;</td>
 301     <td>&lt;ext/pool_allocator.h&gt;</td>
 302     <td>std::__default_alloc_template&lt;bool,int&gt;</td>
 303     <td>&lt;memory&gt;</td>
 304   </tr>
 305   <tr>
 306     <td>__gnu_cxx::__mt_alloc&lt;T&gt;</td>
 307     <td>&lt;ext/mt_allocator.h&gt;</td>
 308     <td></td>
 309     <td></td>
 310   </tr>
 311 </table>
 312
 313    <p>More details on each of these allocators follows. </p>
 314    <ul>
 315      <li><code>new_allocator</code>
 316      <p>Simply wraps <code>::operator new</code>
 317          and <code>::operator delete</code>.
 318      </p>
 319      </li>
 320      <li><code>malloc_allocator</code>
 321      <p>Simply wraps
 322          <code>malloc</code> and <code>free</code>.  There is also a hook
 323          for an out-of-memory handler (for new/delete this is taken care of
 324          elsewhere).
 325      </p>
 326      </li>
 327      <li><code>debug_allocator</code>
 328      <p> A wrapper around an
 329          arbitrary allocator A.  It passes on slightly increased size
 330          requests to A, and uses the extra memory to store size information.
 331          When a pointer is passed to <code>deallocate()</code>, the stored
 332          size is checked, and assert() is used to guarantee they match.
 333      </p>
 334      </li>
 335      <li><code>__pool_alloc</code>
 336      <p> A high-performance, single pool allocator.  The reusable
 337       memory is shared among identical instantiations of this type.
 338       It calls through <code>::operator new</code> to obtain new memory
 339       when its lists run out.  If a client container requests a block
 340       larger than a certain threshold size, then the pool is bypassed,
 341       and the allocate/deallocate request is passed to
 342       <code>::operator new</code> directly.  </p>
 343
 344    <p> This class take a boolean template parameter, called
 345       <code>thr</code>, and an integer template parameter, called
 346       <code>inst</code>.
 347    </p>
 348    <p>The <code>inst</code> number is used to track additional memory
 349       pools.  The point of the number is to allow multiple
 350       instantiations of the classes without changing the semantics at
 351       all.  All three of
 352    </p>
 353
 354    <pre>
 355     typedef  __pool_alloc&lt;true,0&gt;    normal;
 356     typedef  __pool_alloc&lt;true,1&gt;    private;
 357     typedef  __pool_alloc&lt;true,42&gt;   also_private;</pre>
 358    <p>behave exactly the same way.  However, the memory pool for each type
 359       (and remember that different instantiations result in different types)
 360       remains separate.
 361    </p>
 362    <p>The library uses <strong>0</strong> in all its instantiations.  If you
 363       wish to keep separate free lists for a particular purpose, use a
 364       different number.
 365    </p>
 366    <p>The <code>thr</code> boolean determines whether the pool should
 367       be manipulated atomically or not.  When thr=true, the allocator
 368       is is threadsafe, while thr=false, and is slightly faster but
 369       unsafe for multiple threads.
 370    </p>
 371    <p>(Note that the GCC thread abstraction layer allows us to provide safe
 372       zero-overhead stubs for the threading routines, if threads were
 373       disabled at configuration time.)
 374    </p>
 375
 376      </li>
 377
 378      <li><code>__mt_alloc</code>
 379      <p>A high-performance
 380      fixed-size allocator. It has its own documentation, found <a
 381      href="../ext/mt_allocator.html">here</a>.
 382      </p>
 383      </li>
 384    </ul>
 385
 386
 387 <h3 class="left">
 388   <a name="using_custom_allocators">Using a specific allocator</a>
 389 </h3>
 390    <p>You can specify different memory management schemes on a
 391       per-container basis, by overriding the default
 392       <code>Allocator</code> template parameter.  For example, an easy
 393       (but non-portable) method of specifying that only malloc/free
 394       should be used instead of the default node allocator is:
 395    </p>
 396    <pre>
 397     std::list &lt;int, __gnu_cxx::malloc_allocator&lt;int&gt; &gt;  malloc_list;</pre>
 398       Likewise, a debugging form of whichever allocator is currently in use:
 399       <pre>
 400     std::deque &lt;int, __gnu_cxx::debug_allocator&lt;std::allocator&lt;int&gt; &gt; &gt;  debug_deque;</pre>
 401
 402
 403 <h3 class="left">
 404   <a name="custom_allocators">Writing custom allocators</a>
 405 </h3>
 406    <p> Writing a portable C++ allocator would dictate that the
 407    interface would look much like the one specified for <code>
 408    std::allocator</code>. Additional member functions, but not
 409    subtractions, would be permissible.
 410    </p>
 411
 412    <p> Probably the best place to start would be to copy one of the
 413    extension allocators already shipped with libstdc++: say, <code>
 414    new_allocator </code>.
 415    </p>
 416
 417
 418 <h3 class="left">
 419   <a name="biblio">Bibliography / Further Reading</a>
 420 </h3>
 421    <p>
 422    ISO/IEC 14882:1998 Programming languages - C++ [20.4 Memory]
 423    </p>
 424
 425    <p>
 426    Austern, Matt, C/C++ Users Journal.
 427    <a href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/">The Standard Librarian: What Are Allocators Good
 428    For?</a>
 429    </p>
 430
 431    <p>
 432    Berger, Emery,
 433    <a href="http://www.cs.umass.edu/~emery/hoard/"> The Hoard memory allocator </a>
 434    </p>
 435
 436    <p>
 437    Berger, Emery with Ben Zorn & Kathryn McKinley, OOPSLA 2002
 438    <a href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf">Reconsidering Custom Memory Allocation</a>
 439    </p>
 440
 441    <p>
 442    Kreft, Klaus and Angelika Langer, C++ Report, June 1998
 443    <a href="http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html">Allocator Types</a>
 444    </p>
 445
 446    <p>
 447    Stroustrup, Bjarne, 19.4 Allocators, The C++ Programming
 448    Language, Special Edition, Addison Wesley, Inc. 2000
 449    </p>
 450
 451    <p>
 452    Yen, Felix, <a href="http://home.earthlink.net/~brimar/yalloc/">Yalloc: A Recycling C++ Allocator</a>
 453    </p>
 454
 455 <hr />
 456 <p>Return <a href="#top">to the top of the page</a> or
 457    <a href="http://gcc.gnu.org/libstdc++/">to the libstdc++ homepage</a>.
 458 </p>
 459
 460
 461 <!-- ####################################################### -->
 462
 463 <hr />
 464 <p class="fineprint"><em>
 465 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
 466 Comments and suggestions are welcome, and may be sent to
 467 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
 468 </em></p>
 469
 470
 471 </body>
 472 </html>