Hi Ian,

Ian Kosen Via Geometry wrote:

I was looking at this benchmark https://github.com/mloskot/spatial_index_benchmark which attempts to compare the performance between Boost Geometry and LibSpatialIndex. This is done on the r-tree data structure. It caught my eye that Boost Geometry was magnitudes faster than LibSpatialIndex. Is there an obvious reason for this? Design considerations and trade offs?

I'm not familiar with LibSpatialIndex's code to definitely state where is the difference. I can however point out that Boost.Geometry R-tree is in-memory rtree (only, at least for now) and during the implementation I focused on in-memory-access and code performance. While LibSpatialIndex allows to use persistent storage so my guess is that the authors focused more on minimizing disk access, so number of page file loadings affecting performance in this case and that in-memory case was not their primary concern.

Boost.Geometry R-tree uses static polymorphism and template metaprogramming as much as possible while LibSpatialIndex heavily uses dynamic polymorphism. See all of the interfaces (abstract classes with many virtual methods) like IShap, INode, IVisitor, ISpatialIndex, etc. (https://github.com/libspatialindex/libspatialindex/blob/master/include/spatialindex/SpatialIndex.h#L191). So my first guess would be that the compiler is unable to optimize virtual calls while in Boost.Geometry it is able to do it.

Another thing might be data locality or rather lack thereof causing cache misses but I haven't checked how data is stored in nodes of LibSpatialIndex, how bounding boxes are accessed etc. during query so it's possible that this is not the case.

Adam