ska_sort
tiny-sort-rs
| ska_sort | tiny-sort-rs | |
|---|---|---|
| 2 | 1 | |
| 229 | 1 | |
| - | - | |
| 10.0 | 6.7 | |
| about 3 years ago | 5 months ago | |
| C++ | Rust | |
| - | GNU General Public License v3.0 or later |
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.
ska_sort
-
Understanding DeepMind's Sorting Algorithm
Hang on, you can't just quote MB/s numbers for an O(n log(n)) sort. What length were these tests run at?
The code size might not end up quite as good, but a branchless merge sort is a contender for a fast and lightweight merge. Just published, tiny-sort-rs[0] cites 632 bytes and looks like ~350MB/s at 1e4 elements on Zen 3. In my tests, my own pisort[1] benches a little over twice as fast as LongSort, but it uses sorting networks as the base case so it's like 5KB. It's roughly based on piposort[2] which has more complicated recursion but a simpler base case.
400 MB/s seems a bit slow for a radix sort on that hardware: I'm hitting those numbers on my i5-6200U, which has less than half the clock rate, with my own radix sort. Recommend checking ska_sort_copy from [3] as it has about the same performance.
[0] https://github.com/Voultapher/tiny-sort-rs
[1] https://github.com/mlochbaum/SingeliSort/blob/master/src/mer...
[2] https://github.com/scandum/piposort
[3] https://github.com/skarupke/ska_sort
-
Is there radix sort in the STL? Or in any other library?
Skarupke has a good radix sort implementation https://github.com/skarupke/ska_sort https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
tiny-sort-rs
-
Understanding DeepMind's Sorting Algorithm
Hang on, you can't just quote MB/s numbers for an O(n log(n)) sort. What length were these tests run at?
The code size might not end up quite as good, but a branchless merge sort is a contender for a fast and lightweight merge. Just published, tiny-sort-rs[0] cites 632 bytes and looks like ~350MB/s at 1e4 elements on Zen 3. In my tests, my own pisort[1] benches a little over twice as fast as LongSort, but it uses sorting networks as the base case so it's like 5KB. It's roughly based on piposort[2] which has more complicated recursion but a simpler base case.
400 MB/s seems a bit slow for a radix sort on that hardware: I'm hitting those numbers on my i5-6200U, which has less than half the clock rate, with my own radix sort. Recommend checking ska_sort_copy from [3] as it has about the same performance.
[0] https://github.com/Voultapher/tiny-sort-rs
[1] https://github.com/mlochbaum/SingeliSort/blob/master/src/mer...
[2] https://github.com/scandum/piposort
[3] https://github.com/skarupke/ska_sort
What are some alternatives?
github-drama - github-drama (community fork) Important: To edit, open a pull request. We will merge it as soon as we see the notification. To edit a large amount of content, open an issue saying so. We will grant you write access. To receive notifications about the latest drama, subscribe to the Community-Driven Happenings Feed.
piposort - Piposort is a small branchless stable adaptive mergesort.
llama.cpp - LLM inference in C/C++
SingeliSort - Sorting with Singeli