Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-09 14:45:51

Barend Gehrels wrote:
> 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?

Sorry, I didn't read this email before. IMO shared_ptrs was used because 
they handle objects destruction safetly. Previous design is simple and 
readable.

To avoid shared_ptrs we may just use simple pointers and delete objects 
ourselves.

I have this 3rd option in mind. std::vector on GCC has 12B (3 pointers). 
If we consider current node hierarchy. node must have virtual destructor 
and at least one virtual accept(visitor&) method. This gives us 2 
pointers so we waste only one pointer in the case where unused vector is 
stored. But there is no single one virtual function. What is more, we 
musn't use pointers, just store nodes inside std::vectors and that's it!

We have another option - the previous structure:

node {
   vector<node_ptr> m_nodes
   node_ptr parent;
};

leaf : node
{
   vector<value> m_values;
};

In this case, we waste this 1 pointer in leaves only but we must convert 
from node_ptrs to leaf_ptrs (if there are no node_ptrs inside m_nodes, 
node is a leaf and may be converted) which may be dangerous and still we 
have to create and destroy nodes ourselves.

Regards,
Adam