ska_sort
SingeliSort
ska_sort | SingeliSort | |
---|---|---|
2 | 1 | |
229 | 8 | |
- | - | |
10.0 | 7.0 | |
about 3 years ago | 3 months ago | |
C++ | C | |
- | BSD Zero Clause 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.
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/
SingeliSort
-
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.
tiny-sort-rs - This crate provides two sort implementation, one stable and one unstable that are optimized for binary size.
llama.cpp - LLM inference in C/C++