[boost] [COUNTERTREE + SUBALLOCATOR ] New Version

Subject: [boost] [COUNTERTREE + SUBALLOCATOR ] New Version
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-06-05 15:11:19

Hi

this message is to announce the new version of the [countertree +
suballocator] library. You can find in
(http://dl.dropbox.com/u/8437476/works/countertree/index.html)<http://dl.dropbox.com/u/8437476/works/countertree/index.html>

When I was writing the document explaining the allocator's algorithm. I
reexamined my code , and It run well and have an easy interface , but the
internal design was obscure and difficult to understand. Due this, I
decided redesign it in order to make it clear and easy to understand.

I changed too the version of the GCC compiler form the 4.6 to 4.7, and the
machine used for the benchmarks. My old computer, where I developed the
code, had a good cache but a bad bus memory (Single channel 533Mz), and
this introduce a distortion in the comparison of some algorithms. The new
machine is a QuadCore with 8M of cache and 8G dual channel 1066 MHz. The
results obtained are more similar to the obtained in a modern machine.

I added a new point to the documentation explaining the additional features
of the countertree set, multiset, map and multimap with two examples. You
can find in (
http://dl.dropbox.com/u/8437476/works/countertree/ordered.html#functionality)

For the people who don't know this project, this is a description :

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

*SUBALLOCATOR*

The allocator is the data structure defined in the STL, as interface
between the data structures and the memory provided by the Operating System
(O.S.). The allocator manages the memory received from the Operating
System, and the memory requested in the allocate operations and the memory
returned in the deallocate operations.

To write an allocator for to manage a wide range of size elements and a big
number of elements (several millions) of each size in a fast way, it's a
very difficult task. When the number of elements grows, many allocators
begin to have speed problems.

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 . These allocators are named pool allocators.

If you have a small number of elements, you have a small problem, small
resources and small time operations. But, if you have several millions of
elements allocated, perhaps you are using several GB of memory. Running a
program with GB of memory don't used, because the allocator don't return
the memory request, is a great waste of resources.

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

If you use an allocator for the allocation of variable size elements, and a
pool allocator for the allocation of fixed size elements, this improve the
speed, but increase the memory consumption, which is the sum of the maximum
memory of the pool allocator and the memory used by the allocator. If the
pool allocator don't return to the Operating System the unused memory, this
can't be reused by the allocator.

The *suballocator is a solution to these problems*, and others memory
problems described in the suballocator page. The suballocator is a layer
between the allocator and the data structures, compatible with any
allocator with the STL definition. The suballocator request memory to the
allocator, and return to it when unused.

With the suballocator

a) *We have a very fast allocation* *(around 2 times faster than the
std::allocator of GCC 4.7, CLANG 3.0 and 3 times than Visual Studio 10 *See
details in the *Suballocator
Benchmark<http://dl.dropbox.com/u/8437476/works/countertree/suballocator.html#benchmark>
*)*
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, *( as you can see in the *Suballocator
Benchmark
<http://dl.dropbox.com/u/8437476/works/countertree/suballocator.html#benchmark>
*)*
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) Even the time of the allocation is a small part of the time spent in the
insertion in a std::set, the suballocator obtain time reductions over over
the 30% respect the std::allocator. The secret is the cache performance due
to the data locality improvement.

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