Index: gcc/libstdc++-v3/doc/html/manual/memory.html |
diff --git a/gcc/libstdc++-v3/doc/html/manual/memory.html b/gcc/libstdc++-v3/doc/html/manual/memory.html |
deleted file mode 100644 |
index 47327f3f12fc1fc306b1d0c132bb38d6a36d55cd..0000000000000000000000000000000000000000 |
--- a/gcc/libstdc++-v3/doc/html/manual/memory.html |
+++ /dev/null |
@@ -1,349 +0,0 @@ |
-<?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> |