memory.html revision 1.1
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.�� 4 Utilities 5 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>) 19 management classes. 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 29 this respect. 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 37 are: 38 </p><pre class="programlisting"> 39 T* allocate (size_type n, const void* hint = 0); 40 void deallocate (T* p, size_type n); 41 </pre><p> 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>. 70 </p><p> 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 78 reused by the private 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>. 87 </p><p> 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. 101 </p><p> 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. 106 </p><p> 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 113 for speed. 114 </p><p> 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> 118 Insertion. 119 </p><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> 125 containers. 126 </p></li><li class="listitem"><p> 127 Insertion and erasure in a multi-threaded environment. 128 </p><p> 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. 132 Test source 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. 136 </p><p> 137 Test source for 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> 139 and 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> 141 containers. 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 153 function. 154 </p><p> 155 This can be confusing. 156 </p><p> 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>. 160 </p><p> 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. 173 </p><p> 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. 198 </p><p> 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. 210 </p><p> 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> 214 </p><p> 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> 219 </p><p> 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> 227 </p><p> 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> 240 </p><p> 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> 249 </p><p> 250 Includes memory tracking and marking abilities as well as hooks for 251 throwing exceptions at configurable intervals (including random, 252 all, none). 253 </p></li><li class="listitem"><p> 254 <code class="classname">__pool_alloc</code> 255 </p><p> 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> 263 directly. 264 </p><p> 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>. 268 </p><p> 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 272 all. All three of 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; 277 </pre><p> 278 behave exactly the same way. However, the memory pool for each type 279 (and remember that different instantiations result in different types) 280 remains separate. 281 </p><p> 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 284 different number. 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 290 multiple threads. 291 </p><p> 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. 295 </p><p> 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> 301 </p><p> 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> 307 </p><p> 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++ 313 </i>. </span> 314 isoc++_1998 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 316 </i>. </span> 317 austernm 318 <span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername"> 319 C/C++ Users Journal 320 . </span></span><span class="biblioid"> 321 <a class="ulink" href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/" target="_top"> 322 </a> 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> 324 emeryb 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"> 327 </a> 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> 329 bergerzorn 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"> 332 </a> 333 . </span></p></div><div class="biblioentry" title="Allocator Types"><a id="id598997"></a><p><span class="title"><i>Allocator Types</i>. </span> 334 kreftlanger 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"> 336 C/C++ Users Journal 337 . </span></span><span class="biblioid"> 338 <a class="ulink" href="http://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html" target="_top"> 339 </a> 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> 341 tcpl 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"> 343 Addison Wesley 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> 345 yenf 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> 347