SIMD optimizations

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

SIMD optimizations

Vladimir Voznesensky
Hello there.
 
Every node of rtree concludes information about several geometrical objects or boxes bounding such objects. Is it possible to zip (transpose) such information into SIMD vectors (using libsimdpp, for example) to use fast SIMD instructions without messing up too many stuff in boost::geometry?
 
Thanks.

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: SIMD optimizations

Adam Wulkiewicz
Hi Vladimir,

Vladimir Voznesensky wrote:
> Every node of rtree concludes information about several geometrical
> objects or boxes bounding such objects. Is it possible to zip
> (transpose) such information into SIMD vectors (using libsimdpp, for
> example) to use fast SIMD instructions without messing up too many
> stuff in boost::geometry?

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?
And what would you like to do with them? Would they still be used as
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?

Regards,
Adam
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: SIMD optimizations

Vladimir Voznesensky
Please, find the comments below.

29.01.2016, 02:23, "Adam Wulkiewicz" <[hidden email]>:
> 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.

Regards,
Vladimir
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: SIMD optimizations

Adam Wulkiewicz
Vladimir Voznesensky wrote:

> Please, find the comments below.
>
> 29.01.2016, 02:23, "Adam Wulkiewicz" <[hidden email]>:
>> 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 mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry