Geometry Boost List: [ggl] spacial index

Subject: [ggl] spacial index
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-04-28 09:57:35

Adam Wulkiewicz wrote:
>> Interesting, I'm curious about the result... I was suspecting memory
>> consumption problems with the new model, but certainly not performance
>> regressions. Probably we'll have to dig to know where they come from
>> exactly (hope you have an easy way to switch implementations).
>
> I've eliminated the error by disabling reinsertions for now.
>
> Test programs were compiled using VS2010. For 1000000 boxes with random
> position [-1000000, 1000000] and size 1 and 100000 searches results are
> as follows:
>
> For min:4 max:8
> old creation: 8.0s
> old search: 3.4s
> old size: 47MB
> new creation: 6.7s
> new search: 7.1s
> new size: 49MB
>
> For min:3 max:10
> old creation: 8.1s
> old search: 1.5s
> old size: 43MB
> new creation: 9.4s
> new search: 5.6s
> new size: 66MB
>
> For min:6 max:20
> old creation: 7.8s
> old search: 1.6s
> old size: 37MB
> new creation: 21.5s
> new search: 38.0s
> new size: 46MB
>
> For min:8 max:32
> old creation: 8.3s
> old search: 1.8s
> old size: 31MB
> new creation: 48.9s
> new search: 132.8s
> new size: 44MB
>
> Maby I should implement the same algorithm (linear split?) and then
> perform tests. Or create old rtree, fill the new one with data from the
> old one and then test search speed.

Ok, I've created structure using old rtree, load it in the new one and 
measure times. Again for 1M random boxes of size 1 and 100k searches 
with boxes of size 20:

min:4 max:8
old search: 3.57s
new search: 3.37s

min:8 max:32
old search: 1.89s
new search: 1.94s

min:16 max:64
old search: 1.54s
new search: 1.52s

Times looks reasonable this time so i guess r*tree is not created correctly.

Search times are close to the old ones because compiler won't inline 
run-time recursive call. In the old search function there is virtual 
function call. In the new function there is regular call, but there is 
additional switch-case inside variant's apply_visitor and copying of 
std::pair<Box, size_t> instead of just size_t.

The creation routine should speed up because many functions may be 
inlined in one traversing step but this may be verified only for the 
same algorithm. So I guess I'll implement linear split and check times 
again. Then if things looks promising I'll search for the error in 
r*tree. Or maby you have better idea?

Regards,
Adam