sort-research-rs
mountain-sort
sort-research-rs | mountain-sort | |
---|---|---|
47 | 1 | |
291 | 3 | |
- | - | |
9.0 | 10.0 | |
24 days ago | over 8 years ago | |
Rust | C++ | |
Apache License 2.0 | MIT License |
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.
sort-research-rs
-
The Rust Calling Convention We Deserve
If you want a particularity cursed example, I've recently called Go code from Rust via C in the middle, including passing a Rust closure with state into the Go code as callback into a Go stdlib function, including panic unwinding from inside the Rust closure https://github.com/Voultapher/sort-research-rs/commit/df6c91....
- Driftsort: An efficient, generic and robust stable sort implementation
-
Out-of-bounds read and write in the glibc's qsort()
See also https://github.com/Voultapher/sort-research-rs/blob/main/wri.... Discussion at https://news.ycombinator.com/item?id=37781612
- Fast, small, robust: pick three. Introducing a novel branchless partition impl
- A performance analysis of Intel's x86-simd-sort
- sort-research-rs/writeup/intel_avx512/text.md at main ยท Voultapher/sort-research-rs
- Fast, small, robust: pick three. Introducing a novel branchless partition implementation.
-
Branchless Lomuto Partitioning
There was a recent post by Voultapher from the sort-research-rs project on Branchless Lomuto Partitioning
https://github.com/Voultapher/sort-research-rs/blob/main/wri...
Discussion here:
https://news.ycombinator.com/item?id=38528452
This post by orlp (creator of Pattern-defeating Quicksort and Glidesort) was linked to in the above post, and I found both to be interesting.
- A novel branchless partition implementation
- Fast, small, robust: Introducing a novel branchless partition implementation
mountain-sort
-
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)
It depends on the size of the structs. For struct pointers you're likely better off sorting keys and pointers simultaneously. It doesn't matter much until you get to large sizes (millions), but sorting indices and then selecting with them is random access. If the original ordering is messy, selecting can be slower than the sorting step. For structs a few words long, the unit you're moving is a larger portion of a cache line, and I'd expect the data movement to drown out any SIMD advantage. A radix sort might be all right because it moves less, but I'd probably go with sorting indices as the first thing to try unless I knew the arrays were huge. For very large structs there's an interesting effort called mountain sort[0], "probably the best sorting algorithm if you need to sort actual mountains by height". Given that it minimizes number of moves it's ignoring cache entirely. I haven't benchmarked so I can't say much about how practical it is.
[0] https://github.com/Morwenn/mountain-sort
What are some alternatives?
tock - A secure embedded operating system for microcontrollers
rotate - A collection of array rotation algorithms.
ruduino - Reusable components for the Arduino Uno.
quadsort - Quadsort is a branchless stable adaptive mergesort faster than quicksort.
fluxsort - A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.
rust - Empowering everyone to build reliable and efficient software.
glidesort - A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.
highway - Performance-portable, length-agnostic SIMD with runtime dispatch
Presentations - Collection of personal presentations