Re: [boost] [countertree] Formal Review Request

Subject: Re: [boost] [countertree] Formal Review Request
From: Luke Simonson (simoluk_at_[hidden])
Date: 2012-10-05 16:58:18

>  You can't sort by any parameter. I had the defects in a vector_tree, and
> divide the number of defects between the number or cores of the machine,
> assign to each core their defects and begin to process. The possibility of
> insert and delete in any position at log(N), was very useful. As you can
> imagine, the complexity was bigger than the described here, but I thing
> this is not place for to show a detailed specification of the project.

Interesting that we both have background in chip design.

So I surmise that you wanted to simulate equal probability that an
electron interact with a defect by generating a random index into your
countertree data structure holding defect elements.  It's not clear to
me why you needed to insert into the middle, however.  If you weren't
sorting by any parameter why not just push_back each new element onto
a vector?  Threading obviously brings in a lot of complexity, but I
don't see how the countertree solves any of those problems.  I could
implement fast lookup and randomized indexing into a set using a
std::vector and std::set that are cross referenced.  First randomly
select a vector index with equal then randomly select the set element
based upon is value and the distribution function.  When removing an
element from the set swap its vector element to the end and pop_back()
updaing set element index for the swapped end element.  Perhaps there
is some application where indexes needs to be ordered the same as the
set, which would then pretty much require countertree to be made
efficient.

>  About the statefull allocators. I have my own idea, but I need to study
> more in order to have a founded opinion. The suballocator can be
> transformed in statefull allocators with a few changes in the actual code,
> but I need to think about the utility and the problems related.

The list merge/split and thread safety/local being the two problems
that spring immediately to my mind.  It is because there are problems
that we need a library.

Regards,
Luke