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

Subject: Re: [geometry] Boost Geometry Performance vs LibSpatialIndex.
From: Ian Kosen (ikosenn_at_[hidden])
Date: 2018-03-01 23:25:14

Thank you Adam and Mateusz. This is very helpful. It does serve as a starting point.

Kosen.

> On 1 Mar 2018, at 15:08, Mateusz Loskot via Geometry <geometry_at_[hidden]> wrote:
> 
> 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] <mailto:mateusz_at_[hidden]>
> (Sent from mobile)
> 
> On 2 Mar 2018 12:04 am, "Adam Wulkiewicz via Geometry" <geometry_at_[hidden] <mailto:geometry_at_[hidden]>> wrote:
> Hi Ian,
> 
> Ian Kosen Via Geometry wrote:
>> I was looking at this benchmark https://github.com/mloskot/spatial_index_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 <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] <mailto:Geometry_at_[hidden]>
> https://lists.boost.org/mailman/listinfo.cgi/geometry <https://lists.boost.org/mailman/listinfo.cgi/geometry>
> 
> 
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> https://lists.boost.org/mailman/listinfo.cgi/geometry