quadsort
sort-research-rs
| quadsort | sort-research-rs | |
|---|---|---|
| 9 | 47 | |
| 2,106 | 292 | |
| - | - | |
| 4.6 | 9.0 | |
| 6 months ago | 6 days ago | |
| C | Rust | |
| The Unlicense | Apache License 2.0 |
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.
quadsort
-
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)
https://github.com/scandum/quadsort/blob/f171a0b26cf6bd6f6dc...
As you can see, quadsort 1.1.4.1 used 2 instead of 4 writes in the bi-directional parity merges. This was in June 2021, and would have compiled as branchless with clang, but as branched with gcc.
When I added a compile time check to use ternary operations for clang I was not adapting your work. I was well aware that clang compiled ternary operations as branchless, but I wasn't aware that rust did as well. I added the compile time check to use ternary operations for a fair performance comparison against glidesort.
https://raw.githubusercontent.com/scandum/fluxsort/main/imag...
As for ipnsort's small sort, it is very similar to quadsort's small sort, which uses stable sorting networks, instead of unstable sorting networks. From my perspective it's not exactly novel. I didn't go for unstable sorting networks in crumsort to increase code reuse, and to not reduce adaptivity.
-
Show HN: QuadSort, Esoteric Fast Sort
In the code it looks like the seed to the benchmark can be provided as the 4th command line argument: https://github.com/scandum/quadsort/blob/master/src/bench.c#...
-
When does big-oh notation become not helpful when comparing algorithms?
If you look at sorting for example, it's been proven that you can't do a comparison-based sort faster than O(n logn). You may then think that we've already found the fastest possible sorting algorithms since Quicksort and Mergesort are already O(n logn). However, new sorting algorithms keep being invented, for example Quadsort. They're all still O(n logn), but they do offer a considerable speed improvement over more traditional algorithms
- quadsort 1.1.5.1: Up to 2.5x faster than qsort() on random data
- Quadsort 1.1.5.1: Introducing cost effective branchless merging
- I tried creating a sorting algorithm in C language.
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
What are some alternatives?
pdqsort - Pattern-defeating quicksort.
tock - A secure embedded operating system for microcontrollers
fluxsort - A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.
ruduino - Reusable components for the Arduino Uno.
blitsort - Blitsort is an in-place stable adaptive rotate mergesort / quicksort.
Klib - A standalone and lightweight C library
glidesort - A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.
sort-test - A simple sort benchmarking tool
rotate - A collection of array rotation algorithms.
x86-simd-sort - C++ template library for high performance SIMD based sorting algorithms