Geometry Boost List: [ggl] spatial index - structure

Subject: [ggl] spatial index - structure
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-05-06 23:12:57

Adam Wulkiewicz wrote:
> W dniu 2011-05-02 14:46, Bruno Lalande napisal(a):
>> Hi Adam,
>
> 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.

I've implemented run-time visitor pattern. It wasn't that hard actually 
because data is separated from algorithms in the new implementation. I 
had to specialize nodes traits and add some templates but this is quick 
and dirty implementation so if we want to provide 'polymorphic' nodes 
along with the Boost.Variant ones it should be corrected. Nevertheless I 
was able to compare the same algorithms for two structures. In general, 
they takes the same amount of memory but Boost.Variant one is slightly 
faster. In polymorphic implementation there must be 2 virtual methods 
calls for each function, first one in visitor and second one in 
visitable. In Boost.Variant implementation there is switch-case and 
simple call if recursion is used or inlined function if not.

All tests are performed for the same data.

max:64 min:16
              POLY    VARIANT
insert 1M    4.483s  4.455s
search 100k  2.179s  2.155s
remove 500k  5.236s  5.242s
search 100k  0.607s  0.604s
insert 500k  2.352s  2.340s
search 100k  0.979s  0.972s
size         62MB    62MB

max:32 min:8
              POLY    VARIANT
insert 1M    3.658s  3.637s
search 100k  1.794s  1.767s
remove 500k  4.063s  4.087s
search 100k  0.495s  0.490s
insert 500k  1.961s  1.941s
search 100k  0.826s  0.821s
size         60MB    60MB

max:20 min:6
              POLY    VARIANT
insert 1M    3.296s  3.241s
search 100k  2.974s  2.949s
remove 500k  4.538s  4.568s
search 100k  1.041s  1.034s
insert 500k  1.789s  1.742s
search 100k  1.694s  1.685s
size         67MB    67MB

max:8 min:4
              POLY    VARIANT
insert 1M    3.187s  3.101s
search 100k  5.513s  5.439s
remove 500k  10.770s  10.174s
search 100k  1.701s  1.687s
insert 500k  1.743s  1.702s
search 100k  2.923s  2.895s
size         81MB    81MB

max:4 min:2
              POLY    VARIANT
insert 1M    4.055s  3.851s
search 100k  4.126s  4.079s
remove 500k  8.025s  8.104s
search 100k  1.216s  1.197s
insert 500k  2.334s  2.217s
search 100k  1.847s  1.824s
size         114MB    114MB

Interesting is that remove algorithm is generally faster in the case of 
polymorphic implementation.

So I think I'll stick with Boost.Variant. What do you think?

Regards,
Adam