I remember being a bit disappointed with how Julia fared against Chapel in their comparison of standard library sort implementations a couple of years ago, and julia with threaded sort + mergesort was nowhere near the chapel implementation in terms of performance.
Now with LLMs, it’s easy to translate between languages, so I was curious how a julia implementation of the same algorithm (would perform.
The results from a quick benchmark on my laptop are quite encouraging:
Strings can also be sorted faster this way:
Finally, I also wondered if applying some of this could be useful to speed up dataframes operations. And there seems to be some potential here as well, although not as dramatic as for pure sort:
This was just a quick experiment, but in case anyone wants to try it out, the code is available here.
Could you add intel sort simd x86 (both single threaded and multithreaded? and google highway sort(single threaded only) ?
On my machine, they are both twice faster than ChapelSort in single thread mode and intel sort is still twice faster than ChapelSort in multithreaded.
So far, I haven’t come across anything faster.
I did my benchmarks on 10^8 and 10^9 random float64.
Thanks for pointing out these libraries and algorithms. I wasn’t aware of those, and indeed they perform significantly better (on the types they support). Cool to see that quicksort is still relevant.
Of course, this begs the question: can we match this performance in pure julia?
Long story short, for most types we can match or surpass the performance of these libraries.
These are the results from this weekend-project: SIMDSort.jl. This time I asked the AI to start from published papers rather than port the code directly, so it was a bit more work, and notably needed a patched SIMD.jl as several of the needed functions were not implemented.
See the project README for more results and details (as the rest of the project AI generated).
Quite a bit of tuning trading off when to use which algorithm, caches, etc was needed to achieve good performance overall, these results are based on tuning on one AVX2 capable machine (8 threads) and one supporting AVX-512 (56 threads). If you want to try it on additional architectures to improve the tuning, there is a function SIMDSort.tuning_report() that should give output you may submit in an issue (or here I guess).
