Geometry Boost List: [ggl] spacial index

Subject: [ggl] spacial index
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-04-30 16:57:41

Simonson, Lucanus J wrote:
> Adam Wulkiewicz wrote:
>> 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.
>
> You can rewrite recursion as a loop and maintain your own stack data structure in an array.

I've implemented the same creation algorithm that is used in the old 
tree and the results are a lot better.

max:8 min:4
old creation: 8.0s
old search:   3.4s
old size:     47MB
new creation: 3.0s
new search:   3.4s
new size:     42MB

max:10 min:3
old creation: 8.1s
old search:   1.5s
old size:     43MB
new creation: 3.1s
new search:   1.5s
new size:     44MB

max:20 min:6
old creation: 7.7s
old search:   1.6s
old size:     33MB
new creation: 3.2s
new search:   1.7s
new size:     39MB

max:32 min:8
old creation: 8.3s
old search:   1.8s
old size:     31MB
new creation: 3.5s
new search:   1.7s
new size:     37MB

New nodes are smaller than the old ones. They contains a vector of 
pointers or values and variant's id. Old ones contains vector, pointer 
to parent and level's number. Leaf nodes contains also additional 
vector. Moreover shared_ptrs are used so there are references counters. 
Size of the new rtree is bigger probably because I don't delete splited 
nodes. I just clear elements vector for source node and use it as the 
first node, so the memory is still allocated.

As you can see, times are more than 2 times smaller.

Thanks Lucanus that you remembered me about this technique. I'll give it 
a try.

Regards,
Adam