search

apache / arrow-rs

Official Rust implementation of Apache Arrow
https://arrow.apache.org/
Apache License 2.0
2.31k stars 682 forks source link

Implement AVX-512 sort operation #136

Open alamb opened 3 years ago

alamb commented 3 years ago

Note: migrated from original JIRA: https://issues.apache.org/jira/browse/ARROW-10664

None

jhorstmann commented 2 years ago

Related paper by google: https://opensource.googleblog.com/2022/06/Vectorized%20and%20performance%20portable%20Quicksort.html

According to their paper they get a huge performance improvement with the use of sorting networks for sorting smaller partitions and by using AVX512 specific instructions for partitioning. The mentioned speedup of 9x-19x times is compared to the C++ standard library, the rust standard sort_unstable already has some additional optimizations so that the speedup is probably lower.

Our main usecase is also sorting to indices, it's not fully clear how well that use case is supported by their algorithm.

We probably don't want to maintain such an implementation inside arrow-rs, but if someone ports the algorithm to rust as a crate we should be able to use it.