Boost logo

Geometry :

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.


Geometry list run by mateusz at