[boost] [Countertree + Suballocator] New Version

Subject: [boost] [Countertree + Suballocator] New Version
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-04-12 06:18:42

Hi

 this message is to announce the new version of the [countertree +
suballocator] library. You can find the zip file with the code and the
documentation in

https://docs.google.com/file/d/0B9lWJ1Nhb_RhRXVHSS14aGxUZjJjWFdRVC0xZ2czZw/edit?pli=1

or if you want a quick look , you can see in my web page
http://fjtapia.webs.com/works/countertree/index.html

 *COUNTERTREE *

This library is an implementation of a binary red-black counter tree. This
tree have an additional counter in each leaf. This permit the access to the
elements by the position, like in a vector. It is a random access container
with random access iterators .

 With this tree we have vectors (cntree::vector_tree) with identical
interface than std::vector. The vector_tree have the same speed inserting
and deleting in any position (all the operations are O(log N)).It is slower
than std:vector inserting and deleting at end, but much faster for to
insert and delete in any other position.

 With ordered information, we have in the cntree namespace the classes set,
multiset, map and multimap, with identical interface than the STL classes,
with the plus of access to the elements by position, like in a vector. The
iterators are random access , and you can subtract two iterators in a O(log
N) time for to know the number of nodes between them (even with the end( )
and rend( ) iterators)

  For to show the utility of this, imagine a large unordered file with the
information about the employees of a big company. You have indexes
implemented with multimaps, with pairs [value, position], and use the
upper_bound and lower_bound functions. You need to select the employees in
a range of age and weight. With the boost:multimap you can know the number
of elements of the selection.

 In the weight query we found 100 elements and in the age query 10000
elements. To travel the elements of the weight query asking for the age, is
faster than the opposite.

*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.

   *COUNTERTREE + SUBALLOCATOR*

The join of the two ideas provide us data structures with a suballocator
built-in. They are, in the namespace cntree, the vector_tree_pool,
set_pool, multiset_pool,map_pool and multimap_pool, with identical
interface than the STL classes but better performance.

   Tray it. It fast, useful and easy to understand and use,. They are the
STL classes with a few additional functions.

 I had checked this code with GCC 4.6 (32 and 64) , CLANG/LLVM 3.0 and
Visual Studio 1010 (32 and 64).

If you find any error or problem in the code , the documentation or in any
other part ( as friendly do Mr Rene Rivera in the first version). Please
mail me ( fjtapia_at_[hidden]) or if you mail Boost, please insert
[countertree] in the head of the message. Some days I have not time to read
all messages arrived to my mail, but if I see that I detect and respond
first.

 If you have some idea, or have any comment, please mail me, always two
legs run more than only one in the pursuit of the goal, to be useful to the
community of programmers in the same way than our predecessors had been
useful to us.

 Sincerely yours

  Francisco Tapia

 fjtapia_at_[hidden]