OSDN Git Service

2008-04-10 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / doc / html / manual / bk01pt04ch11.html
1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3 <html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter 11. Memory</title><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    " /><link rel="start" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="utilities.html" title="Part IV. Utilities" /><link rel="prev" href="bk01pt04ch10.html" title="Chapter 10. Pairs" /><link rel="next" href="auto_ptr.html" title="auto_ptr" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 11. Memory</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bk01pt04ch10.html">Prev</a> </td><th width="60%" align="center">Part IV. Utilities</th><td width="20%" align="right"> <a accesskey="n" href="auto_ptr.html">Next</a></td></tr></table><hr /></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="manual.util.memory"></a>Chapter 11. Memory</h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="sect1"><a href="bk01pt04ch11.html#manual.util.memory.allocator">Allocators</a></span></dt><dd><dl><dt><span class="sect2"><a href="bk01pt04ch11.html#allocator.req">Requirements</a></span></dt><dt><span class="sect2"><a href="bk01pt04ch11.html#allocator.design_issues">Design Issues</a></span></dt><dt><span class="sect2"><a href="bk01pt04ch11.html#allocator.impl">Implementation</a></span></dt><dt><span class="sect2"><a href="bk01pt04ch11.html#allocator.using">Using a Specific Allocator</a></span></dt><dt><span class="sect2"><a href="bk01pt04ch11.html#allocator.custom">Custom Allocators</a></span></dt><dt><span class="sect2"><a href="bk01pt04ch11.html#allocator.ext">Extension Allocators</a></span></dt></dl></dd><dt><span class="sect1"><a href="auto_ptr.html">auto_ptr</a></span></dt><dd><dl><dt><span class="sect2"><a href="auto_ptr.html#auto_ptr.limitations">Limitations</a></span></dt><dt><span class="sect2"><a href="auto_ptr.html#auto_ptr.using">Use in Containers</a></span></dt></dl></dd><dt><span class="sect1"><a href="shared_ptr.html">shared_ptr</a></span></dt><dd><dl><dt><span class="sect2"><a href="shared_ptr.html#shared_ptr.req">Requirements</a></span></dt><dt><span class="sect2"><a href="shared_ptr.html#shared_ptr.design_issues">Design Issues</a></span></dt><dt><span class="sect2"><a href="shared_ptr.html#shared_ptr.impl">Implementation</a></span></dt><dt><span class="sect2"><a href="shared_ptr.html#shared_ptr.using">Use</a></span></dt><dt><span class="sect2"><a href="shared_ptr.html#shared_ptr.ack">Acknowledgments</a></span></dt></dl></dd></dl></div><p>
4     Memory contains three general areas. First, function and operator
5     calls via <code class="function">new</code> and <code class="function">delete</code>
6     operator or member function calls.  Second, allocation via
7     <code class="classname">allocator</code>. And finally, smart pointer and
8     intelligent pointer abstractions.
9   </p><div class="sect1" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="manual.util.memory.allocator"></a>Allocators</h2></div></div></div><p>
10  Memory management for Standard Library entities is encapsulated in a
11  class template called <code class="classname">allocator</code>. The
12  <code class="classname">allocator</code> abstraction is used throughout the
13  library in <code class="classname">string</code>, container classes,
14  algorithms, and parts of iostreams. This class, and base classes of
15  it, are the superset of available free store (“<span class="quote">heap</span>”)
16  management classes.
17 </p><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.req"></a>Requirements</h3></div></div></div><p>
18     The C++ standard only gives a few directives in this area:
19   </p><div class="itemizedlist"><ul type="disc"><li><p>
20        When you add elements to a container, and the container must
21        allocate more memory to hold them, the container makes the
22        request via its <span class="type">Allocator</span> template
23        parameter, which is usually aliased to
24        <span class="type">allocator_type</span>.  This includes adding chars
25        to the string class, which acts as a regular STL container in
26        this respect.
27       </p></li><li><p>
28        The default <span class="type">Allocator</span> argument of every
29        container-of-T is <code class="classname">allocator&lt;T&gt;</code>.
30        </p></li><li><p>
31        The interface of the <code class="classname">allocator&lt;T&gt;</code> class is
32          extremely simple.  It has about 20 public declarations (nested
33          typedefs, member functions, etc), but the two which concern us most
34          are:
35        </p><pre class="programlisting">
36          T*    allocate   (size_type n, const void* hint = 0);
37          void  deallocate (T* p, size_type n);
38        </pre><p>
39          The <code class="varname">n</code> arguments in both those
40          functions is a <span class="emphasis"><em>count</em></span> of the number of
41          <span class="type">T</span>'s to allocate space for, <span class="emphasis"><em>not their
42          total size</em></span>.
43          (This is a simplification; the real signatures use nested typedefs.)  
44        </p></li><li><p>
45          The storage is obtained by calling <code class="function">::operator
46          new</code>, but it is unspecified when or how
47          often this function is called.  The use of the 
48          <code class="varname">hint</code> is unspecified, but intended as an
49          aid to locality if an implementation so
50          desires. <code class="constant">[20.4.1.1]/6</code>
51        </p></li></ul></div><p> 
52      Complete details cam be found in the C++ standard, look in
53      <code class="constant">[20.4 Memory]</code>.
54    </p></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.design_issues"></a>Design Issues</h3></div></div></div><p>
55     The easiest way of fulfilling the requirements is to call
56     <code class="function">operator new</code> each time a container needs
57     memory, and to call <code class="function">operator delete</code> each time
58     the container releases memory. This method may be <a class="ulink" href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html" target="_top">slower</a>
59     than caching the allocations and re-using previously-allocated
60     memory, but has the advantage of working correctly across a wide
61     variety of hardware and operating systems, including large
62     clusters. The <code class="classname">__gnu_cxx::new_allocator</code>
63     implements the simple operator new and operator delete semantics,
64     while <code class="classname">__gnu_cxx::malloc_allocator</code>
65     implements much the same thing, only with the C language functions
66     <code class="function">std::malloc</code> and <code class="function">free</code>.
67   </p><p> 
68     Another approach is to use intelligence within the allocator
69     class to cache allocations. This extra machinery can take a variety
70     of forms: a bitmap index, an index into an exponentially increasing
71     power-of-two-sized buckets, or simpler fixed-size pooling cache.
72     The cache is shared among all the containers in the program: when
73     your program's <code class="classname">std::vector&lt;int&gt;</code> gets
74   cut in half and frees a bunch of its storage, that memory can be
75   reused by the private
76   <code class="classname">std::list&lt;WonkyWidget&gt;</code> brought in from
77   a KDE library that you linked against.  And operators
78   <code class="function">new</code> and <code class="function">delete</code> are not
79   always called to pass the memory on, either, which is a speed
80   bonus. Examples of allocators that use these techniques are
81   <code class="classname">__gnu_cxx::bitmap_allocator</code>,
82   <code class="classname">__gnu_cxx::pool_allocator</code>, and
83   <code class="classname">__gnu_cxx::__mt_alloc</code>.
84   </p><p>
85     Depending on the implementation techniques used, the underlying
86     operating system, and compilation environment, scaling caching
87     allocators can be tricky. In particular, order-of-destruction and
88     order-of-creation for memory pools may be difficult to pin down
89     with certainty, which may create problems when used with plugins
90     or loading and unloading shared objects in memory. As such, using
91     caching allocators on systems that do not support
92     <code class="function">abi::__cxa_atexit</code> is not recommended.
93   </p></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.impl"></a>Implementation</h3></div></div></div><div class="sect3" lang="en" xml:lang="en"><div class="titlepage"><div><div><h4 class="title"><a id="id425964"></a>Interface Design</h4></div></div></div><p>
94      The only allocator interface that
95      is support is the standard C++ interface. As such, all STL
96      containers have been adjusted, and all external allocators have
97      been modified to support this change.   
98    </p><p> 
99      The class <code class="classname">allocator</code> just has typedef,
100    constructor, and rebind members. It inherits from one of the
101    high-speed extension allocators, covered below. Thus, all
102    allocation and deallocation depends on the base class.
103    </p><p> 
104      The base class that <code class="classname">allocator</code> is derived from
105      may not be user-configurable.
106 </p></div><div class="sect3" lang="en" xml:lang="en"><div class="titlepage"><div><div><h4 class="title"><a id="id424963"></a>Selecting Default Allocation Policy</h4></div></div></div><p> 
107      It's difficult to pick an allocation strategy that will provide
108    maximum utility, without excessively penalizing some behavior. In
109    fact, it's difficult just deciding which typical actions to measure
110    for speed.
111    </p><p> 
112      Three synthetic benchmarks have been created that provide data
113      that is used to compare different C++ allocators. These tests are:
114    </p><div class="orderedlist"><ol type="1"><li><p>
115        Insertion. 
116        </p><p>
117        Over multiple iterations, various STL container
118      objects have elements inserted to some maximum amount. A variety
119      of allocators are tested.  
120      Test source for <a class="ulink" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/sequence.cc?view=markup" target="_top">sequence</a>
121      and <a class="ulink" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert/associative.cc?view=markup" target="_top">associative</a>
122      containers.
123        </p></li><li><p>
124        Insertion and erasure in a multi-threaded environment.
125        </p><p>
126        This test shows the ability of the allocator to reclaim memory
127      on a pre-thread basis, as well as measuring thread contention
128      for memory resources. 
129      Test source 
130     <a class="ulink" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/insert_erase/associative.cc?view=markup" target="_top">here</a>.
131        </p></li><li><p>
132          A threaded producer/consumer model.
133        </p><p>
134        Test source for
135      <a class="ulink" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/producer_consumer/sequence.cc?view=markup" target="_top">sequence</a>
136      and 
137      <a class="ulink" href="http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/testsuite/performance/23_containers/producer_consumer/associative.cc?view=markup" target="_top">associative</a>
138      containers.
139      </p></li></ol></div><p>
140      The current default choice for
141      <code class="classname">allocator</code> is
142      <code class="classname">__gnu_cxx::new_allocator</code>.
143    </p></div><div class="sect3" lang="en" xml:lang="en"><div class="titlepage"><div><div><h4 class="title"><a id="id458581"></a>Disabling Memory Caching</h4></div></div></div><p> 
144       In use, <code class="classname">allocator</code> may allocate and
145       deallocate using implementation-specified strategies and
146       heuristics. Because of this, every call to an allocator object's
147       <code class="function">allocate</code> member function may not actually
148       call the global operator new. This situation is also duplicated
149       for calls to the <code class="function">deallocate</code> member
150       function.
151     </p><p> 
152      This can be confusing. 
153    </p><p> 
154      In particular, this can make debugging memory errors more
155      difficult, especially when using third party tools like valgrind or
156      debug versions of <code class="function">new</code>.
157    </p><p> 
158      There are various ways to solve this problem. One would be to use
159      a custom allocator that just called operators
160      <code class="function">new</code> and <code class="function">delete</code>
161      directly, for every allocation. (See
162      <code class="filename">include/ext/new_allocator.h</code>, for instance.)
163      However, that option would involve changing source code to use
164      a non-default allocator. Another option is to force the
165      default allocator to remove caching and pools, and to directly
166      allocate with every call of <code class="function">allocate</code> and
167      directly deallocate with every call of
168      <code class="function">deallocate</code>, regardless of efficiency. As it
169      turns out, this last option is also available.
170    </p><p>
171      To globally disable memory caching within the library for the
172      default allocator, merely set
173      <code class="constant">GLIBCXX_FORCE_NEW</code> (with any value) in the
174      system's environment before running the program. If your program
175      crashes with <code class="constant">GLIBCXX_FORCE_NEW</code> in the
176      environment, it likely means that you linked against objects
177      built against the older library (objects which might still using the
178      cached allocations...).
179   </p></div></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.using"></a>Using a Specific Allocator</h3></div></div></div><p>
180      You can specify different memory management schemes on a
181      per-container basis, by overriding the default
182      <span class="type">Allocator</span> template parameter.  For example, an easy
183       (but non-portable) method of specifying that only <code class="function">malloc</code> or <code class="function">free</code>
184       should be used instead of the default node allocator is:
185    </p><pre class="programlisting">
186     std::list &lt;int, __gnu_cxx::malloc_allocator&lt;int&gt; &gt;  malloc_list;</pre><p>
187       Likewise, a debugging form of whichever allocator is currently in use:
188     </p><pre class="programlisting">
189     std::deque &lt;int, __gnu_cxx::debug_allocator&lt;std::allocator&lt;int&gt; &gt; &gt;  debug_deque;
190       </pre></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.custom"></a>Custom Allocators</h3></div></div></div><p> 
191     Writing a portable C++ allocator would dictate that the interface
192     would look much like the one specified for
193     <code class="classname">allocator</code>. Additional member functions, but
194     not subtractions, would be permissible.
195   </p><p> 
196      Probably the best place to start would be to copy one of the
197    extension allocators: say a simple one like 
198    <code class="classname">new_allocator</code>.
199    </p></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.ext"></a>Extension Allocators</h3></div></div></div><p> 
200     Several other allocators are provided as part of this
201     implementation.  The location of the extension allocators and their
202     names have changed, but in all cases, functionality is
203     equivalent. Starting with gcc-3.4, all extension allocators are
204     standard style. Before this point, SGI style was the norm. Because of
205     this, the number of template arguments also changed. Here's a simple
206     chart to track the changes.
207   </p><p>
208     More details on each of these extension allocators follows.
209   </p><div class="orderedlist"><ol type="1"><li><p>
210        <code class="classname">new_allocator</code>
211        </p><p>
212          Simply wraps <code class="function">::operator new</code>
213          and <code class="function">::operator delete</code>.
214        </p></li><li><p>
215        <code class="classname">malloc_allocator</code>
216        </p><p>
217          Simply wraps <code class="function">malloc</code> and
218          <code class="function">free</code>. There is also a hook for an
219          out-of-memory handler (for
220          <code class="function">new</code>/<code class="function">delete</code> this is
221          taken care of elsewhere).
222        </p></li><li><p>
223        <code class="classname">array_allocator</code>
224        </p><p>
225          Allows allocations of known and fixed sizes using existing
226          global or external storage allocated via construction of
227          <code class="classname">std::tr1::array</code> objects. By using this
228          allocator, fixed size containers (including
229          <code class="classname">std::string</code>) can be used without
230          instances calling <code class="function">::operator new</code> and
231          <code class="function">::operator delete</code>. This capability
232          allows the use of STL abstractions without runtime
233          complications or overhead, even in situations such as program
234          startup. For usage examples, please consult the testsuite.
235        </p></li><li><p>
236        <code class="classname">debug_allocator</code>
237        </p><p> 
238          A wrapper around an arbitrary allocator A.  It passes on
239          slightly increased size requests to A, and uses the extra
240          memory to store size information.  When a pointer is passed
241          to <code class="function">deallocate()</code>, the stored size is
242          checked, and <code class="function">assert()</code> is used to
243          guarantee they match.
244        </p></li><li><p>
245         <code class="classname">throw_allocator</code>
246         </p><p> 
247           Includes memory tracking and marking abilities as well as hooks for
248           throwing exceptions at configurable intervals (including random,
249           all, none). 
250         </p></li><li><p>
251        <code class="classname">__pool_alloc</code>
252        </p><p> 
253          A high-performance, single pool allocator.  The reusable
254          memory is shared among identical instantiations of this type.
255          It calls through <code class="function">::operator new</code> to
256          obtain new memory when its lists run out.  If a client
257          container requests a block larger than a certain threshold
258          size, then the pool is bypassed, and the allocate/deallocate
259          request is passed to <code class="function">::operator new</code>
260          directly.
261        </p><p> 
262          Older versions of this class take a boolean template
263          parameter, called <code class="varname">thr</code>, and an integer template
264          parameter, called <code class="varname">inst</code>.
265        </p><p>
266          The <code class="varname">inst</code> number is used to track additional memory
267       pools.  The point of the number is to allow multiple
268       instantiations of the classes without changing the semantics at
269       all.  All three of
270        </p><pre class="programlisting">
271     typedef  __pool_alloc&lt;true,0&gt;    normal;
272     typedef  __pool_alloc&lt;true,1&gt;    private;
273     typedef  __pool_alloc&lt;true,42&gt;   also_private;
274    </pre><p>
275      behave exactly the same way.  However, the memory pool for each type
276       (and remember that different instantiations result in different types)
277       remains separate.
278    </p><p>
279      The library uses <span class="emphasis"><em>0</em></span> in all its instantiations.  If you
280       wish to keep separate free lists for a particular purpose, use a
281       different number.
282    </p><p>The <code class="varname">thr</code> boolean determines whether the
283    pool should be manipulated atomically or not.  When
284    <code class="varname">thr</code> = <code class="constant">true</code>, the allocator
285    is is thread-safe, while <code class="varname">thr</code> =
286    <code class="constant">false</code>, and is slightly faster but unsafe for
287    multiple threads.
288    </p><p>
289      For thread-enabled configurations, the pool is locked with a
290      single big lock. In some situations, this implementation detail
291      may result in severe performance degradation.
292    </p><p>
293      (Note that the GCC thread abstraction layer allows us to provide
294      safe zero-overhead stubs for the threading routines, if threads
295      were disabled at configuration time.)
296    </p></li><li><p>
297        <code class="classname">__mt_alloc</code>
298        </p><p>
299          A high-performance fixed-size allocator with
300          exponentially-increasing allocations. It has its own
301          documentation, found <a class="ulink" href="../ext/mt_allocator.html" target="_top">here</a>.
302        </p></li><li><p>
303        <code class="classname">bitmap_allocator</code>
304        </p><p>
305          A high-performance allocator that uses a bit-map to keep track
306          of the used and unused memory locations. It has its own
307          documentation, found <a class="ulink" href="../ext/ballocator_doc.html" target="_top">here</a>.
308        </p></li></ol></div></div><div class="bibliography"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.biblio"></a>Bibliography</h3></div></div></div><div class="biblioentry"><a id="id457599"></a><p><span class="title"><i>
309     ISO/IEC 14882:1998 Programming languages - C++  
310     </i>. </span>
311       isoc++_1998
312     <span class="pagenums">20.4 Memory. </span></p></div><div class="biblioentry"><a id="id457613"></a><p><span class="title"><i>The Standard Librarian: What Are Allocators Good
313     </i>. </span>
314       austernm
315     <span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername">
316         C/C++ Users Journal     
317       . </span></span><span class="biblioid">
318       <a class="ulink" href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/" target="_top">
319       </a>
320     . </span></p></div><div class="biblioentry"><a id="id458630"></a><p><span class="title"><i>The Hoard Memory Allocator</i>. </span>
321       emeryb
322     <span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span><span class="biblioid">
323       <a class="ulink" href="http://www.cs.umass.edu/~emery/hoard/" target="_top">
324       </a>
325     . </span></p></div><div class="biblioentry"><a id="id459380"></a><p><span class="title"><i>Reconsidering Custom Memory Allocation</i>. </span>
326       bergerzorn
327     <span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span><span class="author"><span class="firstname">Ben</span> <span class="surname">Zorn</span>. </span><span class="author"><span class="firstname">Kathryn</span> <span class="surname">McKinley</span>. </span><span class="copyright">Copyright © 2002 OOPSLA. </span><span class="biblioid">
328       <a class="ulink" href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf" target="_top">
329       </a>
330     . </span></p></div><div class="biblioentry"><a id="id470488"></a><p><span class="title"><i>Allocator Types</i>. </span>
331       kreftlanger
332     <span class="author"><span class="firstname">Klaus</span> <span class="surname">Kreft</span>. </span><span class="author"><span class="firstname">Angelika</span> <span class="surname">Langer</span>. </span><span class="publisher"><span class="publishername">
333         C/C++ Users Journal     
334       . </span></span><span class="biblioid">
335       <a class="ulink" href="http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html" target="_top">
336       </a>
337     . </span></p></div><div class="biblioentry"><a id="id454967"></a><p><span class="title"><i>The C++ Programming Language</i>. </span>
338       tcpl
339     <span class="author"><span class="firstname">Bjarne</span> <span class="surname">Stroustrup</span>. </span><span class="copyright">Copyright © 2000 . </span><span class="pagenums">19.4 Allocators. </span><span class="publisher"><span class="publishername">
340         Addison Wesley
341       . </span></span></p></div><div class="biblioentry"><a id="id453321"></a><p><span class="title"><i>Yalloc: A Recycling C++ Allocator</i>. </span>
342       yenf
343     <span class="author"><span class="firstname">Felix</span> <span class="surname">Yen</span>. </span><span class="copyright">Copyright ©  . </span><span class="biblioid">
344       <a class="ulink" href="http://home.earthlink.net/~brimar/yalloc/" target="_top">
345       </a>
346     . </span></p></div></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt04ch10.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="utilities.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="auto_ptr.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 10. Pairs </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> auto_ptr</td></tr></table></div></body></html>