Allocators and allocation
The latest version of this document is always available at
http://gcc.gnu.org/onlinedocs/libstdc++/20_util/allocator.html
http://gcc.gnu.org/onlinedocs/libstdc++/20_util/allocator.html
.
To the
http://gcc.gnu.org/libstdc++/
libstdc++-v3 homepage
.
The C++ Standard encapsulates memory management characteristics
for strings, container classes, and parts of iostreams in a
template class called
std::allocator
.
Standard requirements
The C++ standard only gives a few directives in this area:
When you add elements to a container, and the container must allocate
more memory to hold them, the container makes the request via its
Allocator
template parameter.  This includes adding
chars to the string class, which acts as a regular STL container
in this respect.
The default
Allocator
of every container-of-T is
std::allocator<T>
.
The interface of the
allocator<T>
class is
extremely simple.  It has about 20 public declarations (nested
typedefs, member functions, etc), but the two which concern us most
are:
T*    allocate   (size_type n, const void* hint = 0);
void  deallocate (T* p, size_type n);
(This is a simplification; the real signatures use nested typedefs.)
The
"n"
arguments in both those functions is a
count
of the number of T's to allocate space for,
not their total size
.
"The storage is obtained by calling
::operator new(size_t)
, but it is unspecified when or
how often this function is called.  The use of
hint
is unspecified, but intended as an aid to locality if an
implementation so desires." [20.4.1.1]/6
Complete details cam be found in the C++ standard, look in
[20.4 Memory].
Problems and Possibilities
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.
BUT
http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html
this
method is horribly slow
.
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,
http://gcc.gnu.org/ml/libstdc++/2001-05/msg00136.html
it's
on by default
.  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 operators new and
delete to pass the memory on, either, which is a speed bonus.
BUT
...
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.
BUT
what
if threads in libstdc++-v3 aren't set up properly?
../faq/index.html#5_6
That's been answered already
.
BUT
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
should
go through malloc?
And what if you need to debug it?
Implementation details of
std::allocator
The implementation of
std::allocator
has continued
to evolve through successive releases. Here's a brief history.
3.0, 3.1, 3.2, 3.3
During this period, all allocators were written to the SGI
style, and all STL containers expected this interface. This
interface had a traits class called
_Alloc_traits
that
attempted to provide more information for compile-time allocation
selection and optimization. This traits class had another allocator
wrapper,
__simple_alloc<T,A>
, which was a
wrapper around another allocator, A, which itself is an allocator
for instances of T. But wait, there's more:
__allocator<T,A>
is another adapter.  Many of
the provided allocator classes were SGI style: such classes can be
changed to a conforming interface with this wrapper:
__allocator<T, __alloc>
is thus the same as
allocator<T>
.
The class
std::allocator
use the typedef
__alloc
to select an underlying allocator that
satisfied memory allocation requests. The selection of this
underlying allocator was not user-configurable.
3.4
For this and later releases, 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. Because of this,
__simple_alloc, __allocator, __alloc,
and
_Alloc_traits
have all been removed.
The class
std::allocator
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.
The base class that
std::allocator
is derived from
is not user-configurable.
How the default allocation strategy is selected.
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.
Three synthetic benchmarks have been created that provide data
that is used to compare different C++ allocators. These tests are:
Insertion. Over multiple iterations, various STL container
objects have elements inserted to some maximum amount. A variety
of allocators are tested.
Test source
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.
Insertion, clear, and re-insertion in a multi-threaded
environment.  Over multiple iterations, several threads are
started that insert elements into a STL container, then assign a
null instance of the same type to clear memory, and then
re-insert the same number of elements. Several STL containers and
multiple allocators are tested. 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
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc%2b%2b-v3/testsuite/performance/20_util/allocator/insert_insert.cc
here.
A threaded producer/consumer model.
Test source
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc%2b%2b-v3/testsuite/performance/20_util/allocator/producer_consumer.cc
here.
Disabling memory caching.
In use,
std::allocator
may allocate and deallocate
using implementation-specified strategies and heuristics. Because of
this, every call to an allocator object's
allocate
member function may not actually call the global operator new. This
situation is also duplicated for calls to the
deallocate
member function.
This can be confusing.
In particular, this can make debugging memory errors more
difficult, especially when using third party tools like valgrind or
debug versions of
new
.
There are various ways to solve this problem. One would be to
use a custom allocator that just called operators
new
and
delete
directly, for every
allocation. (See include/ext/new_allocator.h, for instance.)
However, that option would involve changing source code to use the 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
allocate
and directly deallocate
with every call of
deallocate
, regardless of
efficiency. As it turns out, this last option is available,
although the exact mechanism has evolved with time.
For GCC releases from 2.95 through the 3.1 series, defining
__USE_MALLOC
on the gcc command line would change the
default allocation strategy to instead use
malloc
and
free
. See
../23_containers/howto.html#3
this note
for details as to why this was something needing improvement.
Starting with GCC 3.2, and continued in the 3.3 series, to
globally disable memory caching within the library for the
default allocator, merely set GLIBCPP_FORCE_NEW (at this time,
with any value) in the system's environment before running the
program. If your program crashes with GLIBCPP_FORCE_NEW in the
environment, it likely means that you linked against objects
built against the older library.  Code to support this extension
is fully compatible with 3.2 code if GLIBCPP_FORCE_NEW is not in
the environment.
As it turns out, the 3.4 code base continues to use this
mechanism, only the environment variable has been changed to
GLIBCXX_FORCE_NEW.
Other allocators
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.
Allocator (3.4)
Header (3.4)
Allocator (3.[0-3])
Header (3.[0-3])
__gnu_cxx::new_allocator<T>
<ext/new_allocator.h>
std::__new_alloc
<memory>
__gnu_cxx::malloc_allocator<T>
<ext/malloc_allocator.h>
std::__malloc_alloc_template<int>
<memory>
__gnu_cxx::debug_allocator<T>
<ext/debug_allocator.h>
std::debug_alloc<T>
<memory>
__gnu_cxx::__pool_alloc<T>
<ext/pool_allocator.h>
std::__default_alloc_template<bool,int>
<memory>
__gnu_cxx::__mt_alloc<T>
<ext/mt_allocator.h>
__gnu_cxx::bitmap_allocator<T>
<ext/bitmap_allocator.h>
Releases after gcc-3.4 have continued to add to the collection
of available allocators. All of these new allocators are
standard-style. The following table includes details, along with
the first released version of GCC that included the extension allocator.
Allocator
Include
Version
__gnu_cxx::array_allocator<T>
<ext/array_allocator.h>
4.0.0
More details on each of these extension allocators follows.
new_allocator
Simply wraps
::operator new
and
::operator delete
.
malloc_allocator
Simply wraps
malloc
and
free
.  There is also a hook
for an out-of-memory handler (for new/delete this is taken care of
elsewhere).
array_allocator
Allows allocations of known and fixed sizes using existing
global or external storage allocated via construction of
std::tr1::array objects. By using this allocator, fixed size
containers (including std::string) can be used without
instances calling
::operator new
and
::operator delete
. 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 libstdc++ testsuite.
debug_allocator
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
deallocate()
, the stored
size is checked, and assert() is used to guarantee they match.
__pool_alloc
A high-performance, single pool allocator.  The reusable
memory is shared among identical instantiations of this type.
It calls through
::operator new
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
::operator new
directly.
For versions of
__pool_alloc
after 3.4.0, there is
only one template parameter, as per the standard.
Older versions of this class take a boolean template parameter,
called
thr
, and an integer template parameter,
called
inst
.
The
inst
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
typedef  __pool_alloc<true,0>    normal;
typedef  __pool_alloc<true,1>    private;
typedef  __pool_alloc<true,42>   also_private;
behave exactly the same way.  However, the memory pool for each type
(and remember that different instantiations result in different types)
remains separate.
The library uses
0
in all its instantiations.  If you
wish to keep separate free lists for a particular purpose, use a
different number.
The
thr
boolean determines whether the pool should
be manipulated atomically or not.  When thr=true, the allocator
is is threadsafe, while thr=false, and is slightly faster but
unsafe for multiple threads.
For thread-enabled configurations, the pool is locked with a
single big lock. In some situations, this implementation detail may
result in severe performance degredation.
(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.)
__mt_alloc
A high-performance
fixed-size allocator. It has its own documentation, found
../ext/mt_allocator.html
here
.
bitmap_allocator
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
../ext/ballocator_doc.html
here
.
Using a specific allocator
You can specify different memory management schemes on a
per-container basis, by overriding the default
Allocator
template parameter.  For example, an easy
(but non-portable) method of specifying that only malloc/free
should be used instead of the default node allocator is:
std::list <int, __gnu_cxx::malloc_allocator<int> >  malloc_list;
Likewise, a debugging form of whichever allocator is currently in use:
std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > >  debug_deque;
Writing custom allocators
Writing a portable C++ allocator would dictate that the
interface would look much like the one specified for
std::allocator
. Additional member functions, but not
subtractions, would be permissible.
Probably the best place to start would be to copy one of the
extension allocators already shipped with libstdc++: say,
new_allocator
.
Bibliography / Further Reading
ISO/IEC 14882:1998 Programming languages - C++ [20.4 Memory]
Austern, Matt, C/C++ Users Journal.
http://www.cuj.com/documents/s=8000/cujcexp1812austern/
The Standard Librarian: What Are Allocators Good
For?
Berger, Emery,
http://www.cs.umass.edu/~emery/hoard/
The Hoard memory allocator
Berger, Emery with Ben Zorn & Kathryn McKinley, OOPSLA 2002
http://www.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf
Reconsidering Custom Memory Allocation
Kreft, Klaus and Angelika Langer, C++ Report, June 1998
http://www.langer.camelot.de/Articles/C++Report/Allocators/Allocators.html
Allocator Types
Stroustrup, Bjarne, 19.4 Allocators, The C++ Programming
Language, Special Edition, Addison Wesley, Inc. 2000
Yen, Felix,
http://home.earthlink.net/~brimar/yalloc/
Yalloc: A Recycling C++ Allocator
Return
#top
to the top of the page
or
http://gcc.gnu.org/libstdc++/
to the libstdc++ homepage
.
See
../17_intro/license.html
license.html
for copying conditions.
Comments and suggestions are welcome, and may be sent to
mailto:libstdc++@gcc.gnu.org
the libstdc++ mailing list
.
