Boost logo

Geometry :

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



Geometry list run by mateusz at loskot.net