Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-03-10 13:29:19

Adam Wulkiewicz wrote:
> W dniu 2011-03-10 10:56, Bruno Lalande napisal(a):
>> So the question is: is there anything in a leaf that's not in a node?
>> For instance, can both a node and a leaf store values? Or is it just
>> leaves? 
> 
> Only leafs operates on values and only internal nodes operates on
> nodes. There is no problem with it. The problem is with references to
> other nodes. std::vectors can allocate memory somewhere else so the
> rtree should probably be redesigned.
> 
>> One idea, although it's more work: I was wondering if we couldn't
>> implement both, and then test them on a few complicated cases to see
>> what it gives in terms of performance and memory. Would be very
>> instructive, I think.
> 
> Moving to visitors shouldn't take long. The only one improvement is a
> lot smaller vtables for nodes. We have a lot of virtual functions
> pointers we could get rid of but I don't know if it will give us a big
> performance change.

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.  The compiler is able to inline those non-virtual function calls and branch prediction probably eliminates most of the cost of the branch, which is equivalent to the cost of vtable indirection, which is also predicted.  You can generally 
rewrite function recusrive tree traversal algorithms as a loop by maintining your own stack and eliminate function call overhead entirely.  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.

I'm not trying to say what you should choose do, just providing information.

Regards,
Luke