Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-11 04:59:53

W dniu 2011-03-10 20:26, Bruno Lalande napisal(a):
>
>
>     Most people do not understand what the performance penalty of
>     virtual functions is.  The indirection through the vtable is
>     actually a minimal performance penalty and not very important.  The
>     significant performance penalty is that the compiler cannot inline
>     virtual function calls unless it knows at compile time the exact
>     type of the object.  Normally that is not the case, so the compiler
>     will not inline your virtual function calls.  If you are traversing
>     a tree and every hop from node to node requires one or more virtual
>     function call that is not inlined then your function call overhead
>     may dominate your runtime.  Using another way of achieving the same
>     thing (like a union) puts a branch and two non-virtual function
>     calls into your code instead of one virtual function call.
>
>
> I generally agree, thanks for the reminder about the cost of not being
> able to inline a virtual function, I had almost forgotten that aspect of
> things :-)
>
> Boost.Variant presents itself as a sort of class-ready union. I agree
> with that, since I remember having successfully migrated a design from
> unions to variants when it came to make those unions able to be
> std::string's. I was very happy with that library at the moment. The
> only thing that worries me here is the size of the objects, surprisingly
> it doesn't seem to be simply the size of the biggest object it can
> hold... I have to check again though. We should dig in that direction,
> it can give good results.

Yes you're right, variants should be used in this case. We may use 
variant storing vector of children nodes and vector of values or we may 
write our own (it isn't much more work) and use some value which 
normally would be passed in traversing to distinguish between different 
types of nodes. We may e.g. use levels (if they're really needed). If 
level is 0, the node is a leaf.

>
>     Parent pointers usually are not needed in a tree because the parent
>     is stored in the stack, but some algorithms do require them if nodes
>     are reachable other than through traversal from the root.
>
>
> That's a point I wanted to discuss too, but I figured we could discuss
> it later. It is very likely that the nodes of this type of tree are only
> reached via traversal, but this has to be checked.

In the current implementation it's often used. But it's highly probable 
that storing it isn't required. Algorithms uses currently available 
interface. If we change the interface we'll have to rewrite algorithms. 
Maby we should write the spatial index from scratch? With new data 
representation and algorithms adapted to it.

Btw, usually people use pointers to nodes, they're not storing nodes. 
Have you seen this kind of rtree implementation? Or strictly r*tree.

Regards,
Adam