Extended functionality: Extended allocators

Many C++ programmers have ever wondered where does good old realloc fit in C++. And that's a good question. Could we improve vector performance using memory expansion mechanisms to avoid too many copies? But vector is not the only container that could benefit from an improved allocator interface: we could take advantage of the insertion of multiple elements in list using a burst allocation mechanism that could amortize costs (mutex locks, free memory searches...) that can't be amortized when using single node allocation strategies.

These improvements require extending the STL allocator interface and use make use of a new general purpose allocator since new and delete don't offer expansion and burst capabilities.

Boost.Container containers support an extended allocator interface based on an evolution of proposals N1953: Upgrading the Interface of Allocators using API Versioning, N2045: Improving STL allocators and the article Applying classic memory allocation strategies to C++ containers. The extended allocator interface is implemented by allocator, adaptive_pool and node_allocator classes.
Extended allocators use a modified Doug Lea Malloc (DLMalloc) low-level allocator and offers an C API to implement memory expansion and burst allocations. DLmalloc is known to be very size and speed efficient, and this allocator is used as the basis of many malloc implementations, including multithreaded allocators built above DLmalloc (See ptmalloc2, ptmalloc3 or nedmalloc). This low-level allocator is implemented as a separately compiled library and the following extended allocators depend on the library:
allocator: This extended allocator offers expansion, shrink-in place and burst allocation capabilities implemented as a thin wrapper around the modified DLMalloc. It can be used with all containers and it should be the default choice when the programmer wants to use extended allocator capabilities.
node_allocator: It's a Simple Segregated Storage allocator, similar to Boost.Pool that takes advantage of the modified DLMalloc burst interface. It does not return memory to the DLMalloc allocator (and thus, to the system), unless explicitly requested. It does offer a very small memory overhead so it's suitable for node containers ([boost::container::list list], [boost::container::slist slist] [boost::container::set set]...) that allocate very small value_types and it offers improved node allocation times for single node allocations with respecto to allocator.
adaptive_pool: It's a low-overhead node allocator that can return memory to the system. The overhead can be very low (< 5% for small nodes) and it's nearly as fast as node_allocator. It's also suitable for node containers.

Use them simply specifying the new allocator in the corresponding template argument of your favourite container:

#include <boost/container/vector.hpp>
#include <boost/container/flat_set.hpp>
#include <boost/container/list.hpp>
#include <boost/container/set.hpp>

//"allocator" is a general purpose allocator that can reallocate
//memory, something useful for vector and flat associative containers
#include <boost/container/allocator.hpp>

//"adaptive_pool" is a node allocator, specially suited for
//node-based containers
#include <boost/container/adaptive_pool.hpp>

int main ()
{
   using namespace boost::container;

   //A vector that can reallocate memory to implement faster insertions
   vector<int, allocator<int> > extended_alloc_vector;

   //A flat set that can reallocate memory to implement faster insertions
   flat_set<int, std::less<int>, allocator<int> > extended_alloc_flat_set;

   //A list that can manages nodes to implement faster
   //range insertions and deletions
   list<int, adaptive_pool<int> > extended_alloc_list;

   //A set that can recycle nodes to implement faster
   //range insertions and deletions
   set<int, std::less<int>, adaptive_pool<int> > extended_alloc_set;

   //Now user them as always
   extended_alloc_vector.push_back(0);
   extended_alloc_flat_set.insert(0);
   extended_alloc_list.push_back(0);
   extended_alloc_set.insert(0);

   //...
   return 0;
}

Boost C++ Libraries

Extended functionality: Extended allocators