Boost logo

Geometry :

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


Geometry list run by mateusz at loskot.net