Thanks Ron. I am sorry because I didn't thought about the resume of the project. It's too long, it's like a novel ! I will write a short description and I will send you in a few days. Thanks Francisco 2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
Thanks Francisco. I have added Countertree to the review schedule.
Best, Ron
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
Thanks
Francisco
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@gmail.com
2012/11/16 Ronald Garcia <rxg@cs.cmu.edu>
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.
Best, Ron
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 the 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 expansion 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@cs.cmu.edu>
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: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ 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: http://lists.boost.org/mailman/listinfo.cgi/boost