Geometry Boost List: [ggl] rtree index

Subject: [ggl] rtree index
From: Barend Gehrels (Barend.Gehrels)
Date: 2009-06-19 18:18:29

Hartmut Kaiser wrote:
>> My name is Federico J. Fernandez.
>>     
>
> Good to see you again, Federico!
>
>   
>> I worked in the rtree spatial index during 2008 Google Summer of Code.
>> I see that now my code is included in GGL. I'm really happy about that.
>>
>> I've been talking with Barend this days about improving the index,
>> focusing on performance optimization. So I have now some issues to
>> address and I would like to share them with the list to receive
>> suggestions.
>>
>> Let's start with the first. I use boost::shared_ptr<> in the tree nodes
>> to have pointers to the child nodes (in fact a std::vector of
>> children). Barend told me that this could have a very big performance
>> penalty so we want to replace them. I don't know what could I use to
>> have a similar behavior:
>>
>> - normal pointers (then I should take control of the memory management)
>> - some kind of local storage (the problem here is that I should replace
>> all the virtual functions that rely on pointers)
>> - other ideas ?
>>     
>
> boost::intrusive_ptr. The semantics are similar to shared_ptr, but they
> don't require a separate memory allocation to maintain the reference count. 
>
> But what you should probably ask yourself in the first place is whether you
> really need to share the pointers to the child nodes in the tree. If
> ownership of the child nodes is well defined (and that's usually the case in
> tree like structures) you normally don't need to keep reference counts. In
> this case simple wrapper objects a la boost::scoped_ptr are very handy.
>
>   

Agree, I don't think reference counting is necessary.

What I would like, but I don't know if possible, is that the node/leaf 
do not have virtual methods and no dynamic memory (other than std 
containers). But  first we have to be sure that this is really possible. 
I still didn't have a close look. It might mean that a leaf and a node 
are the same object (so the only difference is that they do / don't have 
children, but that is dynamic).

This will be a major change, but if possible, a major increase in 
performance.

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20090620/c3f84b5e/attachment.html