Subject: Re: [boost] [Countertree + Suballocator] New Version
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-04-13 14:35:50
The internal structure of the suballocator is like the reversal of the
Hanoi Towers game. When the suballocator need memory, request to the
allocator a chuck for 1 element. If need more request a chuck of 2, and
after 4, and after 8..., always power of 2 elements. The last element
always is the biggest.
Each chuck has the memory to allocate and a heap of bits for to mark the
free elements. This heap is very fast, and shows in an easy way the first
position free in the chuck, and if the chuck is full.
In every deletion, check the number of elements free. It this is bigger
than a value and the last chuck is empty, it is returned to the allocator.
It is not a region based allocator but have many similar things. I was
surprised when checking the memory used by the program, discover the memory
The allocators of GCC 4.6 and CLANG/LLVM 3.0 have problems for to return
memory to the operating systems. If you create a std::set with 30.000.000
elements, check the memory used by the program, delete all the elements and
check the memory. You see the same memory used by the program in the two
If you do the same in Visual Studio 10, the allocator collect the memory
and return to the operating System, and the memory of the program downs a
lot. But is a byte slower than the GCC allocator
In the benchmarks, the suballocator with the std::allocator with GCC4.6,
CLANG 3.0 and VS10, is more than 3 times faster than the std:allocator
But with GCC and CLANG, the std::allocator is capable to return the memory
returned from the suballocator, to the operating system and the memory used
by the program downs.
You have graphs showing this in the documentation in the benchmarks of
El 13 de abril de 2012 14:06, Mathias Gaunard
> 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?
> Unsubscribe & other changes: http://lists.boost.org/**
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk