[boost] [countertree] Formal Review Request

Subject: [boost] [countertree] Formal Review Request
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-10-03 16:23:05

Hi all,
I would like to request a formal review of the library “Countertree +
Suballocator” [countertree]

Project location ( zip file with code and documentation) :
https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip

Quick view of documentation with code download :
https://dl.dropbox.com/u/8437476/works/countertree/index.html

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 . Based on this tree we have :

   - With unordered information we have vectors (countertree::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 countertree 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*

 In the allocation of equal size elements ( as in STL list, set,
multiset,map and multimap), when the number of elements grows, many
allocators begin to have speed problems. For to improve the speed, many
allocators request to the Operating System big chucks of memory ( pool
allocators). 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 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. The suballocator replace to the
allocator in the allocation of equal size elements

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*)*
b) *Return the suballocator return memory to the allocator, this can use in
the allocation of others types of data or for return to the *Operating
System, decreasing the memory used by the program, *( as you can see in the
*Suballocator 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 countertree, the vector_tree_pool,
set_pool, multiset_pool,map_pool and multimap_pool, with identical
interface than the STL classes but better performance for big number of
elements

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

This library is designed thinking in programmers with a basic knowledge of
C++. As I say in the documentation, if you know the STL classes vector, set
, multiset, map , multimap and allocator, you know more than 95% needed for
to use this library.

 I showed the library to several friends and colleagues, and one of them
said me “If your potential users are not experts, and they need more than 5
minutes to understand what's the goal of the library and what they can do
with it, many of them leave the page.... , and the library”.

 The first page of the documentation explain the library, the reasons and
what can do. And in the next pages show the details and how can do in a a
easy way.

 I had checked this code with GCC 4.7 , CLANG/LLVM 3.0 and Visual C++ 10 (
all with 32 and 64bits.). In code of the project is composed by the code of
the classes, the test programs, the benchmarks programs used and mentioned
in the documentation, and several examples of the code

I had checked all the requirements for to request the review. But I am not
sure if all is OK. If you miss something or something is wrong , please ,
mail me and I will correct as soon as possible

 Sincerely yours

Francisco Tapia

fjtapia_at_[hidden]