--- /dev/null
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+<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.74.0" /><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.
+ 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="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>
+ Memory contains three general areas. First, function and operator
+ calls via <code class="function">new</code> and <code class="function">delete</code>
+ operator or member function calls. Second, allocation via
+ <code class="classname">allocator</code>. And finally, smart pointer and
+ intelligent pointer abstractions.
+ </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>
+ Memory management for Standard Library entities is encapsulated in a
+ class template called <code class="classname">allocator</code>. The
+ <code class="classname">allocator</code> abstraction is used throughout the
+ library in <code class="classname">string</code>, container classes,
+ algorithms, and parts of iostreams. This class, and base classes of
+ it, are the superset of available free store (“<span class="quote">heap</span>”)
+ management classes.
+</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>
+ The C++ standard only gives a few directives in this area:
+ </p><div class="itemizedlist"><ul type="disc"><li><p>
+ When you add elements to a container, and the container must
+ allocate more memory to hold them, the container makes the
+ request via its <span class="type">Allocator</span> template
+ parameter, which is usually aliased to
+ <span class="type">allocator_type</span>. This includes adding chars
+ to the string class, which acts as a regular STL container in
+ this respect.
+ </p></li><li><p>
+ The default <span class="type">Allocator</span> argument of every
+ container-of-T is <code class="classname">allocator<T></code>.
+ </p></li><li><p>
+ The interface of the <code class="classname">allocator<T></code> class is
+ extremely simple. It has about 20 public declarations (nested
+ typedefs, member functions, etc), but the two which concern us most
+ are:
+ </p><pre class="programlisting">
+ T* allocate (size_type n, const void* hint = 0);
+ void deallocate (T* p, size_type n);
+ </pre><p>
+ The <code class="varname">n</code> arguments in both those
+ functions is a <span class="emphasis"><em>count</em></span> of the number of
+ <span class="type">T</span>'s to allocate space for, <span class="emphasis"><em>not their
+ total size</em></span>.
+ (This is a simplification; the real signatures use nested typedefs.)
+ </p></li><li><p>
+ The storage is obtained by calling <code class="function">::operator
+ new</code>, but it is unspecified when or how
+ often this function is called. The use of the
+ <code class="varname">hint</code> is unspecified, but intended as an
+ aid to locality if an implementation so
+ desires. <code class="constant">[20.4.1.1]/6</code>
+ </p></li></ul></div><p>
+ Complete details cam be found in the C++ standard, look in
+ <code class="constant">[20.4 Memory]</code>.
+ </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>
+ The easiest way of fulfilling the requirements is to call
+ <code class="function">operator new</code> each time a container needs
+ memory, and to call <code class="function">operator delete</code> each time
+ 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>
+ than caching the allocations and re-using previously-allocated
+ memory, but has the advantage of working correctly across a wide
+ variety of hardware and operating systems, including large
+ clusters. The <code class="classname">__gnu_cxx::new_allocator</code>
+ implements the simple operator new and operator delete semantics,
+ while <code class="classname">__gnu_cxx::malloc_allocator</code>
+ implements much the same thing, only with the C language functions
+ <code class="function">std::malloc</code> and <code class="function">free</code>.
+ </p><p>
+ Another approach is to use intelligence within the allocator
+ class to cache allocations. This extra machinery can take a variety
+ of forms: a bitmap index, an index into an exponentially increasing
+ power-of-two-sized buckets, or simpler fixed-size pooling cache.
+ The cache is shared among all the containers in the program: when
+ your program's <code class="classname">std::vector<int></code> gets
+ cut in half and frees a bunch of its storage, that memory can be
+ reused by the private
+ <code class="classname">std::list<WonkyWidget></code> brought in from
+ a KDE library that you linked against. And operators
+ <code class="function">new</code> and <code class="function">delete</code> are not
+ always called to pass the memory on, either, which is a speed
+ bonus. Examples of allocators that use these techniques are
+ <code class="classname">__gnu_cxx::bitmap_allocator</code>,
+ <code class="classname">__gnu_cxx::pool_allocator</code>, and
+ <code class="classname">__gnu_cxx::__mt_alloc</code>.
+ </p><p>
+ Depending on the implementation techniques used, the underlying
+ operating system, and compilation environment, scaling caching
+ allocators can be tricky. In particular, order-of-destruction and
+ order-of-creation for memory pools may be difficult to pin down
+ with certainty, which may create problems when used with plugins
+ or loading and unloading shared objects in memory. As such, using
+ caching allocators on systems that do not support
+ <code class="function">abi::__cxa_atexit</code> is not recommended.
+ </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="id419128"></a>Interface Design</h4></div></div></div><p>
+ The only allocator interface that
+ is support is the standard C++ interface. As such, all STL
+ containers have been adjusted, and all external allocators have
+ been modified to support this change.
+ </p><p>
+ The class <code class="classname">allocator</code> just has typedef,
+ constructor, and rebind members. It inherits from one of the
+ high-speed extension allocators, covered below. Thus, all
+ allocation and deallocation depends on the base class.
+ </p><p>
+ The base class that <code class="classname">allocator</code> is derived from
+ may not be user-configurable.
+</p></div><div class="sect3" lang="en" xml:lang="en"><div class="titlepage"><div><div><h4 class="title"><a id="id410525"></a>Selecting Default Allocation Policy</h4></div></div></div><p>
+ It's difficult to pick an allocation strategy that will provide
+ maximum utility, without excessively penalizing some behavior. In
+ fact, it's difficult just deciding which typical actions to measure
+ for speed.
+ </p><p>
+ Three synthetic benchmarks have been created that provide data
+ that is used to compare different C++ allocators. These tests are:
+ </p><div class="orderedlist"><ol type="1"><li><p>
+ Insertion.
+ </p><p>
+ Over multiple iterations, various STL container
+ objects have elements inserted to some maximum amount. A variety
+ of allocators are tested.
+ 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>
+ 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>
+ containers.
+ </p></li><li><p>
+ Insertion and erasure in a multi-threaded environment.
+ </p><p>
+ This test shows the ability of the allocator to reclaim memory
+ on a pre-thread basis, as well as measuring thread contention
+ for memory resources.
+ Test source
+ <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>.
+ </p></li><li><p>
+ A threaded producer/consumer model.
+ </p><p>
+ Test source for
+ <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>
+ and
+ <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>
+ containers.
+ </p></li></ol></div><p>
+ The current default choice for
+ <code class="classname">allocator</code> is
+ <code class="classname">__gnu_cxx::new_allocator</code>.
+ </p></div><div class="sect3" lang="en" xml:lang="en"><div class="titlepage"><div><div><h4 class="title"><a id="id457524"></a>Disabling Memory Caching</h4></div></div></div><p>
+ In use, <code class="classname">allocator</code> may allocate and
+ deallocate using implementation-specified strategies and
+ heuristics. Because of this, every call to an allocator object's
+ <code class="function">allocate</code> member function may not actually
+ call the global operator new. This situation is also duplicated
+ for calls to the <code class="function">deallocate</code> member
+ function.
+ </p><p>
+ This can be confusing.
+ </p><p>
+ In particular, this can make debugging memory errors more
+ difficult, especially when using third party tools like valgrind or
+ debug versions of <code class="function">new</code>.
+ </p><p>
+ There are various ways to solve this problem. One would be to use
+ a custom allocator that just called operators
+ <code class="function">new</code> and <code class="function">delete</code>
+ directly, for every allocation. (See
+ <code class="filename">include/ext/new_allocator.h</code>, for instance.)
+ However, that option would involve changing source code to use
+ a non-default allocator. Another option is to force the
+ default allocator to remove caching and pools, and to directly
+ allocate with every call of <code class="function">allocate</code> and
+ directly deallocate with every call of
+ <code class="function">deallocate</code>, regardless of efficiency. As it
+ turns out, this last option is also available.
+ </p><p>
+ To globally disable memory caching within the library for the
+ default allocator, merely set
+ <code class="constant">GLIBCXX_FORCE_NEW</code> (with any value) in the
+ system's environment before running the program. If your program
+ crashes with <code class="constant">GLIBCXX_FORCE_NEW</code> in the
+ environment, it likely means that you linked against objects
+ built against the older library (objects which might still using the
+ cached allocations...).
+ </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>
+ You can specify different memory management schemes on a
+ per-container basis, by overriding the default
+ <span class="type">Allocator</span> template parameter. For example, an easy
+ (but non-portable) method of specifying that only <code class="function">malloc</code> or <code class="function">free</code>
+ should be used instead of the default node allocator is:
+ </p><pre class="programlisting">
+ std::list <int, __gnu_cxx::malloc_allocator<int> > malloc_list;</pre><p>
+ Likewise, a debugging form of whichever allocator is currently in use:
+ </p><pre class="programlisting">
+ std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > > debug_deque;
+ </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>
+ Writing a portable C++ allocator would dictate that the interface
+ would look much like the one specified for
+ <code class="classname">allocator</code>. Additional member functions, but
+ not subtractions, would be permissible.
+ </p><p>
+ Probably the best place to start would be to copy one of the
+ extension allocators: say a simple one like
+ <code class="classname">new_allocator</code>.
+ </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>
+ Several other allocators are provided as part of this
+ implementation. The location of the extension allocators and their
+ names have changed, but in all cases, functionality is
+ equivalent. Starting with gcc-3.4, all extension allocators are
+ standard style. Before this point, SGI style was the norm. Because of
+ this, the number of template arguments also changed. Here's a simple
+ chart to track the changes.
+ </p><p>
+ More details on each of these extension allocators follows.
+ </p><div class="orderedlist"><ol type="1"><li><p>
+ <code class="classname">new_allocator</code>
+ </p><p>
+ Simply wraps <code class="function">::operator new</code>
+ and <code class="function">::operator delete</code>.
+ </p></li><li><p>
+ <code class="classname">malloc_allocator</code>
+ </p><p>
+ Simply wraps <code class="function">malloc</code> and
+ <code class="function">free</code>. There is also a hook for an
+ out-of-memory handler (for
+ <code class="function">new</code>/<code class="function">delete</code> this is
+ taken care of elsewhere).
+ </p></li><li><p>
+ <code class="classname">array_allocator</code>
+ </p><p>
+ Allows allocations of known and fixed sizes using existing
+ global or external storage allocated via construction of
+ <code class="classname">std::tr1::array</code> objects. By using this
+ allocator, fixed size containers (including
+ <code class="classname">std::string</code>) can be used without
+ instances calling <code class="function">::operator new</code> and
+ <code class="function">::operator delete</code>. This capability
+ allows the use of STL abstractions without runtime
+ complications or overhead, even in situations such as program
+ startup. For usage examples, please consult the testsuite.
+ </p></li><li><p>
+ <code class="classname">debug_allocator</code>
+ </p><p>
+ A wrapper around an arbitrary allocator A. It passes on
+ slightly increased size requests to A, and uses the extra
+ memory to store size information. When a pointer is passed
+ to <code class="function">deallocate()</code>, the stored size is
+ checked, and <code class="function">assert()</code> is used to
+ guarantee they match.
+ </p></li><li><p>
+ <code class="classname">throw_allocator</code>
+ </p><p>
+ Includes memory tracking and marking abilities as well as hooks for
+ throwing exceptions at configurable intervals (including random,
+ all, none).
+ </p></li><li><p>
+ <code class="classname">__pool_alloc</code>
+ </p><p>
+ A high-performance, single pool allocator. The reusable
+ memory is shared among identical instantiations of this type.
+ It calls through <code class="function">::operator new</code> to
+ obtain new memory when its lists run out. If a client
+ container requests a block larger than a certain threshold
+ size, then the pool is bypassed, and the allocate/deallocate
+ request is passed to <code class="function">::operator new</code>
+ directly.
+ </p><p>
+ Older versions of this class take a boolean template
+ parameter, called <code class="varname">thr</code>, and an integer template
+ parameter, called <code class="varname">inst</code>.
+ </p><p>
+ The <code class="varname">inst</code> number is used to track additional memory
+ pools. The point of the number is to allow multiple
+ instantiations of the classes without changing the semantics at
+ all. All three of
+ </p><pre class="programlisting">
+ typedef __pool_alloc<true,0> normal;
+ typedef __pool_alloc<true,1> private;
+ typedef __pool_alloc<true,42> also_private;
+ </pre><p>
+ behave exactly the same way. However, the memory pool for each type
+ (and remember that different instantiations result in different types)
+ remains separate.
+ </p><p>
+ The library uses <span class="emphasis"><em>0</em></span> in all its instantiations. If you
+ wish to keep separate free lists for a particular purpose, use a
+ different number.
+ </p><p>The <code class="varname">thr</code> boolean determines whether the
+ pool should be manipulated atomically or not. When
+ <code class="varname">thr</code> = <code class="constant">true</code>, the allocator
+ is is thread-safe, while <code class="varname">thr</code> =
+ <code class="constant">false</code>, and is slightly faster but unsafe for
+ multiple threads.
+ </p><p>
+ For thread-enabled configurations, the pool is locked with a
+ single big lock. In some situations, this implementation detail
+ may result in severe performance degradation.
+ </p><p>
+ (Note that the GCC thread abstraction layer allows us to provide
+ safe zero-overhead stubs for the threading routines, if threads
+ were disabled at configuration time.)
+ </p></li><li><p>
+ <code class="classname">__mt_alloc</code>
+ </p><p>
+ A high-performance fixed-size allocator with
+ exponentially-increasing allocations. It has its own
+ documentation, found <a class="link" href="ext_allocators.html#manual.ext.allocator.mt" title="mt_allocator">here</a>.
+ </p></li><li><p>
+ <code class="classname">bitmap_allocator</code>
+ </p><p>
+ A high-performance allocator that uses a bit-map to keep track
+ of the used and unused memory locations. It has its own
+ documentation, found <a class="link" href="bitmap_allocator.html" title="bitmap_allocator">here</a>.
+ </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="id455580"></a><p><span class="title"><i>
+ ISO/IEC 14882:1998 Programming languages - C++
+ </i>. </span>
+ isoc++_1998
+ <span class="pagenums">20.4 Memory. </span></p></div><div class="biblioentry"><a id="id408540"></a><p><span class="title"><i>The Standard Librarian: What Are Allocators Good
+ </i>. </span>
+ austernm
+ <span class="author"><span class="firstname">Matt</span> <span class="surname">Austern</span>. </span><span class="publisher"><span class="publishername">
+ C/C++ Users Journal
+ . </span></span><span class="biblioid">
+ <a class="ulink" href="http://www.cuj.com/documents/s=8000/cujcexp1812austern/" target="_top">
+ </a>
+ . </span></p></div><div class="biblioentry"><a id="id411757"></a><p><span class="title"><i>The Hoard Memory Allocator</i>. </span>
+ emeryb
+ <span class="author"><span class="firstname">Emery</span> <span class="surname">Berger</span>. </span><span class="biblioid">
+ <a class="ulink" href="http://www.cs.umass.edu/~emery/hoard/" target="_top">
+ </a>
+ . </span></p></div><div class="biblioentry"><a id="id392744"></a><p><span class="title"><i>Reconsidering Custom Memory Allocation</i>. </span>
+ bergerzorn
+ <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">
+ <a class="ulink" href="http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf" target="_top">
+ </a>
+ . </span></p></div><div class="biblioentry"><a id="id422908"></a><p><span class="title"><i>Allocator Types</i>. </span>
+ kreftlanger
+ <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">
+ C/C++ Users Journal
+ . </span></span><span class="biblioid">
+ <a class="ulink" href="http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html" target="_top">
+ </a>
+ . </span></p></div><div class="biblioentry"><a id="id395999"></a><p><span class="title"><i>The C++ Programming Language</i>. </span>
+ tcpl
+ <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">
+ Addison Wesley
+ . </span></span></p></div><div class="biblioentry"><a id="id398620"></a><p><span class="title"><i>Yalloc: A Recycling C++ Allocator</i>. </span>
+ yenf
+ <span class="author"><span class="firstname">Felix</span> <span class="surname">Yen</span>. </span><span class="copyright">Copyright © . </span><span class="biblioid">
+ <a class="ulink" href="http://home.earthlink.net/~brimar/yalloc/" target="_top">
+ </a>
+ . </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>
projects / msp430-gcc.git / blobdiff