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