HackerReposA FIELD GUIDE TO OPEN SOURCE
ProSponsor the shelf♧ 0
← Back to top all-time
Voultapher
sort-research-rs
Rust2023–2026
Voultapher / sort-research-rs

sort-research-rs

Test and benchmark suite for sort implementations.

25Distinct people
47Mentions
0Explicit recommenders
546GitHub stars
REPOSITORY AT A GLANCE

What to know before exploring

What it is

Test and benchmark suite for sort implementations.

GitHub

Where it is used

No documented product use was verified in the last source check.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

No other repository is repeatedly linked in the same discussions.

This week on Hacker News

Nov 9–Nov 16 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/16/2026, 6:28:55 AM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by year47 dated mentions

Observed mentions: 2023-02-11 17:42:47 UTC to 2026-09-16 20:15:06 UTC.

05101520252023-01-01 00:00:00 UTC to 2024-01-01 00:00:00 UTC (exclusive): 24 mentions; 8 submissions, 16 comments20232024-01-01 00:00:00 UTC to 2025-01-01 00:00:00 UTC (exclusive): 8 mentions; 3 submissions, 5 comments20242025-01-01 00:00:00 UTC to 2026-01-01 00:00:00 UTC (exclusive): 13 mentions; 8 submissions, 5 comments2026-01-01 00:00:00 UTC to 2027-01-01 00:00:00 UTC (exclusive): 2 mentions; 1 submissions, 1 comments. Incomplete calendar period.2026*

* An incomplete calendar period is marked with an outlined bar. Its count is not directly comparable with a full period.

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges
UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
PeriodStart (UTC)End (exclusive, UTC)MentionsSubmissionsComments
20232023-01-01 00:00:00 UTC2024-01-01 00:00:00 UTC24816
20242024-01-01 00:00:00 UTC2025-01-01 00:00:00 UTC835
20252025-01-01 00:00:00 UTC2026-01-01 00:00:00 UTC1385
2026 (partial)2026-01-01 00:00:00 UTC2027-01-01 00:00:00 UTC211

From the project README

An excerpt from the repository, fetched Nov 13, 2026.

Read the project’s introduction
sort-research-rs Is a sort implementation correct? Is a sort implementation fast? This repository contains: An exhaustive test suite, including properties not commonly checked or upheld An extensive benchmark suite, abstracting over types, patterns and sizes A fuzzing harness A novel sort implementation ipnsort (Instruction-Parallel-Network-Sort) Vendored sort implementations (Rust, C++, C), e.g. cpp_pdqsort, rust_std_stable Various experiments and demonstrations Results of the research as papers Most tests and benchmarks can be applied to non Rust implementations. This works by implementing the 5 benchmark types as #[repr(C)] and having a defined C API that can be implemented, wrapping the C/C++ sorts. Most functionality is by default disabled via cargo features, see the Cargo.toml. Some functionality can be enabled or switched by setting environment variables. See for example benches/bench.rs. Research results The unreasonable effectiveness of modern sort algorithms ipnsort: an efficient, generic and robust unstable sort implementation. driftsort: an efficient, generic and robust stable sort implementation. Fast, small, robust: pick three. Introducing a novel branchless partition implementation. Safety vs Performance. A case study of C, C++ and Rust sort implementations. 10~17x faster than what? A performance analysis of Intel's x86-simd-sort (AVX-512) A performance analysis of glidesort and ipn_stable Running the tests cargo test cargo miri test # Might require disabling criterion dependency. RUSTFLAGS=-Zsanitizer=address cargo t --release Running the benchmarks cargo bench cargo bench <sort_name>-<prediction_state>-<type>-<pattern>-<size> # Example cargo bench rust_std_stable-hot-u64-random-10000 cargo bench hot-u64-random-10000 cargo bench random You can also set a custom regex to filter the benchmarks you want to run: BENCH_REGEX="std.*i32-random-8$" cargo bench If you want to collect a set of results that can then later be used to create graphs, you can use the run_benchmarks.py utility script: # Will write results to my_test_zen3.json BENCH_REGEX="_stable.*random-" python util/run_benchmarks.py my_test_zen3 To run the graph_all.py script to create graphs from this data you need to first install the dependencies as specified in requirements.txt e.g. on Linux: python -m venv venv source ./venv/bin/active pip install --requirement util/graph_bench_result/requirements.txt Afterwards, you can use the graph_all.py script: python util/graph_bench_result/graph_all.py my_test_zen3.json Fuzzing You'll need to install cargo fuzz and cargo afl respectively. See https://rust-fuzz.github.io/book/introduction.html. Fuzzing with libfuzzer cd fuzz cargo fuzz run libfuzzer_main Fuzzing with afl cd fuzz-afl RUSTFLAGS=-Zsanitizer=address cargo afl build --release && cargo afl fuzz -i in -o out -D target/release/afl Adjust fuzz/fuzz_targets/libfuzzer_main.rs and fuzz/fuzz_targets/libfuzzer_main.rs respectively to change the fuzz target. Default rust_ipn_stable. Contributing Please respect the CODE_OF_CONDUCT.md when contributing. Adding a new sort implementation Please open an issue before investing the effort of adding a new sort implementation. The maintainer of this project is currently not interested in building an up-to-date database of all existing sort implementations. Implementations are added based on situational context and relevance to the maintainers' goals. Baseline for all new sort implementations is they must pass all functionality tests, they may pass the safety tests but don't have to. Authors Lukas Bergdoll - Voultapher See also the list of contributors who participated in this project. License This project is licensed under the Apache License, Version 2.0 - see the LICENSE.md file for details.
Read the full README on GitHub

