[LLVMdev] SUBALLOCATOR

[Francisco José Tapia]

I am a teacher of computing programming in Madrid (Spain).Reciently I had
presented for to be examined new library in Boost.(
http://dl.dropbox.com/u/8437476/works/countertree/index.html ). I am
writting you because I think a part of this library, the suballocator, can
be useful to you.

The suballocator works with the allocator for to improve the allocation
speed of fixed size elements, like in the Standard Library list, set,
multiset, map and multimap.

In the benchmark done with CLANG 3.0 (
http://dl.dropbox.com/u/8437476/works/countertree/suballocator.html#benchmark
 ), the suballocator

a) Provide *fast allocation* *(around 2 times faster than the
std::allocator of CLANG 3.0 )*

b) *Return memory to the allocator, for to be used by others types of data*.
For to improve the speed allocating of the small size elements, many
allocators request to the Operating System big chucks of memory. With this,
the allocator don't need request memory to the operating system for each
allocation. But many allocators don't return well the unused chucks of
memory to the Operating System and the memory used by the allocator is the
maximum used, never decrease . The suballocator have an agressive policy in
order to return the unused memory to the Operating System and decrease the
memory used by the program.

This problem is specially important in two environments :

   - When you have a limited resources, as occurs in the mobile phones,
   pads , tablets...
   - When the programs must run continuously in a multitask environment

*c) You can use with any allocator if it is according with the STL
definition*. The suballocator provides speed and memory management to any
allocator

d) In the insertion in a std::set, the allocation time is around 1%. The
suballocator obtain time reductions over the 30% respect the
std::allocator. The secret is the cache performance due to the data
locality improvement.






You can find the documentation and the code here (
http://dl.dropbox.com/u/8437476/works/countertree/suballocator.html ).

If you want to know something more, have some idea, any comment, or if you
find any error or problem, please mail me (fjtapia at gmail.com)


Sincerely yours

Francisco Tapia

fjtapia at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120605/d5b91d68/attachment.html>