OSDN Git Service

2004-03-24 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / 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   <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>More details on each of these allocators follows. </p>
320    <ul>
321      <li><code>new_allocator</code> 
322      <p>Simply wraps <code>::operator new</code>
323          and <code>::operator delete</code>.
324      </p>
325      </li>
326      <li><code>malloc_allocator</code> 
327      <p>Simply wraps
328          <code>malloc</code> and <code>free</code>.  There is also a hook
329          for an out-of-memory handler (for new/delete this is taken care of
330          elsewhere).  
331      </p>
332      </li>
333      <li><code>debug_allocator</code> 
334      <p> A wrapper around an
335          arbitrary allocator A.  It passes on slightly increased size
336          requests to A, and uses the extra memory to store size information.
337          When a pointer is passed to <code>deallocate()</code>, the stored
338          size is checked, and assert() is used to guarantee they match. 
339      </p>
340      </li>
341      <li><code>__pool_alloc</code>
342      <p> A high-performance, single pool allocator.  The reusable
343       memory is shared among identical instantiations of this type.
344       It calls through <code>::operator new</code> to obtain new memory
345       when its lists run out.  If a client container requests a block
346       larger than a certain threshold size, then the pool is bypassed,
347       and the allocate/deallocate request is passed to
348       <code>::operator new</code> directly.  </p>
349
350    <p> This class take a boolean template parameter, called
351       <code>thr</code>, and an integer template parameter, called
352       <code>inst</code>.
353    </p>
354    <p>The <code>inst</code> number is used to track additional memory
355       pools.  The point of the number is to allow multiple
356       instantiations of the classes without changing the semantics at
357       all.  All three of
358    </p>
359
360    <pre>
361     typedef  __pool_alloc&lt;true,0&gt;    normal;
362     typedef  __pool_alloc&lt;true,1&gt;    private;
363     typedef  __pool_alloc&lt;true,42&gt;   also_private;</pre>
364    <p>behave exactly the same way.  However, the memory pool for each type
365       (and remember that different instantiations result in different types)
366       remains separate.
367    </p>
368    <p>The library uses <strong>0</strong> in all its instantiations.  If you
369       wish to keep separate free lists for a particular purpose, use a
370       different number.
371    </p>
372    <p>The <code>thr</code> boolean determines whether the pool should
373       be manipulated atomically or not.  When thr=true, the allocator
374       is is threadsafe, while thr=false, and is slightly faster but
375       unsafe for multiple threads.
376    </p>
377    <p>(Note that the GCC thread abstraction layer allows us to provide safe
378       zero-overhead stubs for the threading routines, if threads were
379       disabled at configuration time.)
380    </p>
381
382      </li>
383
384      <li><code>__mt_alloc</code> 
385      <p>A high-performance
386      fixed-size allocator. It has its own documentation, found <a
387      href="../ext/mt_allocator.html">here</a>.
388      </p>
389      </li>
390
391      <li><code>bitmap_allocator</code> 
392      <p>A high-performance allocator that uses a bit-map to keep track
393      of the used and unused memory locations. It has its own
394      documentation, found <a
395      href="../ext/ballocator_doc.txt">here</a>.
396      </p>
397      </li>
398    </ul>
399
400
401 <h3 class="left">
402   <a name="using_custom_allocators">Using a specific allocator</a>
403 </h3>
404    <p>You can specify different memory management schemes on a
405       per-container basis, by overriding the default
406       <code>Allocator</code> template parameter.  For example, an easy
407       (but non-portable) method of specifying that only malloc/free
408       should be used instead of the default node allocator is:
409    </p>
410    <pre>
411     std::list &lt;int, __gnu_cxx::malloc_allocator&lt;int&gt; &gt;  malloc_list;</pre>
412       Likewise, a debugging form of whichever allocator is currently in use:
413       <pre>
414     std::deque &lt;int, __gnu_cxx::debug_allocator&lt;std::allocator&lt;int&gt; &gt; &gt;  debug_deque;</pre>
415
416
417 <h3 class="left">
418   <a name="custom_allocators">Writing custom allocators</a>
419 </h3>
420    <p> Writing a portable C++ allocator would dictate that the
421    interface would look much like the one specified for <code>
422    std::allocator</code>. Additional member functions, but not
423    subtractions, would be permissible.
424    </p>
425
426    <p> Probably the best place to start would be to copy one of the
427    extension allocators already shipped with libstdc++: say, <code>
428    new_allocator </code>.
429    </p>
430
431
432 <h3 class="left">
433   <a name="biblio">Bibliography / Further Reading</a>
434 </h3>
435    <p>
436    ISO/IEC 14882:1998 Programming languages - C++ [20.4 Memory]
437    </p>
438
439    <p>
440    Austern, Matt, C/C++ Users Journal.
441    <a href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/">The Standard Librarian: What Are Allocators Good
442    For?</a>
443    </p>
444
445    <p>
446    Berger, Emery, 
447    <a href="http://www.cs.umass.edu/~emery/hoard/"> The Hoard memory allocator </a>
448    </p>
449
450    <p>
451    Berger, Emery with Ben Zorn & Kathryn McKinley, OOPSLA 2002
452    <a href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf">Reconsidering Custom Memory Allocation</a>
453    </p>
454
455    <p>
456    Kreft, Klaus and Angelika Langer, C++ Report, June 1998
457    <a href="http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html">Allocator Types</a>
458    </p>
459
460    <p>
461    Stroustrup, Bjarne, 19.4 Allocators, The C++ Programming
462    Language, Special Edition, Addison Wesley, Inc. 2000
463    </p>
464
465    <p>
466    Yen, Felix, <a href="http://home.earthlink.net/~brimar/yalloc/">Yalloc: A Recycling C++ Allocator</a>
467    </p>
468
469 <hr />
470 <p>Return <a href="#top">to the top of the page</a> or
471    <a href="http://gcc.gnu.org/libstdc++/">to the libstdc++ homepage</a>.
472 </p>
473
474
475 <!-- ####################################################### -->
476
477 <hr />
478 <p class="fineprint"><em>
479 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
480 Comments and suggestions are welcome, and may be sent to
481 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
482 </em></p>
483
484
485 </body>
486 </html>