libstdc++-v3/doc/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++ 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>. This class, and
  39    base classes of it, are the superset of available free store
  40    (&quot;heap&quot;) management classes.
  41 </p>
  42
  43 <h3 class="left">
  44   <a name="standard_requirements">Standard requirements</a>
  45 </h3>
  46    <p>The C++ standard only gives a few directives in this area:
  47    </p>
  48    <ul>
  49      <li>When you add elements to a container, and the container must allocate
  50          more memory to hold them, the container makes the request via its
  51          <code>Allocator</code> template parameter.  This includes adding
  52          chars to the string class, which acts as a regular STL container
  53          in this respect.
  54      </li>
  55      <li>The default <code>Allocator</code> of every container-of-T is
  56          <code>std::allocator&lt;T&gt;</code>.
  57      </li>
  58      <li>The interface of the <code>allocator&lt;T&gt;</code> class is
  59          extremely simple.  It has about 20 public declarations (nested
  60          typedefs, member functions, etc), but the two which concern us most
  61          are:
  62          <pre>
  63       T*    allocate   (size_type n, const void* hint = 0);
  64       void  deallocate (T* p, size_type n);</pre>
  65          (This is a simplification; the real signatures use nested typedefs.)
  66          The <code>&quot;n&quot;</code> arguments in both those functions is a
  67          <em>count</em> of the number of T's to allocate space for,
  68          <em>not their total size</em>.
  69      </li>
  70      <li>&quot;The storage is obtained by calling
  71          <code>::operator new(size_t)</code>, but it is unspecified when or
  72          how often this function is called.  The use of <code>hint</code>
  73          is unspecified, but intended as an aid to locality if an
  74          implementation so desires.&quot; [20.4.1.1]/6
  75       </li>
  76    </ul>
  77
  78    <p> Complete details cam be found in the C++ standard, look in
  79    [20.4 Memory].
  80    </p>
  81
  82 <h3 class="left">
  83   <a name="probs_possibilities">Problems and Possibilities</a>
  84 </h3>
  85    <p>The easiest way of fulfilling the requirements is to call operator new
  86       each time a container needs memory, and to call operator delete each
  87       time the container releases memory. This method may be
  88       <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html">slower</a>
  89       than caching the allocations and re-using previously-allocated
  90       memory, but has the advantage of working correctly across a wide
  91       variety of hardware and operating systems, including large
  92       clusters. The <code>__gnu_cxx::new_allocator</code> implements
  93       the simple operator new and operator delete semantics, while <code>__gnu_cxx::malloc_allocator</code> implements much the same thing, only with the C language functions <code>std::malloc</code> and <code>std::free</code>.
  94    </p>
  95
  96 <p> Another approach is to use intelligence within the allocator class
  97 to cache allocations. This extra machinery can take a variety of
  98 forms: a bitmap index, an index into an exponentially increasing
  99 power-of-two-sized buckets, or simpler fixed-size pooling cache.  The
 100 cache is shared among all the containers in the program: when your
 101 program's std::vector&lt;int&gt; gets cut in half and frees a bunch of
 102 its storage, that memory can be reused by the private
 103 std::list&lt;WonkyWidget&gt; brought in from a KDE library that you
 104 linked against.  And operators new and delete are not always called to
 105 pass the memory on, either, which is a speed bonus. Examples of
 106 allocators that use these techniques
 107 are <code>__gnu_cxx::bitmap_allocator</code>, <code>__gnu_cxx::pool_allocator</code>,
 108 and <code>__gnu_cxx::__mt_alloc</code>.
 109 </p>
 110
 111 <p>Depending on the implementation techniques used, the underlying
 112 operating system, and compilation environment, scaling caching
 113 allocators can be tricky. In particular, order-of-destruction and
 114 order-of-creation for memory pools may be difficult to pin down with
 115 certainty, which may create problems when used with plugins or loading
 116 and unloading shared objects in memory. As such, using caching
 117 allocators on systems that do not
 118 support <code>abi::__cxa_atexit</code> is not recommended.
 119 </p>
 120
 121    <p>Versions of libstdc++ prior to 3.4 cache allocations in a memory
 122    pool, instead of passing through to call the global allocation
 123    operators (ie, <code>__gnu_cxx::pool_allocator</code>).  More
 124    recent versions default to the
 125    simpler <code>__gnu_cxx::new_allocator</code>.
 126    </p>
 127
 128 <h3 class="left">
 129   <a name="stdallocator">Implementation details of <code>std::allocator</code></a>
 130 </h3>
 131    <p> The implementation of <code> std::allocator</code> has continued
 132       to evolve through successive releases. Here's a brief history.
 133    </p>
 134
 135 <h5 class="left">
 136   <a name="30allocator"> 3.0, 3.1, 3.2, 3.3 </a>
 137 </h5>
 138    <p> During this period, all allocators were written to the SGI
 139    style, and all STL containers expected this interface. This
 140    interface had a traits class called <code>_Alloc_traits</code> that
 141    attempted to provide more information for compile-time allocation
 142    selection and optimization. This traits class had another allocator
 143    wrapper, <code>__simple_alloc&lt;T,A&gt;</code>, which was a
 144    wrapper around another allocator, A, which itself is an allocator
 145    for instances of T. But wait, there's more:
 146    <code>__allocator&lt;T,A&gt;</code> is another adapter.  Many of
 147    the provided allocator classes were SGI style: such classes can be
 148    changed to a conforming interface with this wrapper:
 149    <code>__allocator&lt;T, __alloc&gt;</code> is thus the same as
 150    <code>allocator&lt;T&gt;</code>.
 151    </p>
 152
 153    <p> The class <code>std::allocator</code> use the typedef
 154    <code>__alloc</code> to select an underlying allocator that
 155    satisfied memory allocation requests. The selection of this
 156    underlying allocator was not user-configurable.
 157    </p>
 158
 159 <h5 class="left">
 160   <a name="34allocator"> 3.4 </a>
 161 </h5>
 162    <p> For this and later releases, the only allocator interface that
 163    is support is the standard C++ interface. As such, all STL
 164    containers have been adjusted, and all external allocators have
 165    been modified to support this change. Because of this,
 166    <code>__simple_alloc, __allocator, __alloc, </code> and <code>
 167    _Alloc_traits</code> have all been removed.
 168    </p>
 169
 170    <p> The class <code>std::allocator</code> just has typedef,
 171    constructor, and rebind members. It inherits from one of the
 172    high-speed extension allocators, covered below. Thus, all
 173    allocation and deallocation depends on the base class.
 174    </p>
 175
 176   <p> The base class that <code>std::allocator</code> is derived from
 177   is not user-configurable.
 178   </p>
 179
 180 <h5 class="left">
 181   <a name="benchmarks"> How the default allocation strategy is selected.</a>
 182 </h5>
 183    <p> It's difficult to pick an allocation strategy that will provide
 184    maximum utility, without excessively penalizing some behavior. In
 185    fact, it's difficult just deciding which typical actions to measure
 186    for speed.
 187    </p>
 188
 189    <p> Three synthetic benchmarks have been created that provide data
 190    that is used to compare different C++ allocators. These tests are:
 191    </p>
 192
 193    <ul>
 194      <li>Insertion. Over multiple iterations, various STL container
 195      objects have elements inserted to some maximum amount. A variety
 196      of allocators are tested.
 197      Test source for <a
 198      href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/sequence.cc?view=markup">sequence</a>
 199      and <a
 200      href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/associative.cc?view=markup">associative</a>
 201      containers.
 202      </li>
 203
 204      <li>Insertion and erasure in a multi-threaded environment.
 205      This test shows the ability of the allocator to reclaim memory
 206      on a pre-thread basis, as well as measuring thread contention
 207      for memory resources.
 208      Test source
 209     <a href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert_erase/associative.cc?view=markup">here</a>.
 210      </li>
 211
 212      <li>A threaded producer/consumer model.
 213      Test source for
 214      <a href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/producer_consumer/sequence.cc?view=markup">sequence</a>
 215      and
 216      <a href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/producer_consumer/associative.cc?view=markup">associative</a>
 217      containers.
 218      </li>
 219    </ul>
 220
 221 <h5 class="left">
 222   <a name="forcenew"> Disabling memory caching.</a>
 223 </h5>
 224    <p> In use, <code>std::allocator</code> may allocate and deallocate
 225    using implementation-specified strategies and heuristics. Because of
 226    this, every call to an allocator object's <code> allocate</code>
 227    member function may not actually call the global operator new. This
 228    situation is also duplicated for calls to the <code>
 229    deallocate</code> member function.
 230    </p>
 231
 232    <p> This can be confusing.
 233    </p>
 234
 235    <p> In particular, this can make debugging memory errors more
 236    difficult, especially when using third party tools like valgrind or
 237    debug versions of <code> new</code>.
 238    </p>
 239
 240    <p> There are various ways to solve this problem. One would be to
 241    use a custom allocator that just called operators <code> new
 242    </code> and <code> delete</code> directly, for every
 243    allocation. (See include/ext/new_allocator.h, for instance.)
 244    However, that option would involve changing source code to use the a
 245    non-default allocator. Another option is to force the default
 246    allocator to remove caching and pools, and to directly allocate
 247    with every call of <code> allocate</code> and directly deallocate
 248    with every call of <code> deallocate</code>, regardless of
 249    efficiency. As it turns out, this last option is available,
 250    although the exact mechanism has evolved with time.
 251    </p>
 252
 253    <p> For GCC releases from 2.95 through the 3.1 series, defining
 254    <code>__USE_MALLOC</code> on the gcc command line would change the
 255    default allocation strategy to instead use <code> malloc</code> and
 256    <code> free</code>. See
 257    <a href="../23_containers/howto.html#3">this note</a>
 258    for details as to why this was something needing improvement.
 259    </p>
 260
 261    <p>Starting with GCC 3.2, and continued in the 3.3 series, to
 262       globally disable memory caching within the library for the
 263       default allocator, merely set GLIBCPP_FORCE_NEW (at this time,
 264       with any value) in the system's environment before running the
 265       program. If your program crashes with GLIBCPP_FORCE_NEW in the
 266       environment, it likely means that you linked against objects
 267       built against the older library.  Code to support this extension
 268       is fully compatible with 3.2 code if GLIBCPP_FORCE_NEW is not in
 269       the environment.
 270    </p>
 271
 272    <p> As it turns out, the 3.4 code base continues to use this
 273    mechanism, only the environment variable has been changed to
 274    GLIBCXX_FORCE_NEW.
 275    </p>
 276
 277 <h3 class="left">
 278   <a name="ext_allocators">Other allocators</a>
 279 </h3>
 280    <p> Several other allocators are provided as part of this
 281    implementation.  The location of the extension allocators and their
 282    names have changed, but in all cases, functionality is
 283    equivalent. Starting with gcc-3.4, all extension allocators are
 284    standard style. Before this point, SGI style was the norm. Because of
 285    this, the number of template arguments also changed. Here's a simple
 286    chart to track the changes.
 287    </p>
 288
 289 <table title="extension allocators" border="1">
 290   <tr>
 291     <th>Allocator (3.4)</th>
 292     <th>Header (3.4)</th>
 293     <th>Allocator (3.[0-3])</th>
 294     <th>Header (3.[0-3])</th>
 295   </tr>
 296   <tr>
 297     <td>__gnu_cxx::new_allocator&lt;T&gt;</td>
 298     <td>&lt;ext/new_allocator.h&gt;</td>
 299     <td>std::__new_alloc</td>
 300     <td>&lt;memory&gt;</td>
 301   </tr>
 302   <tr>
 303     <td>__gnu_cxx::malloc_allocator&lt;T&gt;</td>
 304     <td>&lt;ext/malloc_allocator.h&gt;</td>
 305     <td>std::__malloc_alloc_template&lt;int&gt;</td>
 306     <td>&lt;memory&gt;</td>
 307   </tr>
 308   <tr>
 309     <td>__gnu_cxx::debug_allocator&lt;T&gt;</td>
 310     <td>&lt;ext/debug_allocator.h&gt;</td>
 311     <td>std::debug_alloc&lt;T&gt;</td>
 312     <td>&lt;memory&gt;</td>
 313   </tr>
 314   <tr>
 315     <td>__gnu_cxx::__pool_alloc&lt;T&gt;</td>
 316     <td>&lt;ext/pool_allocator.h&gt;</td>
 317     <td>std::__default_alloc_template&lt;bool,int&gt;</td>
 318     <td>&lt;memory&gt;</td>
 319   </tr>
 320   <tr>
 321     <td>__gnu_cxx::__mt_alloc&lt;T&gt;</td>
 322     <td>&lt;ext/mt_allocator.h&gt;</td>
 323     <td></td>
 324     <td></td>
 325   </tr>
 326   <tr>
 327     <td>__gnu_cxx::bitmap_allocator&lt;T&gt;</td>
 328     <td>&lt;ext/bitmap_allocator.h&gt;</td>
 329     <td></td>
 330     <td></td>
 331   </tr>
 332 </table>
 333
 334    <p> Releases after gcc-3.4 have continued to add to the collection
 335    of available allocators. All of these new allocators are
 336    standard-style. The following table includes details, along with
 337    the first released version of GCC that included the extension allocator.
 338    </p>
 339
 340 <table title="more extension allocators" border="1">
 341   <tr>
 342     <th>Allocator</th>
 343     <th>Include</th>
 344     <th>Version</th>
 345   </tr>
 346   <tr>
 347     <td>__gnu_cxx::array_allocator&lt;T&gt;</td>
 348     <td>&lt;ext/array_allocator.h&gt;</td>
 349     <td>4.0.0</td>
 350   </tr>
 351   <tr>
 352     <td>__gnu_cxx::throw_allocator&lt;T&gt;</td>
 353     <td>&lt;ext/throw_allocator.h&gt;</td>
 354     <td>4.2.0</td>
 355   </tr>
 356 </table>
 357
 358    <p>More details on each of these extension allocators follows. </p>
 359    <ul>
 360      <li><code>new_allocator</code>
 361      <p>Simply wraps <code>::operator new</code>
 362          and <code>::operator delete</code>.
 363      </p>
 364      </li>
 365      <li><code>malloc_allocator</code>
 366      <p>Simply wraps
 367          <code>malloc</code> and <code>free</code>.  There is also a hook
 368          for an out-of-memory handler (for new/delete this is taken care of
 369          elsewhere).
 370      </p>
 371      </li>
 372      <li><code>array_allocator</code>
 373      <p>Allows allocations of known and fixed sizes using existing
 374          global or external storage allocated via construction of
 375          std::tr1::array objects. By using this allocator, fixed size
 376          containers (including std::string) can be used without
 377          instances calling <code>::operator new</code> and
 378          <code>::operator delete</code>. This capability allows the
 379          use of STL abstractions without runtime complications or
 380          overhead, even in situations such as program startup. For
 381          usage examples, please consult the libstdc++ testsuite.
 382      </p>
 383      </li>
 384      <li><code>debug_allocator</code>
 385      <p> A wrapper around an
 386          arbitrary allocator A.  It passes on slightly increased size
 387          requests to A, and uses the extra memory to store size information.
 388          When a pointer is passed to <code>deallocate()</code>, the stored
 389          size is checked, and assert() is used to guarantee they match.
 390      </p>
 391      </li>
 392       <li><code>throw_allocator</code>
 393      <p> Includes memory tracking and marking abilities as well as hooks for
 394      throwing exceptinos at configurable intervals (including random,
 395      all, none).
 396      </p>
 397      </li>
 398      <li><code>__pool_alloc</code>
 399      <p> A high-performance, single pool allocator.  The reusable
 400       memory is shared among identical instantiations of this type.
 401       It calls through <code>::operator new</code> to obtain new memory
 402       when its lists run out.  If a client container requests a block
 403       larger than a certain threshold size, then the pool is bypassed,
 404       and the allocate/deallocate request is passed to
 405       <code>::operator new</code> directly.  </p>
 406
 407    <p> For versions of <code>__pool_alloc</code> after 3.4.0, there is
 408    only one template parameter, as per the standard.
 409    </p>
 410
 411    <p> Older versions of this class take a boolean template parameter,
 412       called <code>thr</code>, and an integer template parameter,
 413       called <code>inst</code>.
 414    </p>
 415
 416    <p>The <code>inst</code> number is used to track additional memory
 417       pools.  The point of the number is to allow multiple
 418       instantiations of the classes without changing the semantics at
 419       all.  All three of
 420    </p>
 421
 422    <pre>
 423     typedef  __pool_alloc&lt;true,0&gt;    normal;
 424     typedef  __pool_alloc&lt;true,1&gt;    private;
 425     typedef  __pool_alloc&lt;true,42&gt;   also_private;</pre>
 426    <p>behave exactly the same way.  However, the memory pool for each type
 427       (and remember that different instantiations result in different types)
 428       remains separate.
 429    </p>
 430    <p>The library uses <strong>0</strong> in all its instantiations.  If you
 431       wish to keep separate free lists for a particular purpose, use a
 432       different number.
 433    </p>
 434    <p>The <code>thr</code> boolean determines whether the pool should
 435       be manipulated atomically or not.  When thr=true, the allocator
 436       is is threadsafe, while thr=false, and is slightly faster but
 437       unsafe for multiple threads.
 438    </p>
 439
 440    <p>For thread-enabled configurations, the pool is locked with a
 441    single big lock. In some situations, this implementation detail may
 442    result in severe performance degredation.
 443    </p>
 444
 445    <p>(Note that the GCC thread abstraction layer allows us to provide safe
 446       zero-overhead stubs for the threading routines, if threads were
 447       disabled at configuration time.)
 448    </p>
 449
 450      </li>
 451
 452      <li><code>__mt_alloc</code>
 453      <p>A high-performance
 454      fixed-size allocator. It has its own documentation, found <a
 455      href="../ext/mt_allocator.html">here</a>.
 456      </p>
 457      </li>
 458
 459      <li><code>bitmap_allocator</code>
 460      <p>A high-performance allocator that uses a bit-map to keep track
 461      of the used and unused memory locations. It has its own
 462      documentation, found <a
 463      href="../ext/ballocator_doc.html">here</a>.
 464      </p>
 465      </li>
 466    </ul>
 467
 468
 469 <h3 class="left">
 470   <a name="using_custom_allocators">Using a specific allocator</a>
 471 </h3>
 472    <p>You can specify different memory management schemes on a
 473       per-container basis, by overriding the default
 474       <code>Allocator</code> template parameter.  For example, an easy
 475       (but non-portable) method of specifying that only malloc/free
 476       should be used instead of the default node allocator is:
 477    </p>
 478    <pre>
 479     std::list &lt;int, __gnu_cxx::malloc_allocator&lt;int&gt; &gt;  malloc_list;</pre>
 480       Likewise, a debugging form of whichever allocator is currently in use:
 481       <pre>
 482     std::deque &lt;int, __gnu_cxx::debug_allocator&lt;std::allocator&lt;int&gt; &gt; &gt;  debug_deque;</pre>
 483
 484
 485 <h3 class="left">
 486   <a name="custom_allocators">Writing custom allocators</a>
 487 </h3>
 488    <p> Writing a portable C++ allocator would dictate that the
 489    interface would look much like the one specified for <code>
 490    std::allocator</code>. Additional member functions, but not
 491    subtractions, would be permissible.
 492    </p>
 493
 494    <p> Probably the best place to start would be to copy one of the
 495    extension allocators already shipped with libstdc++: say, <code>
 496    new_allocator </code>.
 497    </p>
 498
 499
 500 <h3 class="left">
 501   <a name="biblio">Bibliography / Further Reading</a>
 502 </h3>
 503    <p>
 504    ISO/IEC 14882:1998 Programming languages - C++ [20.4 Memory]
 505    </p>
 506
 507    <p>
 508    Austern, Matt, C/C++ Users Journal.
 509    <a href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/">The Standard Librarian: What Are Allocators Good
 510    For?</a>
 511    </p>
 512
 513    <p>
 514    Berger, Emery,
 515    <a href="http://www.cs.umass.edu/~emery/hoard/"> The Hoard memory allocator </a>
 516    </p>
 517
 518    <p>
 519    Berger, Emery with Ben Zorn &amp; Kathryn McKinley, OOPSLA 2002
 520    <a href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf">Reconsidering Custom Memory Allocation</a>
 521    </p>
 522
 523    <p>
 524    Kreft, Klaus and Angelika Langer, C++ Report, June 1998
 525    <a href="http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html">Allocator Types</a>
 526    </p>
 527
 528    <p>
 529    Stroustrup, Bjarne, 19.4 Allocators, The C++ Programming
 530    Language, Special Edition, Addison Wesley, Inc. 2000
 531    </p>
 532
 533    <p>
 534    Yen, Felix, <a href="http://home.earthlink.net/~brimar/yalloc/">Yalloc: A Recycling C++ Allocator</a>
 535    </p>
 536
 537 <hr />
 538 <p>Return <a href="#top">to the top of the page</a> or
 539    <a href="http://gcc.gnu.org/libstdc++/">to the libstdc++ homepage</a>.
 540 </p>
 541
 542
 543 <!-- ####################################################### -->
 544
 545 <hr />
 546 <p class="fineprint"><em>
 547 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
 548 Comments and suggestions are welcome, and may be sent to
 549 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
 550 </em></p>
 551
 552
 553 </body>
 554 </html>