Geometry Boost List: [ggl] spacial index

Subject: [ggl] spacial index
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-05-04 07:31:49

Adam Wulkiewicz wrote:
> 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.

Of course instead of using some condition there might be a virtual 
function which casts base class object to the derived class object, e.g. 
visitor pattern used as you mentioned before. But one should have to 
remember to implement functions carefully, not use dynamic polimorphism, 
not use any other virtual function (e.g. only the recursively called 
ones) and implement the rest of the algorithms as e.g. compile-time 
templates. Probably only 3 virtual functions are needed - insert, remove 
and is_leaf. So instead of switch-case with cast from Boost.Variant 
there could be a virtual call with cast from visitor pattern which 
couldn't be optimized in the case of not recursive call (e.g. when 
is_leaf is needed) but it is not that bad I guess. To compare both 
designs one should implement another tree.

Regards,
Adam