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;T&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   <tr>
 312     <td>__gnu_cxx::bitmap_allocator&lt;T&gt;</td>
 313     <td>&lt;ext/bitmap_allocator.h&gt;</td>
 314     <td></td>
 315     <td></td>
 316   </tr>
 317 </table>
 318
 319    <p> Releases after gcc-3.4 have continued to add to the collection
 320    of available allocators. All of these new allocators are
 321    standard-style. The following table includes details, along with
 322    the first released version of GCC that included the extension allocator.
 323    </p>
 324
 325 <table title="more extension allocators" border="1">
 326   <tr>
 327     <th>Allocator</th>
 328     <th>Include</th>
 329     <th>Version</th>
 330   </tr>
 331   <tr>
 332     <td>__gnu_cxx::array_allocator&lt;T&gt;</td>
 333     <td>&lt;ext/array_allocator.h&gt;</td>
 334     <td>4.0.0</td>
 335   </tr>
 336 </table>
 337
 338    <p>More details on each of these extension allocators follows. </p>
 339    <ul>
 340      <li><code>new_allocator</code>
 341      <p>Simply wraps <code>::operator new</code>
 342          and <code>::operator delete</code>.
 343      </p>
 344      </li>
 345      <li><code>malloc_allocator</code>
 346      <p>Simply wraps
 347          <code>malloc</code> and <code>free</code>.  There is also a hook
 348          for an out-of-memory handler (for new/delete this is taken care of
 349          elsewhere).
 350      </p>
 351      </li>
 352      <li><code>array_allocator</code>
 353      <p>Allows allocations of known and fixed sizes using existing
 354          global or external storage allocated via construction of
 355          std::tr1::array objects. By using this allocator, fixed size
 356          containers (including std::string) can be used without
 357          instances calling <code>::operator new</code> and
 358          <code>::operator delete</code>. This capability allows the
 359          use of STL abstractions without runtime complications or
 360          overhead, even in situations such as program startup. For
 361          usage examples, please consult the libstdc++ testsuite.
 362      </p>
 363      </li>
 364      <li><code>debug_allocator</code>
 365      <p> A wrapper around an
 366          arbitrary allocator A.  It passes on slightly increased size
 367          requests to A, and uses the extra memory to store size information.
 368          When a pointer is passed to <code>deallocate()</code>, the stored
 369          size is checked, and assert() is used to guarantee they match.
 370      </p>
 371      </li>
 372      <li><code>__pool_alloc</code>
 373      <p> A high-performance, single pool allocator.  The reusable
 374       memory is shared among identical instantiations of this type.
 375       It calls through <code>::operator new</code> to obtain new memory
 376       when its lists run out.  If a client container requests a block
 377       larger than a certain threshold size, then the pool is bypassed,
 378       and the allocate/deallocate request is passed to
 379       <code>::operator new</code> directly.  </p>
 380
 381    <p> For versions of <code>__pool_alloc</code> after 3.4.0, there is
 382    only one template parameter, as per the standard.
 383    </p>
 384
 385    <p> Older versions of this class take a boolean template parameter,
 386       called <code>thr</code>, and an integer template parameter,
 387       called <code>inst</code>.
 388    </p>
 389
 390    <p>The <code>inst</code> number is used to track additional memory
 391       pools.  The point of the number is to allow multiple
 392       instantiations of the classes without changing the semantics at
 393       all.  All three of
 394    </p>
 395
 396    <pre>
 397     typedef  __pool_alloc&lt;true,0&gt;    normal;
 398     typedef  __pool_alloc&lt;true,1&gt;    private;
 399     typedef  __pool_alloc&lt;true,42&gt;   also_private;</pre>
 400    <p>behave exactly the same way.  However, the memory pool for each type
 401       (and remember that different instantiations result in different types)
 402       remains separate.
 403    </p>
 404    <p>The library uses <strong>0</strong> in all its instantiations.  If you
 405       wish to keep separate free lists for a particular purpose, use a
 406       different number.
 407    </p>
 408    <p>The <code>thr</code> boolean determines whether the pool should
 409       be manipulated atomically or not.  When thr=true, the allocator
 410       is is threadsafe, while thr=false, and is slightly faster but
 411       unsafe for multiple threads.
 412    </p>
 413
 414    <p>For thread-enabled configurations, the pool is locked with a
 415    single big lock. In some situations, this implementation detail may
 416    result in severe performance degredation.
 417    </p>
 418
 419    <p>(Note that the GCC thread abstraction layer allows us to provide safe
 420       zero-overhead stubs for the threading routines, if threads were
 421       disabled at configuration time.)
 422    </p>
 423
 424      </li>
 425
 426      <li><code>__mt_alloc</code>
 427      <p>A high-performance
 428      fixed-size allocator. It has its own documentation, found <a
 429      href="../ext/mt_allocator.html">here</a>.
 430      </p>
 431      </li>
 432
 433      <li><code>bitmap_allocator</code>
 434      <p>A high-performance allocator that uses a bit-map to keep track
 435      of the used and unused memory locations. It has its own
 436      documentation, found <a
 437      href="../ext/ballocator_doc.html">here</a>.
 438      </p>
 439      </li>
 440    </ul>
 441
 442
 443 <h3 class="left">
 444   <a name="using_custom_allocators">Using a specific allocator</a>
 445 </h3>
 446    <p>You can specify different memory management schemes on a
 447       per-container basis, by overriding the default
 448       <code>Allocator</code> template parameter.  For example, an easy
 449       (but non-portable) method of specifying that only malloc/free
 450       should be used instead of the default node allocator is:
 451    </p>
 452    <pre>
 453     std::list &lt;int, __gnu_cxx::malloc_allocator&lt;int&gt; &gt;  malloc_list;</pre>
 454       Likewise, a debugging form of whichever allocator is currently in use:
 455       <pre>
 456     std::deque &lt;int, __gnu_cxx::debug_allocator&lt;std::allocator&lt;int&gt; &gt; &gt;  debug_deque;</pre>
 457
 458
 459 <h3 class="left">
 460   <a name="custom_allocators">Writing custom allocators</a>
 461 </h3>
 462    <p> Writing a portable C++ allocator would dictate that the
 463    interface would look much like the one specified for <code>
 464    std::allocator</code>. Additional member functions, but not
 465    subtractions, would be permissible.
 466    </p>
 467
 468    <p> Probably the best place to start would be to copy one of the
 469    extension allocators already shipped with libstdc++: say, <code>
 470    new_allocator </code>.
 471    </p>
 472
 473
 474 <h3 class="left">
 475   <a name="biblio">Bibliography / Further Reading</a>
 476 </h3>
 477    <p>
 478    ISO/IEC 14882:1998 Programming languages - C++ [20.4 Memory]
 479    </p>
 480
 481    <p>
 482    Austern, Matt, C/C++ Users Journal.
 483    <a href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/">The Standard Librarian: What Are Allocators Good
 484    For?</a>
 485    </p>
 486
 487    <p>
 488    Berger, Emery,
 489    <a href="http://www.cs.umass.edu/~emery/hoard/"> The Hoard memory allocator </a>
 490    </p>
 491
 492    <p>
 493    Berger, Emery with Ben Zorn & Kathryn McKinley, OOPSLA 2002
 494    <a href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf">Reconsidering Custom Memory Allocation</a>
 495    </p>
 496
 497    <p>
 498    Kreft, Klaus and Angelika Langer, C++ Report, June 1998
 499    <a href="http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html">Allocator Types</a>
 500    </p>
 501
 502    <p>
 503    Stroustrup, Bjarne, 19.4 Allocators, The C++ Programming
 504    Language, Special Edition, Addison Wesley, Inc. 2000
 505    </p>
 506
 507    <p>
 508    Yen, Felix, <a href="http://home.earthlink.net/~brimar/yalloc/">Yalloc: A Recycling C++ Allocator</a>
 509    </p>
 510
 511 <hr />
 512 <p>Return <a href="#top">to the top of the page</a> or
 513    <a href="http://gcc.gnu.org/libstdc++/">to the libstdc++ homepage</a>.
 514 </p>
 515
 516
 517 <!-- ####################################################### -->
 518
 519 <hr />
 520 <p class="fineprint"><em>
 521 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
 522 Comments and suggestions are welcome, and may be sent to
 523 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
 524 </em></p>
 525
 526
 527 </body>
 528 </html>