fluxsort
rust
fluxsort | rust | |
---|---|---|
12 | 2,683 | |
662 | 93,041 | |
- | 1.2% | |
6.4 | 10.0 | |
3 months ago | 7 days ago | |
C | Rust | |
The Unlicense | 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.
fluxsort
- Fluxsort: A stable quicksort, now faster than Timsort for both random and ordered data
-
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)
Steps to build a fast, highly adaptive AVX-512 sorting algorithm:
- Clone fluxsort (https://github.com/scandum/fluxsort)
- Replace the partitioning code in flux_default_partition and flux_reverse_partition with the obvious AVX-512 version using a compare and two compress instructions
- If you're feeling ambitious, swap out the small array sorting, or incorporate crumsort's fulcrum partition for larger arrays.
I know why I haven't done this: my computer doesn't have AVX-512, and hardly anyone else's seems to. Maybe a couple Zen 4 owners. I'm less clear on why the tech giants are reinventing the wheel to make these sorting alrogithms that don't even handle pre-sorted data rather than working with some of the very high-quality open source stuff out there. Is adaptivity really considered that worthless?
Fluxsort makes this particularly simple because it gets great performance out of a stable out-of-place partition. It's a bit newer; maybe the authors weren't aware of this work. But these algorithms both use (fairly difficult) in-place partitioning code; why not slot that into the well-known pdqsort?
- A Rust port of crumsort, up to 75% faster than pdqsort
- GitHub - scandum/fluxsort: A branchless stable quicksort / mergesort hybrid.
-
Reinforcement learned branchless sorting functions for sort3, sort4 and sort5 were landed in LLVM
With the right code and code-gen https://github.com/scandum/fluxsort/issues/5 these can be excellent at exploiting wide super-scalar architectures. I use them in both ipn_stable and to a larger extent in ipn_unstable which even uses the lesser known median networks for pivot selection. That said, I've done a lot of experiments with smaller sorting networks, sort3/4/5 as used in libcxx. And I found that they only look good in synthetic micro-benchmarks. If all your program does, is sort inputs of one specific size 3/4/5 in a hot loop and does nothing else, yes they are faster than insertion sort. But as soon as your application does some non-trivial amount of other work before calling sort again, the code complexity and additional branching required to get to that sort network is not worth it anymore. Depending on your architecture, my findings suggest they only start pulling ahead beginning at sizes 8-12.
-
Changing std:sort at Google’s Scale and Beyond
Any chance you could comment on fluxsort[0], another fast quicksort? It's stable and uses a buffer about the size of the original array, which sounds like it puts it in a similar category as glidesort. Benchmarks against pdqsort at the end of that README; I can verify that it's faster on random data by 30% or so, and the stable partitioning should mean it's at least as adaptive (but the current implementation uses an initial analysis pass followed by adaptive mergesort rather than optimistic insertion sort to deal with nearly-sorted data, which IMO is fragile). There's an in-place effort called crumsort along similar lines, but it's not stable.
I've been doing a lot of work on sorting[2], in particular working to hybridize various approaches better. Very much looking forward to seeing how glidesort works.
[0] https://github.com/scandum/fluxsort
[1] https://github.com/scandum/crumsort
[2] https://mlochbaum.github.io/BQN/implementation/primitive/sor...
- I tried creating a sorting algorithm in C language.
- Fluxsort: A stable adaptive partitioning comparison sort
-
Hacker News top posts: Jul 25, 2021
Fluxsort: A stable adaptive partitioning comparison sort\ (0 comments)
rust
-
Create a Custom GitHub Action in Rust
If you haven't dipped your touch-typing fingers into Rust yet, you really owe it to yourself. Rust is a modern programming language with features that make it suitable not only for systems programming -- its original purpose, but just about any other environment, too; there are frameworks that let your build web services, web applications including user interfaces, software for embedded devices, machine learning solutions, and of course, command-line tools. Since a custom GitHub Action is essentially a command-line tool that interacts with the system through files and environment variables, Rust is perfectly suited for that as well.
-
Why Does Windows Use Backslash as Path Separator?
Here's an example of someone citing a disagreement between CRT and shell32:
https://github.com/rust-lang/rust/issues/44650
This in addition to the Rust CVE mentioned elsewhere in the thread which was rooted in this issue:
https://blog.rust-lang.org/2024/04/09/cve-2024-24576.html
Here are some quick programs to test contrasting approaches. I don't have examples of inputs where they parse differently on hand right now, but I know they exist. This was also a problem that was frequently discussed internally when I worked at MSFT.
#include
-
I hate Rust (programming language)
> instead of choosing a certain numbered version of the random library (if I remember correctly) I let cargo download the latest version which had a completely different API.
Yeah, they didn't follow the instructions and got burned. I still think that multiple things went wrong simultaneously for that experience. I wonder if more prevalent uses of `#[doc(alias = "name")]` being leveraged by https://github.com/rust-lang/rust/pull/120730 (which now that I check only accounts for methods and not functions, I should get on that!) so that when changing APIs around people at least get a slightly better experience.
- Rust Weird Exprs
- Critical safety flaw found in Rust on Windows (CVE-2024-24576)
-
Unformat Rust code into perfect rectangles
Almost fixed the compiler: https://github.com/rust-lang/rust/pull/123325
-
Implement React v18 from Scratch Using WASM and Rust - [1] Build the Project
Rust: A secure, efficient, and modern programming language (omitting ten thousand words). You can simply follow the installation instructions provided on the official website.
-
Show HN: Fancy-ANSI – Small JavaScript library for converting ANSI to HTML
Recently did something similar in Rust but for generating SVGs. We've adopted it for snapshot testing of cargo and rustc's output. Don't have a good PR handy for showing Github's rendering of changes in the SVG (text, side-by-side, swiping) but https://github.com/rust-lang/rust/pull/121877/files has newly added SVGs.
To see what is supported, see the screenshot in the docs: https://docs.rs/anstyle-svg/latest/anstyle_svg/
-
Upgrading Hundreds of Kubernetes Clusters
We strongly believe in Rust as a powerful language for building production-grade software, especially for systems like ours that run alongside Kubernetes.
-
What Are Const Generics and How Are They Used in Rust?
The above Assert<{N % 2 == 1}> requires #![feature(generic_const_exprs)] and the nightly toolchain. See https://github.com/rust-lang/rust/issues/76560 for more info.
What are some alternatives?
crumsort - A branchless unstable quicksort / mergesort that is highly adaptive.
carbon-lang - Carbon Language's main repository: documents, design, implementation, and related tools. (NOTE: Carbon Language is experimental; see README)
pdqsort - Pattern-defeating quicksort.
zig - General-purpose programming language and toolchain for maintaining robust, optimal, and reusable software.
quadsort - Quadsort is a branchless stable adaptive mergesort faster than quicksort.
Nim - Nim is a statically typed compiled systems programming language. It combines successful concepts from mature languages like Python, Ada and Modula. Its design focuses on efficiency, expressiveness, and elegance (in that order of priority).
awesome-algorithms - A curated list of awesome places to learn and/or practice algorithms.
Odin - Odin Programming Language
awesome-theoretical-computer-science - The interdicplinary of Mathematics and Computer Science, Distinguisehed by its emphasis on mathemtical technique and rigour.
Elixir - Elixir is a dynamic, functional language for building scalable and maintainable applications
xeus-cling - Jupyter kernel for the C++ programming language
Rustup - The Rust toolchain installer