Boost logo

Geometry :

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


Geometry list run by mateusz at loskot.net