Subject: Re: [boost] Review Wizard Report for November 2012 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
Among other things, countertree would allow the boost Statistical Accumulators Library to support rolling median and rolling quantiles efficiently. This would be very useful. I had previously had to hack the tree class in the Policy-Based Data Structures part of the gnu c++ library. (see http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_order_statistics_node...) Leo Goodstadt
On Sat, Nov 17, 2012 at 4:25 AM, Leo Goodstadt <leo.goodstadt@llew.org.uk>wrote:
Subject: Re: [boost] Review Wizard Report for November 2012 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
Among other things, countertree would allow the boost Statistical Accumulators Library to support rolling median and rolling quantiles efficiently. This would be very useful.
I had previously had to hack the tree class in the Policy-Based Data Structures part of the gnu c++ library. (see
http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_order_statistics_node... )
As far as I know, this support is not yet available in countertree project, although this is possible in principle. Do you have a document with descriptions of your work and/or sample code? Regards, Vadim Stadnik
About the compatibility with the boost Statistical Accumulators Library, I didn't thought about it, but it would be useful. I will try to implement, but I need to examine in deep for to provide you a well founded opinion. About the Policy-Based Data Structures of GCC, I didn't know, but I had learned many things reading the code and the documentation of GCC, and I hope to learn more with them. I say you the same, I will examine in order to provide you a founded opinion. About the question of sample code. If you see the online documentation. ( https://dl.dropbox.com/u/8437476/works/countertree/index.html). The last point is the Download. It's a zip file. If you examine this file, you have a example folder with examples of all the data structures, and a benchmark folder with the benchmarks used for the documentation. Don't worry, it's easy. For to use this library only need to know the basic of the STL. You will understand all at first look. It is easy to learn and use. And if you have any question, please ask me Thanks by your interest and your suggestions. Francisco 2012/11/16 Vadim Stadnik <vadimstdk@gmail.com>
On Sat, Nov 17, 2012 at 4:25 AM, Leo Goodstadt <leo.goodstadt@llew.org.uk
wrote:
Subject: Re: [boost] Review Wizard Report for November 2012 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
Among other things, countertree would allow the boost Statistical Accumulators Library to support rolling median and rolling quantiles efficiently. This would be very useful.
I had previously had to hack the tree class in the Policy-Based Data Structures part of the gnu c++ library. (see
http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_order_statistics_node...
)
As far as I know, this support is not yet available in countertree project, although this is possible in principle. Do you have a document with descriptions of your work and/or sample code?
Regards, Vadim Stadnik
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Le 17/11/12 18:44, Francisco José Tapia a écrit :
About the compatibility with the boost Statistical Accumulators Library, I didn't thought about it, but it would be useful. I will try to implement, but I need to examine in deep for to provide you a well founded opinion.
About the Policy-Based Data Structures of GCC, I didn't know, but I had learned many things reading the code and the documentation of GCC, and I hope to learn more with them. I say you the same, I will examine in order to provide you a founded opinion.
About the question of sample code.
If you see the online documentation. ( https://dl.dropbox.com/u/8437476/works/countertree/index.html). The last point is the Download. It's a zip file. If you examine this file, you have a example folder with examples of all the data structures, and a benchmark folder with the benchmarks used for the documentation.
Please don't top post on this ML. I have taken a look at the performances on https://dl.dropbox.com/u/8437476/works/countertree/doc/ordered.html#benchmar.... From the figures it seems that the counter tree implementation has worst performances that the std:: when no allocator is used. I'm wondering if the figures for the std:: containers are using a specific allocator? If not, it will be a good idea to add them also, so that the comparison are fair. Best, Vicente
Hi Vicente, As you comment in the message, with the same allocator the countertree based data structures have worst performance than the STL data structures. The difference depends of the compiler. The countertree algorithms had been designed by me because I can't use the traditional algorithms ( described in Introduction to Algorithms), because with the counters, it was too complex. And I decided to design new algorithms based on the definition of Tree234. Internally, it must work with the pointers, like the STL data structures, and with the counters. And when you insert a node , you must increment all the counters from the node where go to be inserted, to the root of the tree, and this is the devil of the performance. Because many nodes in the path to the root node, are not in the cache. I have on paper a full redesign of the algorithms in order to improve the speed, but until I implement it, I don't know exactly the improvement. The access by position provide you additional features as to know the number of elements in a upper_bound, lower_bound search because you can know the position of each iterator. But the main utility is in a concurrent data structure. If you examine the Threading Building Blocks library, you can see many concurrent data structures. But don't have concurrent data structures based on trees. I suppose due to the difficult of assign the elements stored in the data structure to an arbitrary number of threads. With the countertree is easy, because you can use like a vector. You assign to the thread an iterator to the first element of the range, and a number of elements, and the thread can read, insert and delete in the range independently of the others threads. I am implementing this now, but I don't know if I could finish before the acceptance process. In the library , I have designed too the countertree data structures with the suballocator incorporate, which are the set_pool, map_pool..... In the benchmarks of the sorted elements https://dl.dropbox.com/u/8437476/works/countertree/doc/ordered.html#benchmar.... You can see the comparison between the stl set and multiset, countertree set and multiset, and the set_pool and multiset_pool In the benchmarks of the suballocator page, you have the test with the stl set and several suballocators https://dl.dropbox.com/u/8437476/works/countertree/doc/suballocator.html#ben... The suballocator is a layer over ANY allocator, and improve the speed and the memory management ( the memory unused is returned to the allocator and decrease the memory used by the program ) With the STL data structures the speed improvement in the GCC and CLANG compiler is around 30% , and with the Visual C++ 10 is around 15%. I didn't wrote more test in the documentation, because if each data structure have two graphs ( performance and memory), and I use 3 compilers (recently I had the test with the fourth compiler Intel 13 ), the number of graphs can be excessive Thanks by your interest. Francisco 2012/11/17 Vicente J. Botet Escriba <vicente.botet@wanadoo.fr>
Le 17/11/12 18:44, Francisco José Tapia a écrit :
About the compatibility with the boost Statistical Accumulators Library, I
didn't thought about it, but it would be useful. I will try to implement, but I need to examine in deep for to provide you a well founded opinion.
About the Policy-Based Data Structures of GCC, I didn't know, but I had learned many things reading the code and the documentation of GCC, and I hope to learn more with them. I say you the same, I will examine in order to provide you a founded opinion.
About the question of sample code.
If you see the online documentation. ( https://dl.dropbox.com/u/**8437476/works/countertree/**index.html<https://dl.dropbox.com/u/8437476/works/countertree/index.html>). The last point is the Download. It's a zip file. If you examine this file, you have a example folder with examples of all the data structures, and a benchmark folder with the benchmarks used for the documentation.
Please don't top post on this ML.
I have taken a look at the performances on https://dl.dropbox.com/u/** 8437476/works/countertree/doc/**ordered.html#benchmarks<https://dl.dropbox.com/u/8437476/works/countertree/doc/ordered.html#benchmarks>.
From the figures it seems that the counter tree implementation has worst performances that the std:: when no allocator is used. I'm wondering if the figures for the std:: containers are using a specific allocator? If not, it will be a good idea to add them also, so that the comparison are fair.
Best, Vicente
______________________________**_________________ Unsubscribe & other changes: http://lists.boost.org/** mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>
participants (4)
-
Francisco José Tapia -
Leo Goodstadt -
Vadim Stadnik -
Vicente J. Botet Escriba