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