Re: [boost] Countertree

Subject: Re: [boost] Countertree
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2012-11-17 14:55:40

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#benchmarks.
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#benchmark

 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_at_[hidden]>

> 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#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>
>