Boost logo

Geometry :

Subject: Re: [geometry] SIMD optimizations
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2016-01-29 09:14:25


Vladimir Voznesensky wrote:
> Please, find the comments below.
>
> 29.01.2016, 02:23, "Adam Wulkiewicz" <adam.wulkiewicz_at_[hidden]>:
>> Hi Vladimir,
>>
>>
>> How would you like to zip/transpose it exactly? Instead of having a
>> container of e.g. points, to have D containers of coordinates, where D
>> is the dimension?
> Exactly. The maximum number of points in each node/leaf would be determined by SIMD vector size.
>
>> And what would you like to do with them? Would they still be used as
>> coordinates?
> For this topic, the answer is yes, still be coordinates.
>
>> Would you like to change only the nodes contents, provide some
>> lower-level algorithms e.g. testing for spatial overlap or would you
>> like to use entirely different balancing and querying algorithms?
> I'm not intended to change high-level balancing and querying math. Anyway, every algorithm here could benefit from SIMD optimizations.

As I wrote in the other email node types used by the rtree can be
changed easily (though this is not a part of the official interface).
As a reminder, you could:
- define your own parameters like this:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/parameters.hpp#L74
- specialize options_type<> to use your nodes like this:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/options.hpp
- define those node types and specialize required traits like this:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp

With that said currently the rtree assumes that internal nodes store
specific type of objects (a pair) and that both node types store random
access containers of elements (either Values or pairs). Currently the
rtree simply retrieves the reference to a container storing children
nodes or Values and works on those elements. So if we wanted to change
nodes internals we'd be forced to modify the ways how rtree uses the
nodes in all algorithms.

Regards,
Adam


Geometry list run by mateusz at loskot.net