avx_qsort
zort
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
avx_qsort
-
Sorting with SIMD
The original (AFAICT) work on SIMD quick sort, also mentioned in the google post also implemented pointer sort by loading a pointed key using gather instructions and the method can be used for an array of structs. https://github.com/vkrasnov/avx_qsort/blob/master/qsort_AVX2...
-
Significantly faster quicksort using SIMD
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
zort
-
How a Zig IDE Could Work
because both parts of the expression are evaluated by the compiler and must be the same type, including the function's return type. This means we end up instantiating nonsense functions like readOneByte returning u16. Elsewhere in the same file, some should-be-impossible template instantiations have had to have their static_assert's removed, because C++ will instantiate them and then not insert any calls to them into the generated code. So one cannot use static_assert to say "If this is reachable, that's a bug, please fail compilation and return an error" because template instantiation does not imply reachability.
[0]: https://github.com/alichraghi/zort/blob/main/src/radix.zig#L...
-
Sorting with SIMD
Please do comment in situations like this.
It's tough to find a good overview of this topic that includes recent work or that is aimed at empirical performance. That's part of why TFA is great!
A version of MSB radix sort for sorting ints, doubles, or floats, or sorting structs by a single key of those types is here[0] and a version for sorting strings is here[1]. These are based on the MSB radix sort from this repository[2] which is associated with a technical report about parallel string sorts. I was only interested in sequential sorts, but this repository turned out to be a great resource anyway.
[0]: https://github.com/alichraghi/zort/blob/main/src/radix.zig
[1]: https://github.com/dendibakh/perf-challenge6/blob/Solution_R...
[2]: https://github.com/bingmann/parallel-string-sorting
What are some alternatives?
highway - Performance-portable, length-agnostic SIMD with runtime dispatch
zerovm-samples - Sample code and libraries built for ZeroVM
perf-challenge6
parallel-string-sorting - Collection of Parallel String Sorting Algorithms including Parallel Super Scalar String Sample Sort and Parallel Multiway LCP-Mergesort