Geometry Boost List: [ggl] spacial index

Subject: [ggl] spacial index
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-05-02 10:11:20

W dniu 2011-05-02 14:46, Bruno Lalande napisal(a):
> Hi Adam,
>
> Sorry for reacting a bit late on this. Actually I had troubles following
> your different tests and I'm still not sure what you actually tested. To
> my understanding the very first test you presented was comparing
> different things (different constructs/algorithms/operations) so was not
> relevant, only the subsequent ones are, right? But then a few
> implementation details came into the game, like memory management and
> traversal method. In the end, do we have an idea about whether or not
> the Boost.Variant tree VS the dynamically polymorphic tree was a
> improvement? I.e. do we have a test that really isolates this factor,
> without changing the other ones?

In the latest tests I've compared creation and search algorithms of two 
implementations. First is the rtree which is currently in the 'official' 
Boost.Geometry. Second is the new one based on Boost.Variant.

I just realized that recent better times are the result of slightly 
different tree creation algorithm (e.g. x axis is prefered, y were in 
the old one). Previous emails contains times for the same trees, only 
the last one (different search algorithms) are preformed for different 
tree than before. But the test was about comparing search algorithms not 
the old and the new implementation.

Searching algorithm is exactly the same as the old one. The times of 
both implementations are close. New one is slightly better but still 
there are recursive calls so the compiler won't inline it. See previous 
emails. I've tried to use my own stack and the results are described in 
the the latest email. Sometimes better sometimes worse.

I may check different searching algorithms implementations for exactly 
the same trees to confront it with the old algorithm but I don't know if 
it's necessary.

There are of course differences in nodes structures. In the old 
implementation there is a hierarchy of base and derived class. Pointer 
to parent is stored as well as level. New implementation uses just 
vectors of elements.

This leads to differences in the creation algorithm but in the key parts 
it is the same. Algorithm choosing next node in the traversing step is 
the same as well as algorithm redistributing elements when split occurs. 
There is a little differences in the creation algorithm flow.

In the old implementation there is a lot of virtual methods that done 
varius things(no visitor pattern used). First the recursive function 
choose_leaf is called. It traverses the tree recursively in order to 
find leaf node which will contain the new value. Then recursive function 
adjust_tree is called it iterates through parent nodes 'backwards' from 
the leaf and splits nodes if necessary. Split is done by creating 2 new 
nodes and placing elements in them. Then original node is deleted. 
Moreover std::shared_ptrs are used to store nodes pointers.

In the new implementation all is implemented in one recursive function. 
First next node is choosen (a part of choose_leaf) then recursive call 
an then split if necessary so the algorithm behaves the same way.

I of course done some optimizations. E.g. I don't calculate bounding 
boxes of groups of elements each time I'm adding new element into the 
group. I store results of functions rather than calculate them over and 
over etc.

There is only one recursively called function for insert algorithm. The 
rest of the algorithm may be inlined/optimized by the compiler. There 
are just regular functions, no virtual function calls for each small thing.

The old tree structure could be rewritten in the same way. Somwhere 
should be a condition checking if node is a leaf or internal node, then 
cast to proper type and then regular functions. So we would have 
something like boost::variant but instead of switch-case there will be 
virtual function call.

I don't know if full comparision of new and old implementation is 
possible but the new one is more than 2x faster in the creation step.

Regards,
Adam