Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2010-08-17 12:14:11

Adam Wulkiewicz wrote:
> I have a few possible solutions in mind:
> 
> 1. nodes' structure,
> 
> a) store nodes in a std::vector and inside nodes store indexes of left
> and right child,
> b) store nodes in a std::list and store pointers/iterators (or maby
> use intrusive std::list),
> c) create the structure by my own,
> 
> 2. nodes,
> 
> a) store vectors of objects(IDs, ptrs) in all nodes - there will be
> empty containers inside the internal nodes,
> b) store pointers to vectors and create them in runtime,
> c) store lists of objects in all nodes - slower than vectors?,
> d) implement simple container defined by 2 values e.g. pointers to the
> beginning and the end or number of elements,
> e) store only internal nodes in the structure and store pointers to
> leafs inside them (vectors only in leafs),
> f) use run-time polimorphism - this may be only used with 1c.
> 
> I don't know which one is the best. I'd like to avoid 1c, 2f and
> everything that requires using allocator by my own.
> 
> Memory allocation (pointers) could be implemented as 1-element std
> lists. 
> 
> I'd rather use 1a and 2b (2e eventually but it's more complicated).
> Although, this means that there would be e.g. vector of nodes
> containing 1-element lists of vectors. What do you think?

If we provide an iterator semantic for the interface of the tree it is very important to decide if the iterators are invalidated by operations that modify the tree (like push_back on a vector invalidates iterators) or not (like insert in a map does not invalidate iterators.)  Using vectors in the leaves implies that iterators to the vector elements cannot be used in data structures returned by our interface if we are to avoid invalidating them.  If you plan to bound the size of the vector in the leaves you should use a boost array instead.

I'd rather not see 1-element std lists used as a way to access the std allocator.  You can directly use the std allocator to allocate an object of type T.  There are interesting things you could do with std containers to implement rudimentary garbage collection or memory pools, but that should not be neccesary.  It would be better to reuse existing boost libraries such as the memory pools library and parameterize the containers to allow the user to specify the allocator.  Allocators are a very important issue in spacial indexes.  A memory pooling allocator is a very imporatant optimization because it both improves the locality of reference of tree nodes and reduces the negative impact of cache churn due to node lookup that can slow down the rest of the application.  Also, the choice of stateful allocator which can have a separate lock for each thread (or lock free) has a pretty big impact on scalability and performance of multi-threaded code that mutates the tree.

Regards,
Luke