What Hacker News says

24 sources
You claim yourself that "I have not delved very much into depth" yet you make a lot of assumptions here. Here are the key facts, the `_by` functions that contain the complex exception handling stuff are only used for tests and the benchmark ones are as native as possible e.g. `std::sort(data, data + len)`. I pick either gcc or clang based on what gives better performance, and use these settings with the cc crate https://github.com/Voultapher/sort-research-rs/blob/b131ed61... plus sort specific options. It all gets statically linked into one big binary. Also note the C++ code is header only, so one big translation unit per sort. The only disadvantage based on me looking at the generated asm is one additional function call versus possible inlining for the initial part of the sort. This adds a total of ~20 or less cycles to the total time, w
Read the rest
hich in the benchmark is measured in microseconds, where 1 microsecond is ~4900 cycles.
In Safety vs. Performance. A case study of C, C++ and Rust sort implementations
TBH I find it difficult to understand: 1. How do you compile the C++ code? E.g. what flags do you use with GCC, clang and MSVC 2. How exactly is C++ binary run through a Rust benchmark suite? FFI? 3. Is it possible for rust code-under-test to be at any advantage here because it is run and built natively from the benchmark written in the rust itself? What I find questionable though is the actual C++ code found in the benchmark: 1. Exception-handling code around std::sort and std::stable_sort - nobody does that. What problem are you trying to solve with this? Comparators do not throw exceptions. 2. Using function pointers for the comparators - surprising to see such code in C++ benchmark - it's very non-idiomatic and essentially making it impossible for a compiler to inline the code. std::sort is rarely used like that. 3. Passing over some
Read the rest
magical third argument to the comparator function - ? 4. Passing over the context to the comparator "function" - I fail to see if "ctx" has been used anywhere? 5. "Making" the comparator function with make_compare_fn which in turn instantiates a lambda that, again, throws an exception from its body. 6. Storing a comparison result - why? You only need to return true or false from a comparator. 7. Modeling rust "panics" by storing a boolean is_panic plus exception-handling code plus throwing exceptions when is_panic is "ON" - why? 8. Confusing exceptions with rust panics - even if you wanted to do so, which still would be an arguable thing to do, std::abort or std::terminate is a replacement for std::panic. Not throwing exceptions and implementing the is_panic logic around it. 9. What is https://github.com/Voultapher/sort-research-rs/blob/main/src... being used for? I think you're making a bit dishonest representation here for the reasons above. And I have not delved very much into depth nor have I covered all the code but just the fragment of it. Also, it is not quite clear how everything is put together and run because, ideally, you would want to have multiple binaries built with their representative toolchains/scripts _regardless_ of your benchmarking framework. And only then I would want to point the benchmarking framework to the respective binary to run the test. Here, it seems it's the other way around.
In Safety vs. Performance. A case study of C, C++ and Rust sort implementations
Adding onto what the other commenter said, these sort implementations are practically all hybrids, containing multiple sort algorithms. In fact ipnsort uses optimal sorting networks as part of its small-sort https://github.com/Voultapher/sort-research-rs/blob/bf90e294.... And for example vqsort benchmarked in another one of my writeups uses a bitonic merge network to combine smaller blocks created from optimal sorting networks.
In Safety vs. Performance. A case study of C, C++ and Rust sort implementations
The C and C++ code pulls in all thirdparty code as header only, making for one single translation unit, and the compiler is able to do comparison inlining for the C++ implementations. I've written a bit about this previously [here](https://github.com/Voultapher/sort-research-rs/blob/main/wri...). Regarding `ValWithPtr` my goal was to make it as close semantically as I could to the Rust code while keeping the example to a minimum to avoid distracting from the main point. If you have a concrete idea how `ValWithPtr` could have been modeled better given these criteria, please let me know.
In Safety vs. Performance. A case study of C, C++ and Rust sort implementations
I'm surprised to see that the author's ipnsort is not published on crates.io, even though it performs at first or second place on most of the benchmarks for unstable sorts and it passes all the safety and correctness criteria, all while also being able to deterministically panic to inform the user of a logic bug in their comparison function. https://github.com/Voultapher/sort-research-rs/tree/main/ipn...
In Safety vs. Performance. A case study of C, C++ and Rust sort implementations
Yes, only your "10x" and "5-10x" numbers are overstated. Which is to say, all the quantitative comparison you've shared here, or in the vqsort README (aside from the link to Lukas's measurements, which is linked with no indication it benchmarks against faster sorts). What you share is defensible in that it's technically correct, but it's not helpful. As an example, consider an application that uses heapsort now, but ships a unified binary for x86. The programmers could easily switch to pdqsort, which is well-tested and available in many languages. If they read only material you publish, they may get the impression that SIMD support (at least SSE4) is required to get a substantial improvement, and stick with heapsort to avoid the need to ship multiple binaries or add architecture detection. All you need to correct this is one mention that
Read the rest
you can do better than std::sort! By leaving this out, you instead reinforce the idea that it's a reasonable choice if you have to go scalar. ipnsort has no explicit vectorization; some parts may be auto-vectorized. From a quick glance through perf results, I don't see any vector instructions used in the parts that take up time. I didn't see any anywhere, actually. Same story with other quicksorts, although I know fluxsort/crumsort's initial analyzer is designed to be auto-vectorized. I don't get why you dismiss radix sort so quickly, when your own research shows that an MSD/LSD hybrid addresses the bandwidth problem well? Thanks for sharing that paper by the way, very elegant approach. The bandwidth problem is not one I've seen discussed although I see how it would arise. I just don't deal with big arrays that much—and it seems if you're going to market vqsort as general-purpose you should also care about this use case! However, a nice thing about radix sort is that it can be used as a base case for quicksort/samplesort, and any partitioning done so far allows fewer steps to be used. I have a case in SingeliSort to do 4-byte sorting that fits in 2-byte range nearly in-place[0]. It's only used on 2^16 elements or fewer to avoid possible cache associativity problems, so that should fit in L2 and not use system bandwidth. Comparison-based algorithms I consider most relevant at the moment are fluxsort/crumsort/quadsort (all by the same author; they share many pieces), ipnsort (largely derived from those plus pdqsort but it may be easier to read), and glidesort somewhat (the gliding technique is cool but I think there are flaws to address, see [1]). For distribution sorting, there's radix, the version of counting sort where you reconstruct from counts instead of moving the data (output can be vectorized with a scan for large ranges!), and I've developed Robin Hood sort to take advantage of smooth-ish distributions such as uniform random. I keep notes at [2], which are pretty out of date. I should be writing there instead of here... I of course don't think there's any requirement to know all this to contribute to sorting research. I take issue with making blanket claims like "I'd consider AVX2 to be table stakes for any sorting algorithm" and "anything as energy-inefficient as scalar code running on big OoO cores is a hard sell" without being familiar with the state of the art in scalar sorting. [0] https://github.com/mlochbaum/SingeliSort/blob/master/src/rad... [1] https://github.com/Voultapher/sort-research-rs/pull/6#issuec... [2] https://mlochbaum.github.io/BQN/implementation/primitive/sor...
In Intel Releases x86-SIMD-sort 2.0 With Faster AVX-512 Sorting, New Algorithms
See also "10~17x faster than what? A performance analysis of Intel's x86-simd-sort (AVX-512)" at https://github.com/Voultapher/sort-research-rs/blob/main/wri... posted here at https://news.ycombinator.com/item?id=36273544 and minor additional comments at https://news.ycombinator.com/item?id=36268877 . When those benchmarks were first done, for random input, vqsort was faster once you get around ~20,000 items, but for 1,000 items the new AVX512 sort is 13x faster than vqsort. As you read it, you'll see that the vqsort issue for small arrays has been fixed, and as of a few weeks ago or so, vqsort is now faster than the AVX512 sort for random.
In Intel Releases x86-SIMD-sort 2.0 With Faster AVX-512 Sorting, New Algorithms

Showing the 15 most recent of 24 sources. Enable JavaScript to search and browse every indexed mention.

MAKE YOURSELF AT HOME

A few shortcuts

/
Search the collection
?
Open this guide
Esc
Close dialogs and navigation

Your saved repositories and interests stay in this browser.