Thoughts on SIMD support and data types

[tirithen]

Hi! Are there any plans on using data types and algorithms that enables SIMD support?

There is an interesting article on that here https://www.rustsim.org/blog/2020/03/23/simd-aosoa-in-nalgebra/ that mentions the crates https://crates.io/crates/ultraviolet and https://crates.io/crates/nalgebra

[Stoeoef]

So, I've finally come to take a look at this.

In general, Delaunay triangulations have actually very little linear algebra going on - Spade rarely does matrix or vector operations that would be potentially be sped up by a linear algebra crate.

The major (and very important) exception is the orientation and incircle tests which are provided by robust - these do take up a significant amount of time. Both of them are determinant calculations under the hood which can definitely be improved with some SIMD.

E.g. the code for the incircle test can be found here: https://github.com/georust/robust/blob/a1ecfc790d9a23092b7bab9a4827551696a27263/src/lib.rs#L564

Now, I've tried to speed up this code by switching to linear algebra libraries for the vector operations that are used in this function. However, at least from looking at the assembly, I wasn't really able to outperform the existing code generation.
This code already auto-vectorizes many (or even all?) of the floating point operations (when compiled with target-cpu=native...)

See https://godbolt.org/z/hKaaj9c1c

My local code-gen appeared to only swap around some of the instructions, their overall count appeared to remain the same.

Disclaimer: I'm not that well versed in reading assembly code - I might miss something obvious.

---

Thus, I currently don't see great potential for speeding this up. I hope to be mistaken though :-) . In the meantime, I'll close this issue - feel free to comment if I'm missing out on something and I'm happy to re-open.

[tirithen]

@Stoeoef thank you for having a look into this! You are probably right then, makes sense to just close this issue. Thanks for your work on the crate.