Subject: Re: [boost] Review Wizard Report for November 2012
From: Ronald Garcia (rxg_at_[hidden])
Date: 2012-11-16 17:21:32
Thanks Francisco. I have added Countertree to the review schedule.
On Nov 15, 2012, at 10:59 PM, Francisco José Tapia wrote:
> 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
> Hi all,
> I would like to request a formal review of the library Countertree +
> Suballocator [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
> 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
> 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) :
>>> Online documentation with code download :
>>> 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.
>>> Francisco Tapia
>>> 2012/11/12 Ronald Garcia <rxg_at_[hidden]>
>>>> Thank you for catching that Chris.
>>>> On Nov 11, 2012, at 12:13 PM, Christopher Kormanyos wrote:
>>>>>> The following libraries have been accepted to Boost, but have not yet
>>>>>> been submitted to SVN:
>>>>> There's Multiprecision as well, unless I missed it in the list.
>>>>> Thank you for the excellent update!
>>>>> Best regards, Chris.
>>>>> Unsubscribe & other changes:
>>>> Unsubscribe & other changes:
>>> Unsubscribe & other changes:
>> Unsubscribe & other changes:
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk