[boost] [container] Experimental support for memory expansion in vector and burst allocation in node containers

Subject: [boost] [container] Experimental support for memory expansion in vector and burst allocation in node containers
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2014-02-16 07:41:16

Hi to all,

Some years later than I expected, I've committed to the master branch 
(after regression tests in develop were ok) a new feature for 
Boost.Container: new experimental allocators that support memory 
expansion and burst allocation in order to improve insertion and erasure 
times in most containers. The interface of these allocators is a 
variation of the interface I proposed in N2045. The interface is still 
experimental and not ready to be used by other containers as it's quite 
complex to handle and I think it can be further improved. Nevertheless, 
Boost.Container users can benefit from improved performance just using 
these allocators.

The first experiment using this approach can be found in my old article 
"Applying classic memory allocation strategies to C++ containers" 
(http://www.drivehq.com/web/igaztanaga/allocplus/). In that article, 
Boost.Interprocess containers were modified to support N2045 and 
DLMalloc was version 2.8.3. In the new version the extended system 
allocator is based on DLMalloc version 2.8.6 (I've noticed a performance 
improvement in DLMalloc in the new version) and requires linking a new 
Boost.Container library. Boost.Container is still header-only if 
extended allocators are not used.

DLMalloc is known to be size and speed efficient for non heavily 
multithreaded environments, but Boost.Container DLMalloc extension is 
*not* a replacement for multithreaded allocators (say ptmalloc2, 
ptmalloc3, nedmalloc, tcmalloc, jemalloc...). Your default system 
allocator will be more efficient than Boost.Container for highly 
multithreaded environments. On the other hand, at least in Windows and 
Linux, the allocator seems to be very efficient in non-multithreaded 
programs.

The following extended allocators are provided:

* boost::container::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.

* boost::container::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 that allocate very small value_types and it offers improved 
node allocation times for single node allocations with respect to 
boost::container::allocator.

* boost::container::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 
boost::container::node_allocator. It's also suitable for node 
containers. More details on the implementation of this allocator can be 
found in http://www.drivehq.com/web/igaztanaga/allocplus/#Chapter3.

The goal of these extended allocators in Boost.Container is to start 
building widespread existing practice in regularly requested features 
from container users (realloc-like behaviour in vector, amortizing 
several node allocation in range insertions, etc...). I'm not an 
allocator expert, nor a HPC guru. These new allocators are just the 
first step of an experiment that I hope real experts will improve. I 
will appreciate any comment, bug report or suggestion.

Thanks,

Ion