Subject: Re: [boost] Review Wizard Report for November 2012
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-11-16 01:59:55
Hi , Ron
I send you a copy of the message.
I supouse I will have time for the two thinks and . I will examine the
projects for review in order to be reviewer of someone
I would like to request a formal review of the library Countertree +
Project location ( zip file with code and documentation) :
Quick view of documentation with code download :
For the people who don't know this project, this is a description :
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)
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
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
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
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
2012/11/16 Ronald Garcia <rxg_at_[hidden]>
> Hello Francisco,
> Thank you for your note. Could you forward me a copy of the October 3
> note, because I do not have a copy.
> Also, I cannot estimate the time when the review will happen. You will
> need to find a review manager first and then schedule the review, so the
> time until the review could vary greatly. Ultimately it is up to you
> whether you would like to continue working or prepare for review now.
> On Nov 14, 2012, at 3:02 PM, Francisco José Tapia wrote:
> > Hi Ronald
> > The 3 of October I sent a message requesting the Formal Review of the
> > library Countertree. I don't know if this is sufficient for to request a
> > Formal Review. If not, please, say me, in order to to do it.
> > That message contains a brief description of the project. The code and
> > documentation are located in my dropbox, because when I had lost the
> > password of the vault. But if it is necessary I will put there.
> > Project location ( zip file with code and documentation) :
> > https://dl.dropbox.com/u/8437476/works/countertree_code_doc.zip
> > Online documentation with code download :
> > https://dl.dropbox.com/u/8437476/works/countertree/index.html
> > I would know if you have any time estimation about the beginning of the
> > review. I ask you because, in the Countertree library the logical
> > is the concurrent version. This is important because many libraries like
> > the Threading Building Blocks have concurrent data structures, but don't
> > have concurrent data structures based on trees ( set, multiset, map and
> > multimap), due to the difficulty of to distribute the elements stored
> > between an arbitrary number of threads. With the countertree is easy
> > because you can use like a vector.
> > Depending of the time estimation, if close, I will do more quietly and I
> > can be a reviewer of some library, if not I will tray to finish the
> > concurrent part for the review.
> > Regards
> > Francisco Tapia
> > 2012/11/12 Ronald Garcia <rxg_at_[hidden]>
> >> Thank you for catching that Chris.
> >> Best,
> >> Ron
> >> On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
> >>> <snip>
> >>>> The following libraries have been accepted to Boost, but have not yet
> >>>> been submitted to SVN:
> >>> <snip>
> >>> There's Multiprecision as well, unless I missed it in the list.
> >>> Thank you for the excellent update!
> >>> Best regards, Chris.
> >>> <snip>
> >>> _______________________________________________
> >>> Unsubscribe & other changes:
> >> http://lists.boost.org/mailman/listinfo.cgi/boost
> >> _______________________________________________
> >> Unsubscribe & other changes:
> >> http://lists.boost.org/mailman/listinfo.cgi/boost
> > _______________________________________________
> > Unsubscribe & other changes:
> Unsubscribe & other changes:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk