Boost logo

Geometry :

Subject: [ggl] spacial index construction interface
From: Bruno Lalande (bruno.lalande)
Date: 2011-03-10 14:26:47

> 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.

> 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.

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at