Allocators and allocation

The latest version of this document is always available at http://gcc.gnu.org/onlinedocs/libstdc++/20_util/allocator.html.

To the libstdc++ homepage.


The C++ Standard encapsulates memory management characteristics for strings, container classes, and parts of iostreams in a template class called std::allocator. This class, and base classes of it, are the superset of available free store ("heap") management classes.

Standard requirements

The C++ standard only gives a few directives in this area:

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. This method may be slower 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 __gnu_cxx::new_allocator implements the simple operator new and operator delete semantics, while __gnu_cxx::malloc_allocator implements much the same thing, only with the C language functions std::malloc and std::free.

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 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 operators new and delete are not always called to pass the memory on, either, which is a speed bonus. Examples of allocators that use these techniques are __gnu_cxx::bitmap_allocator, __gnu_cxx::pool_allocator, and __gnu_cxx::__mt_alloc.

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 abi::__cxa_atexit is not recommended.

Versions of libstdc++ prior to 3.4 cache allocations in a memory pool, instead of passing through to call the global allocation operators (ie, __gnu_cxx::pool_allocator). More recent versions default to the simpler __gnu_cxx::new_allocator.

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:

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 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
__gnu_cxx::throw_allocator<T> <ext/throw_allocator.h> 4.2.0

More details on each of these extension allocators follows.

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. The Standard Librarian: What Are Allocators Good For?

Berger, Emery, The Hoard memory allocator

Berger, Emery with Ben Zorn & Kathryn McKinley, OOPSLA 2002 Reconsidering Custom Memory Allocation

Kreft, Klaus and Angelika Langer, C++ Report, June 1998 Allocator Types

Stroustrup, Bjarne, 19.4 Allocators, The C++ Programming Language, Special Edition, Addison Wesley, Inc. 2000

Yen, Felix, Yalloc: A Recycling C++ Allocator


Return to the top of the page or to the libstdc++ homepage.


See license.html for copying conditions. Comments and suggestions are welcome, and may be sent to the libstdc++ mailing list.