Significantly faster quicksort using SIMD

• cosmopolitan

  201 15,067 9.8 C

  build-once run-anywhere c library

I wonder how fast it is compared to djbsort https://github.com/jart/cosmopolitan/blob/master/libc/nexgen... and longsort https://github.com/jart/cosmopolitan/blob/e011973593407f576d... djbsort is outrageously fast for 32-bit ints with avx2 (which unlike avx512 it's the avx we can reliably use in open source). But there's never been a clear instruction set to use on Intel / AMD for sorting 64-bit ints that's reliably fast. So if this thing can actually sort 64-bit integers 10x faster on avx2 I'd be so thrilled.

• tidb

  1 19 0.0 Go
  

This is great, and can definitely help quite a lot database and big data projects. I can immediately imagine this is a perfect match to one open source HTAP system (https://github.com/tigraph/tidb) which uses SIMD in their columnar processing engine TiFlash (https://github.com/pingcap/tiflash).

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

• tiflash

  5 929 9.7 C++

  The analytical engine for TiDB and TiDB Cloud. Try free: https://tidbcloud.com/free-trial

  

This is great, and can definitely help quite a lot database and big data projects. I can immediately imagine this is a perfect match to one open source HTAP system (https://github.com/tigraph/tidb) which uses SIMD in their columnar processing engine TiFlash (https://github.com/pingcap/tiflash).

• vops

  1 162 5.6 C
  

This might interest someone: "Vectorized Operations extension for PostgreSQL"

https://github.com/postgrespro/vops

• vxsort-cpp

  2 30 5.9 C++

  My very own vxsort re-implemented with "modern" C++ by a complete idiot (in C++)

Interesting post and paper, thanks!

Sometimes the state of the art is not found in another paper but somewhere else, e.g,. there is vxsort by Dan Shechter (damageboy):

https://github.com/damageboy/vxsort-cpp/tree/master

He uses a similar approach and while I'm not sure how it compares to the Blacher et al version, I expect it to be in the ballpark.

• avx_qsort

  2 67 10.0 Assembly

  Quick sort code using AVX2 instructions

I'm the co-author of one of the papers referenced in the blogpost, (Fast Quicksort Implementation Using AVX Instructions), we did write the AVX512 code back in 2015, just had nowhere to run it, at least publicly. The paper also very explicitly says that the lookup tables can be instead replaced by the AVX512 compress instructions. The code for that paper is available in https://github.com/vkrasnov/avx_qsort

• version2

  6 1,216 5.8 C++

  Vector class library, latest version

  

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• highway

  66 3,645 9.8 C++

  Performance-portable, length-agnostic SIMD with runtime dispatch

  

Response here because I'm not on Twitter: https://github.com/google/highway/issues/736

In short, what is being compared is O(1) djbsort sorting network, vs our full quicksort with pivot sampling, partitioning, then sorting network.

This is because our sorting network size is 16 * elements_per_vector i.e. 128 in this configuration.

Suggest a related project