OSDN Git Service

07e8e2dd909c8bd771dead039c4f60b4e18bdab1
[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 </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>