Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Barend Gehrels (barend)
Date: 2011-03-09 13:50:09

Gum

On 9-3-2011 15:51, Bruno Lalande wrote:
> Hi,
>
>
>     The current implementation of the spatial index is, if I'm right,
>     full of virtual functions and shared ptr's, which I would like to
>     limit to the minimum... If possible, of course.
>
>
> I see your point. A quick glance at the source code indeed shows a few 
> things that should not be there. The fact of using a shared_ptr to 
> manage tree elements is probably not the most efficient way to do, for 
> instance. I would say shared_ptr is more for high level code. At low 
> level within a library, performance should be the priority. Virtual 
> functions like is_leaf must go away as well (as discussed).
>
> That said, we must keep in mind that such a tree cannot be obtained 
> only by compile-time techniques, since it is dynamic. If STL or Boost 
> don't use much dynamic polymorphism, it is simply because they are all 
> about adapting some metalibrary to a client code at compile-time. 
> Here, we are talking about the guts of a machine. If the guts in 
> question take input only at run-time, obviously they will use run-time 
> techniques. Even a book like "C++ Template Meta-programming", which is 
> almost all about compile-time computations, talks about and uses 
> virtuality when it comes to "cross the run-time boundary" (see "Type 
> Erasure"). And the few Boost library which are more about applicative 
> tasks than library writing tools definitely use dynamic polymorphism 
> (e.g. Filesystem, Format, Wave, Serialization, ProgramOptions...) and 
> dynamic memory allocation (e.g. Iostream, DateTime...).
>
> So to summarize: we should avoid confusing interaction between library 
> and client code (which typically involves compile-time techniques), 
> and core guts implementation (which possibly involves a lot of runtime 
> stuff).

Thanks for all input.

Just as a clarification, I completely understand why the current 
implementation contains both virtual functions and shared ptrs, they are 
related. Because there are either nodes or leaves, and their behaviour 
is different, there are virtual fuctions designed, as the normal 
classical OO design, and because of that they must be contained into 
shared pointers inside a vector. Otherwise it won't work. And because of 
that, there are many of those shared pointers. Which is probably the 
largest bottle-neck in performance (much larger than the virtual 
functions, I assume).

So probably the key is first to avoid those shared pointers. That can be 
done by using one of the designs Adam and Bruno pointed out, specificly 
option 3 from Adam ("No virtuals. Unused data"), also favoured by Bruno 
(if I'm right). Because there is then only one object left, it can be 
stored inside a vector without falling back to dynamic memory. So a 
"std::vector<node> leaf;" (instead of a std::vector<node_ptr> leafs - 
I'm referring to Adam's examples now). I think this is already a step 
forwards.

I thought just to summarize this again, because it is not only about 
virtuality but more about the consequences, a shared ptr for indexed 
element, which must be avoided.

Then Bruno decribed the visitors, does that agree or disagree what I 
described here? Can they be applied in this design or should it be 
adapted therefore?

Regards, Barend

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