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
> allocator)
>
> 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
> size.
>
> 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
arena allocators.
How does your allocator differ from the usual arena ones?