This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[libstdc++] Document the allocators.
- From: Phil Edwards <pedwards at disaster dot jaj dot com>
- To: libstdc++ at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Tue, 27 Nov 2001 19:06:08 -0500
- Subject: [libstdc++] Document the allocators.
These will probably be changing on a weekly basis before we're through,
but hopefully they will answer questions for users and fellow developers.
2001-11-27 Phil Edwards <pme@gcc.gnu.org>
* docs/html/explanations.html: New section, empty for now.
* docs/html/17_intro/howto.html: Cleanup. Move unrelated link...
* docs/html/23_containers/howto.html: ...to here. Break up and
rewrap threading discussion to emphasize warning. Move malloc text...
* docs/html/ext/howto.html: ...to here. New section. Describe
allocators and __USE_MALLOC effects.
* docs/html/ext/sgiexts.html: Mention their code.
Index: docs/html/explanations.html
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/docs/html/explanations.html,v
retrieving revision 1.6
diff -u -3 -p -r1.6 explanations.html
--- explanations.html 2001/10/11 18:41:42 1.6
+++ explanations.html 2001/11/27 23:58:49
@@ -61,6 +61,15 @@ design</a></h1>
</p>
+<hr>
+<a name="alloc"><h3>Internal Allocators</h3></a>
+<p>
+</p>
+<p>Return <a href="#top">to the top of the page</a> or
+ <a href="http://gcc.gnu.org/libstdc++/";>to the homepage</a>.
+</p>
+
+
<!-- ####################################################### -->
<hr>
Index: docs/html/17_intro/howto.html
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/docs/html/17_intro/howto.html,v
retrieving revision 1.17
diff -u -3 -p -r1.17 howto.html
--- howto.html 2001/11/23 16:29:00 1.17
+++ howto.html 2001/11/27 23:58:49
@@ -74,7 +74,7 @@
</p>
<p>All normal disclaimers aside, multithreaded C++ application are
only supported when libstdc++ and all user code was built with
- compilers which report (via <em>gcc/g++ -v</em>) the same thread
+ compilers which report (via <code> gcc/g++ -v </code>) the same thread
model and that model is not <em>single</em>. As long as your
final application is actually single-threaded, then it should be
safe to mix user code built with a thread model of
@@ -89,7 +89,7 @@
</p>
<p>When you link a multithreaded application, you will probably
need to add a library or flag to g++. This is a very
- non-standardized area of gcc across ports. Some ports support a
+ non-standardized area of GCC across ports. Some ports support a
special flag (the spelling isn't even standardized yet) to add
all required macros to a compilation (if any such flags are
required then you must provide the flag for all compilations not
@@ -135,9 +135,6 @@
This message</a> inspired a recent updating of issues with threading
and the SGI STL library. It also contains some example
POSIX-multithreaded STL code.
- <li><a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00136.html";>
- Here</a> is an early analysis of why __USE_MALLOC should be disabled
- for the 3.0 release of libstdc++.</a>
</ul>
(A large selection of links to older messages has been removed; many
of the messages from 1999 were lost in a disk crash, and the few
Index: docs/html/23_containers/howto.html
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/docs/html/23_containers/howto.html,v
retrieving revision 1.18
diff -u -3 -p -r1.18 howto.html
--- howto.html 2001/11/23 16:29:01 1.18
+++ howto.html 2001/11/27 23:58:49
@@ -244,14 +244,22 @@
</p>
<p>The STL implementation is currently configured to use the
high-speed caching memory allocator. If you absolutely think
- you must change this on a global basis for your platform to
- better support multi-threading, then please consult all
- commentary in include/bits/c++config. (Explicit warning since
- so many people post after getting confused while attempting
- this:) Adding -D__USE_MALLOC on the command line is not a good
- idea. Related to threading or otherwise, the current
- recommendation is that users not add any macro defines on the
- command line to enable features out of libstdc++-v3. There is
+ you must change this on a global basis for your platform to better
+ support multi-threading, then please consult all commentary in
+ include/bits/stl_alloc.h and the allocators link below.
+ <blockquote>
+ <p>(Explicit warning since so many people get confused while
+ attempting this:)
+ </p>
+ <p><strong>Adding -D__USE_MALLOC on the command
+ line is almost certainly a bad idea.</strong> Memory efficiency is
+ almost guaranteed to suffer as a result; this is
+ <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00136.html";>why
+ we disabled it for 3.0 in the first place</a>.
+ </p>
+ <p>Related to threading or otherwise, the current recommendation is
+ that users not add any macro defines on the command line to remove or
+ otherwise disable features of libstdc++-v3. There is
no condition under which it will help you without causing other
issues to perhaps raise up (possible linkage/ABI problems). In
particular, __USE_MALLOC should only be added to a libstdc++-v3
@@ -259,22 +267,22 @@
action is cautioned against), and the entire library should be
rebuilt. If you do not, then you might be violating the
one-definition rule of C/C++ and you might cause yourself untold
- problems. If you find any platform where gcc reports a
- threading model other than single and where libstdc++-v3 builds
+ problems.
+ </p>
+ </blockquote>
+ If you find any platform where gcc reports a
+ threading model other than single, and where libstdc++-v3 builds
a buggy container allocator when used with threads unless you
define __USE_MALLOC, we want to hear about it ASAP. In the
past, correctness was the main reason people were led to believe
that they should define __USE_MALLOC when using threads.
</p>
- <p>There is a better way (not standardized yet): It is possible to
+ <p>There is a better way (not standardized yet): It is possible to
force the malloc-based allocator on a per-case-basis for some
application code. The library team generally believes that this
is a better way to tune an application for high-speed using this
- implementation of the STL. Here is one possible example
- displaying the forcing of the malloc-based allocator over the
- typically higher-speed default allocator:
- <pre>
- std::list <my_type, std::__malloc_alloc_template<0> > my_malloc_based_list;</pre>
+ implementation of the STL. There is
+ <a href="../ext/howto.html#3">more information on allocators here</a>.
</p>
<p>Return <a href="#top">to top of page</a> or
<a href="../faq/index.html">to the FAQ</a>.
Index: docs/html/ext/howto.html
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/docs/html/ext/howto.html,v
retrieving revision 1.12
diff -u -3 -p -r1.12 howto.html
--- howto.html 2001/10/11 18:41:47 1.12
+++ howto.html 2001/11/27 23:58:49
@@ -143,8 +143,193 @@
<hr>
<h2><a name="3">Allocators</a></h2>
- <p>This will be blank for a while. It will describe all of the different
- memory allocators, most inherited from SGI's code. Input is solicited.
+ <p>Thread-safety, space efficiency, high speed, portability... this is a
+ mess. Where to begin?
+ </p>
+ <h3>The Rules</h3>
+ <p>The C++ standard only gives a few directives in this area:
+ <ul>
+ <li>When you add elements to a container, and the container must allocate
+ more memory to hold them, the container makes the request via its
+ <code>Allocator</code> template parameter. This includes adding
+ char's to the string class, which acts as a regular STL container
+ in this respect.
+ <li>The default <code>Allocator</code> of every container-of-T is
+ <code>std::allocator<T></code>.
+ <li>The interface of the <code>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:
+ <pre>
+ T* allocate (size_type n, const void* hint = 0);
+ void deallocate (T* p, size_type n);</pre>
+ (This is a simplicifcation; the real signatures use nested typedefs.)
+ The <code>"n"</code> arguments in both those functions is a
+ <em>count</em> of the number of T's to allocate space for,
+ <em>not their total size</em>.
+ <li>"The storage is obtained by calling
+ <code>::operator new(size_t)</code>, but it is unspecified when or
+ how often this function is called. The use of <code>hint</code>
+ is unspecified, but intended as an aid to locality if an
+ implementation so desires." [20.4.1.1]/6
+ </ul>
+ </p>
+ <h3>Problems and Possibilities</h3>
+ <p>The easiest way of fulfilling the requirements is to call operator new
+ each time a container needs memory, and to call operator delete each
+ time the container releases memory. <strong>BUT</strong>
+ <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html";>this
+ method is horribly slow</a>.
+ </p>
+ <p>Or we can keep old memory around, and reuse it in a pool to save time.
+ The old libstdc++-v2 used a memory pool, and so do we. As of 3.0,
+ <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00136.html";>it's
+ on by default</a>. The pool is shared among all the containers in the
+ program: when your program's std::vector<int> gets cut in half
+ and frees a bunch of its storage, that memory can be reused by the
+ private std::list<WonkyWidget> brought in from a KDE library
+ that you linked against. And we don't have to call operator's new and
+ delete to pass the memory on, ether, which is a speed bonus.
+ <strong>BUT</strong>...
+ </p>
+ <p>What about threads? No problem: in a threadsafe environment, the
+ memory pool is manipulated atomically, so you can grow a container in
+ one thread and shrink it in another, etc. <strong>BUT</strong> what
+ if threads in libstdc++-v3 aren't set up properly?
+ <a href="../faq/index.html#5_6">That's been answered already</a>.
+ </p>
+ <p><strong>BUT</strong> what if you want to use your own allocator? What
+ if you plan on using a runtime-loadable version of malloc() which uses
+ shared telepathic anonymous mmap'd sections serializable over a
+ network, so that memory requests <em>should</em> go through malloc?
+ And what if you need to debug it?
+ </p>
+ <p>Well then:
+ </p>
+ <h3>Available allocators in namespace std</h3>
+ <p>First I'll describe the situation as it exists for the code which will
+ be released in GCC 3.1. This situation is extremely fluid. Then I'll
+ describe the differences for 3.0.x, which will not change much in
+ this respect.
+ </p>
+ <p>As a general rule of thumb, users are not allowed to use names which
+ begin with an underscore. This means that to be portable between
+ compilers, none of the following may be used in your program directly.
+ (If you decide to be unportable, then you're free do do what you want,
+ but it's not our fault if stuff breaks.) They are presented here for
+ information for maintainers and contributors in addition to users, but
+ we will probably make them available for users in 3.1 somehow.
+ </p>
+ <p>These classes are always available:
+ <ul>
+ <li><code>__new_alloc</code> simply wraps <code>::operator new</code>
+ and <code>::operator delete</code>.
+ <li><code>__malloc_alloc_template<int inst></code> simply wraps
+ <code>malloc</code> and <code>free</code>. There is also a hook
+ for an out-of-memory handler (for new/delete this is taken care of
+ elsewhere). The <code>inst</code> parameter is described below.
+ This class was called <code>malloc_alloc</code> in earlier versions.
+ <li><code>allocator<T></code> has already been described; it is
+ The Standard Allocator for instances of T. It uses the internal
+ <code>__alloc</code> typedef (see below) to satisy its requests.
+ <li><code>__simple_alloc<T,A></code> is a wrapper around another
+ allocator, A, which itself is an allocator for instances of T.
+ This is primarily used in an internal "allocator traits"
+ class which helps encapsulate the different styles of allocators.
+ <li><code>__debug_alloc<A></code> is also 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>deallocate()</code>, the stored
+ size is checked, and assert() is used to guarantee they match.
+ <li><code>__allocator<T,A></code> is an adaptor. Many of these
+ allocator classes have a consistent yet non-standard interface.
+ Such classes can be changed to a conforming interface with this
+ wrapper: <code>__allocator<T, __alloc></code> is thus the
+ same as <code>allocator<T></code>.
+ </ul>
+ </p>
+ <p>An internal typedef, <code> __mem_interface </code>, is defined to be
+ <code>__new_alloc</code> by default.
+ </p>
+ <p>Normally,
+ <code> __default_alloc_template<bool thr, int inst> </code>
+ is also available. This is the high-speed pool, called the default
+ node allocator. The reusable memory is shared among identical
+ instantiations of
+ this type. It calls through <code>__mem_interface</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>__mem_interface</code> directly.
+ </p>
+ <p>Its <code>inst</code> parameter is described below. The
+ <code>thr</code> boolean determines whether the pool should be
+ manipulated atomically or not. Two typedefs are provided:
+ <code>__alloc</code> is defined as this node allocator with thr=true,
+ and therefore is threadsafe, while <code>__single_client_alloc</code>
+ defines thr=false, and is slightly faster but unsafe for multiple
+ threads.
+ </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. In this situation,
+ <code>__alloc</code> should not be noticably slower than
+ <code>__single_client_alloc</code>.)
+ </p>
+ <h3>A cannon to swat a fly:<code> __USE_MALLOC</code></h3>
+ <p>If you've already read <a href="../23_containers/howto.html#3">this
+ advice</a> and decided to define this macro, then the situation changes
+ thusly:
+ <ol>
+ <li><code>__mem_interface</code>, and
+ <li><code>__alloc</code>, and
+ <li><code>__single_client_alloc</code> are all typedef'd to
+ <code>__malloc_alloc_template</code>.
+ <li><code>__default_alloc_template</code> is no longer available.
+ At all. Anywhere. <!-- might change? -->
+ </ol>
+ </p>
+ <h3>Writing your own allocators</h3>
+ <p>Depending on your application (a specific program, a generic library,
+ etc), allocator classes tend to be one of two styles: "SGI"
+ or "standard". See the comments in stl_alloc.h for more
+ information on this crucial difference.
+ </p>
+ <p>At the bottom of that header is a helper type,
+ <code>_Alloc_traits</code>, and various specializations of it. This
+ allows the container classes to make possible compile-time
+ optimizations based on features of the allocator. You should provide
+ a specialization of this type for your allocator (doing so takes only
+ two or three statements).
+ </p>
+ <h3>Using non-default allocators</h3>
+ <p>You can specify different memory management schemes on a per-container
+ basis, by overriding the default <code>Allocator</code> template
+ parameter. For example, an easy
+ (but nonportable)
+ method of specifying that only malloc/free should be used instead of
+ the default node allocator is:
+ <pre>
+ std::list <my_type, std::__malloc_alloc_template<0> > my_malloc_based_list;</pre>
+ Likewise, a debugging form of whichever allocator is currently in use:
+ <pre>
+ std::deque <my_type, std::__debug_alloc<std::__alloc> > debug_deque;</pre>
+ </p>
+ <h3><code>inst</code></h3>
+ <p>The <code>__malloc_alloc_template</code> and
+ <code>__default_alloc_template</code> classes take an integer parameter,
+ called inst here. This number is completely unused.
+ </p>
+ <p> More soon.
+ </p>
+ <p>
+ </p>
+ <h3>3.0.x</h3>
+ <p>I don't even remember. More soon.
+ </p>
+ <p>
+ </p>
+ <p>
</p>
<p>Return <a href="#top">to top of page</a> or
<a href="../faq/index.html">to the FAQ</a>.
Index: docs/html/ext/sgiexts.html
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/docs/html/ext/sgiexts.html,v
retrieving revision 1.6
diff -u -3 -p -r1.6 sgiexts.html
--- sgiexts.html 2001/11/23 16:29:01 1.6
+++ sgiexts.html 2001/11/27 23:58:49
@@ -60,6 +60,9 @@ libstdc++-v3</a></h1>
<li>mem_fun adaptor helpers mem_fun1 and mem_fun1_ref are provided for
backwards compatibility.
</ul></p>
+<p>20.4.1 can use several different allocators; they are described on the
+ main extensions page.
+</p>
<p>20.4.3 is extended with a special version of
<code>get_temporary_buffer</code> taking a second argument. The argument
is a pointer, which is ignored, but can be used to specify the template