Geometry Boost List: [ggl] spatial index - structure

Subject: [ggl] spatial index - structure
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-05-11 20:34:30

Adam Wulkiewicz wrote:
> W dniu 2011-05-09 16:21, Bruno Lalande napisal(a):
>> Inserting were faster in gcc 3.3s instead of 3.6s and searching in
>> vs 1.7s instead of 2.0s.
>>
>>
>> Did you make sure to always compile with the -03 option?
>
> It was compiled with -O2 in G++, and full optimization (/0x) in VS. When
> I finish 'clean' version of polymorphic nodes I'll perform more tests
> with various compilers options.

I found out that implementation of both solutions requires small changes 
which causes different code to be generated so I didn't implement a 
version which works for both cases. Instead, I tested additional 
visitors implementations, i.e. which stores the result as a class 
attribute. E.g. if the result of is_leaf is a class attribute instead of 
returned by a function the times of inserting are greater.

VS  : Full optimization /Ox, Inline any suitable
g++ : O3

I've marked tests as follows:
compiler | node implementation | version

compiler:
VS - VS2010
GCC - g++ 4.5.2

node:
empty - Boost.Variant nodes
P - polymorphic nodes

version:
m - is_leaf result returned by method
a - is_leaf result returned as class attribute

e.g. VSm - VS2010 compiler, Boost.Variant, result returned by method

M:8 m:4
            VSm   VSa   VSPm  VSPa  GCCm  GCCa GCCPm GCCPa
ins 1M   : 3.03  3.14  3.23  3.23  2.77  2.77 2.79  2.86
sea 100k : 5.70  5.70  5.70  5.70  5.93  5.93 5.82  5.79
rem 500k : 10.46 10.52 10.46 10.50 12.97 13.0 12.65 12.70
sea 100k : 1.77  1.77  1.77  1.76  2.00  1.99 1.94  1.93
ins 500k : 1.68  1.74  1.78  1.79  1.54  1.55 1.56  1.58
sea 100k : 3.02  3.02  3.02  3.01  3.22  3.24 3.17  3.14

M:32 m:8
            VSm  VSa VSPm VSPa  GCCm GCCa GCCPm GCCPa
ins 1M   : 3.56 3.67 3.70 3.72 3.27 3.27 3.27  3.32
sea 100k : 1.84 1.84 1.83 1.83 2.12 2.12 2.02  2.02
rem 500k : 4.17 4.20 4.20 4.20 4.20 4.20 4.12  4.12
sea 100k : 0.51 0.51 0.51 0.51 0.68 0.68 0.64  0.64
ins 500k : 1.91 1.97 1.99 2.00 1.75 1.75 1.75  1.78
sea 100k : 0.85 0.85 0.85 0.85 1.15 1.15 1.10  1.10

Boost.Variant in relation to polymorphic nodes:

for VS:
Inserting times: faster
Searching times: equal/slightly slower(bigger nodes)
Removing times:  slightly faster(small nodes)/slightly slower(big nodes)

for GCC
Inserting times: faster/equal(bigger nodes)
Searching times: slower
Removing times:  slower

In addition to this, if Boost.Variant is used I'll leave 'm' version 
only. It's most probable that in the case of polymorphic nodes, version 
'Pa' will be used because there is a problem with implementation of 
various visitors with the same parameters applied to the same visitable. 
In this case I'll change Boost.Variant 'm' version which is used 
currently to 'a' and release both.

What do you think? I guess it's better to switch to polymorphic nodes. 
One will search more frequently.

Regards,
Adam