Geometry Boost List: Re: [geometry] Boost Geometry Performance vs LibSpatialIndex.

Subject: Re: [geometry] Boost Geometry Performance vs LibSpatialIndex.
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2018-03-01 23:04:37

Hi Ian,

Ian Kosen Via Geometry wrote:
> I was looking at this benchmark 
> https://github.com/mloskot/spatial_index_benchmark%a0which 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