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

Subject: Re: [geometry] Boost Geometry Performance vs LibSpatialIndex.
From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2018-03-01 23:08:58

That's nearly exactly what I replied to Ian in private conversation.
I'm glad you seem to confirm my understanding Adam.
I also haven't looked into very details of libspatialindex, neither I have
profiled it to find out where are the hot spots.

Mateusz Loskot, mateusz_at_[hidden]
(Sent from mobile)

On 2 Mar 2018 12:04 am, "Adam Wulkiewicz via Geometry" <
geometry_at_[hidden]> wrote:

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

_______________________________________________
Geometry mailing list
Geometry_at_[hidden]
https://lists.boost.org/mailman/listinfo.cgi/geometry