Subject: Re: [boost] [Countertree + Suballocator] New Version
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2012-04-13 08:06:57
On 12/04/12 12:18, Francisco José Tapia wrote:
> *SUBALLOCATOR *
> A very hard test for the allocators are the data structures which need a
> very high number (several millions) of elements of the same size, like the
> STL list, set, multiset, map or multimap.
> When the number of elements grow, many allocators begin to have speed
> problems. The solution proposed for this problem are the custom allocators.
> These allocators are very fast, but many of them present additional
> problems related with the memory consumption. And they don't work well when
> they must manage many types of data.
> When the allocators receive the request from the program, they request
> memory to the Operating System, and the memory consumed by the program
> grows up.
> When the program return to the allocators the request, many allocators have
> problems for to return the memory freed to the Operating System (The
> std::allocator of GCC 4.6 don't return well the memory, and the
> std::allocator of Visual C++, return, but it is slower than the GCC
> If you use only one allocator, you have a bad management or in the speed
> of equal size elements, or with a wide variety of elements. If you use two
> allocators, the memory freed by an allocator can't be used by the other,
> and the memory consumption is very high, and when decrease the number of
> elements to manage, the memory don't decrease.
> These problems are specially important in two environments : a) When you
> have a limited resources, as occurs in the mobile phones, pads ... b) When
> the programs must run continuously in a multitask environment
> The solution is the suballocator. It is a mechanism for to manage in a
> fast way a greater number (hundred millions) of elements with the same
> The suballocator is a layer over the allocator (any allocator with the STL
> interface). The suballocator receives an allocator as template parameter.
> When the suballocator needs memory, request memory from the allocator, and
> when the memory is not used, is returned to the allocator. The suballocator
> present the same interface than the STL allocator. Form the view point of
> the data structures, the suballocator is other allocator
> The suballocator always return the first element free. This improve the
> cache performance and the speed of the data structures. This simple memory
> schema permit to the allocators return memory to the Operating System and
> decrease the memory used by the program, as demonstrate the programs in the
> benchmarks, and you can see in the benchmark point.
> With the suballocator
> a) We have a very *fast allocation* (3 times faster than GCC 4.6
> std::allocator, 3.5 times faster than Visual Studio 10 std::allocator )
> b) Return memory to the allocator, for to be used by others types of data.
> Many allocators, return this memory to the Operating System, and *decrease
> the memory used by the program *
> c) You *can use with any allocator* if according with the STL definition.
> The suballocator provides speed and memory management to any allocator.
> d) In the insertion in a std::set<uint64_t> , the time spent by the
> allocator is around 1%, but the suballocator save around 35% of time . The
> suballocator always provide the first position free, This provide us a very
> compact data are, which *improve the cache performance*
> All the information showed here is explained and detailed in the point
> Suballocator. All the information is extracted from the programs in the
> benchmarks folder.
From what you're describing, this looks like region-based memory
management. In C++, the most common strategy for this kind of thing is
How does your allocator differ from the usual arena ones?
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk