Boost logo

Geometry :

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?


Geometry list run by mateusz at