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<T></code>. 55 </li> 56 <li>The interface of the <code>allocator<T></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>"n"</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>"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." [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<int> gets cut in half 94 and frees a bunch of its storage, that memory can be reused by the 95 private std::list<WonkyWidget> 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<T,A></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<T,A></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<T, __alloc></code> is thus the same as 135 <code>allocator<T></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<T></td> 283 <td><ext/new_allocator.h></td> 284 <td>std::__new_alloc</td> 285 <td><memory></td> 286 </tr> 287 <tr> 288 <td>__gnu_cxx::malloc_allocator<T></td> 289 <td><ext/malloc_allocator.h></td> 290 <td>std::__malloc_alloc_template<int></td> 291 <td><memory></td> 292 </tr> 293 <tr> 294 <td>__gnu_cxx::debug_allocator<T></td> 295 <td><ext/debug_allocator.h></td> 296 <td>std::debug_alloc<T></td> 297 <td><memory></td> 298 </tr> 299 <tr> 300 <td>__gnu_cxx::__pool_alloc<T></td> 301 <td><ext/pool_allocator.h></td> 302 <td>std::__default_alloc_template<bool,int></td> 303 <td><memory></td> 304 </tr> 305 <tr> 306 <td>__gnu_cxx::__mt_alloc<T></td> 307 <td><ext/mt_allocator.h></td> 308 <td></td> 309 <td></td> 310 </tr> 311 <tr> 312 <td>__gnu_cxx::bitmap_allocator<T></td> 313 <td><ext/bitmap_allocator.h></td> 314 <td></td> 315 <td></td> 316 </tr> 317</table> 318 319 <p> Releases after gcc-3.4 have continued to add to the collection 320 of available allocators. All of these new allocators are 321 standard-style. The following table includes details, along with 322 the first released version of GCC that included the extension allocator. 323 </p> 324 325<table title="more extension allocators" border="1"> 326 <tr> 327 <th>Allocator</th> 328 <th>Include</th> 329 <th>Version</th> 330 </tr> 331 <tr> 332 <td>__gnu_cxx::array_allocator<T></td> 333 <td><ext/array_allocator.h></td> 334 <td>4.0.0</td> 335 </tr> 336</table> 337 338 <p>More details on each of these extension allocators follows. </p> 339 <ul> 340 <li><code>new_allocator</code> 341 <p>Simply wraps <code>::operator new</code> 342 and <code>::operator delete</code>. 343 </p> 344 </li> 345 <li><code>malloc_allocator</code> 346 <p>Simply wraps 347 <code>malloc</code> and <code>free</code>. There is also a hook 348 for an out-of-memory handler (for new/delete this is taken care of 349 elsewhere). 350 </p> 351 </li> 352 <li><code>array_allocator</code> 353 <p>Allows allocations of known and fixed sizes using existing 354 global or external storage allocated via construction of 355 std::tr1::array objects. By using this allocator, fixed size 356 containers (including std::string) can be used without 357 instances calling <code>::operator new</code> and 358 <code>::operator delete</code>. This capability allows the 359 use of STL abstractions without runtime complications or 360 overhead, even in situations such as program startup. For 361 usage examples, please consult the libstdc++ testsuite. 362 </p> 363 </li> 364 <li><code>debug_allocator</code> 365 <p> A wrapper around an 366 arbitrary allocator A. It passes on slightly increased size 367 requests to A, and uses the extra memory to store size information. 368 When a pointer is passed to <code>deallocate()</code>, the stored 369 size is checked, and assert() is used to guarantee they match. 370 </p> 371 </li> 372 <li><code>__pool_alloc</code> 373 <p> A high-performance, single pool allocator. The reusable 374 memory is shared among identical instantiations of this type. 375 It calls through <code>::operator new</code> to obtain new memory 376 when its lists run out. If a client container requests a block 377 larger than a certain threshold size, then the pool is bypassed, 378 and the allocate/deallocate request is passed to 379 <code>::operator new</code> directly. </p> 380 381 <p> For versions of <code>__pool_alloc</code> after 3.4.0, there is 382 only one template parameter, as per the standard. 383 </p> 384 385 <p> Older versions of this class take a boolean template parameter, 386 called <code>thr</code>, and an integer template parameter, 387 called <code>inst</code>. 388 </p> 389 390 <p>The <code>inst</code> number is used to track additional memory 391 pools. The point of the number is to allow multiple 392 instantiations of the classes without changing the semantics at 393 all. All three of 394 </p> 395 396 <pre> 397 typedef __pool_alloc<true,0> normal; 398 typedef __pool_alloc<true,1> private; 399 typedef __pool_alloc<true,42> also_private;</pre> 400 <p>behave exactly the same way. However, the memory pool for each type 401 (and remember that different instantiations result in different types) 402 remains separate. 403 </p> 404 <p>The library uses <strong>0</strong> in all its instantiations. If you 405 wish to keep separate free lists for a particular purpose, use a 406 different number. 407 </p> 408 <p>The <code>thr</code> boolean determines whether the pool should 409 be manipulated atomically or not. When thr=true, the allocator 410 is is threadsafe, while thr=false, and is slightly faster but 411 unsafe for multiple threads. 412 </p> 413 414 <p>For thread-enabled configurations, the pool is locked with a 415 single big lock. In some situations, this implementation detail may 416 result in severe performance degredation. 417 </p> 418 419 <p>(Note that the GCC thread abstraction layer allows us to provide safe 420 zero-overhead stubs for the threading routines, if threads were 421 disabled at configuration time.) 422 </p> 423 424 </li> 425 426 <li><code>__mt_alloc</code> 427 <p>A high-performance 428 fixed-size allocator. It has its own documentation, found <a 429 href="../ext/mt_allocator.html">here</a>. 430 </p> 431 </li> 432 433 <li><code>bitmap_allocator</code> 434 <p>A high-performance allocator that uses a bit-map to keep track 435 of the used and unused memory locations. It has its own 436 documentation, found <a 437 href="../ext/ballocator_doc.html">here</a>. 438 </p> 439 </li> 440 </ul> 441 442 443<h3 class="left"> 444 <a name="using_custom_allocators">Using a specific allocator</a> 445</h3> 446 <p>You can specify different memory management schemes on a 447 per-container basis, by overriding the default 448 <code>Allocator</code> template parameter. For example, an easy 449 (but non-portable) method of specifying that only malloc/free 450 should be used instead of the default node allocator is: 451 </p> 452 <pre> 453 std::list <int, __gnu_cxx::malloc_allocator<int> > malloc_list;</pre> 454 Likewise, a debugging form of whichever allocator is currently in use: 455 <pre> 456 std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > > debug_deque;</pre> 457 458 459<h3 class="left"> 460 <a name="custom_allocators">Writing custom allocators</a> 461</h3> 462 <p> Writing a portable C++ allocator would dictate that the 463 interface would look much like the one specified for <code> 464 std::allocator</code>. Additional member functions, but not 465 subtractions, would be permissible. 466 </p> 467 468 <p> Probably the best place to start would be to copy one of the 469 extension allocators already shipped with libstdc++: say, <code> 470 new_allocator </code>. 471 </p> 472 473 474<h3 class="left"> 475 <a name="biblio">Bibliography / Further Reading</a> 476</h3> 477 <p> 478 ISO/IEC 14882:1998 Programming languages - C++ [20.4 Memory] 479 </p> 480 481 <p> 482 Austern, Matt, C/C++ Users Journal. 483 <a href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/">The Standard Librarian: What Are Allocators Good 484 For?</a> 485 </p> 486 487 <p> 488 Berger, Emery, 489 <a href="http://www.cs.umass.edu/~emery/hoard/"> The Hoard memory allocator </a> 490 </p> 491 492 <p> 493 Berger, Emery with Ben Zorn & Kathryn McKinley, OOPSLA 2002 494 <a href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf">Reconsidering Custom Memory Allocation</a> 495 </p> 496 497 <p> 498 Kreft, Klaus and Angelika Langer, C++ Report, June 1998 499 <a href="http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html">Allocator Types</a> 500 </p> 501 502 <p> 503 Stroustrup, Bjarne, 19.4 Allocators, The C++ Programming 504 Language, Special Edition, Addison Wesley, Inc. 2000 505 </p> 506 507 <p> 508 Yen, Felix, <a href="http://home.earthlink.net/~brimar/yalloc/">Yalloc: A Recycling C++ Allocator</a> 509 </p> 510 511<hr /> 512<p>Return <a href="#top">to the top of the page</a> or 513 <a href="http://gcc.gnu.org/libstdc++/">to the libstdc++ homepage</a>. 514</p> 515 516 517<!-- ####################################################### --> 518 519<hr /> 520<p class="fineprint"><em> 521See <a href="../17_intro/license.html">license.html</a> for copying conditions. 522Comments and suggestions are welcome, and may be sent to 523<a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>. 524</em></p> 525 526 527</body> 528</html> 529