What is this?
A test, benchmark and fuzzing suite for sort implementations, written in Rust. It also hosts a novel sort called ipnsort, vendored Rust, C++ and C sorts for comparison, and the resulting research papers.
A test, benchmark and fuzzing suite for sort implementations, written in Rust. It also hosts a novel sort called ipnsort, vendored Rust, C++ and C sorts for comparison, and the resulting research papers.Is this a library I'd pull into my project, or a standalone suite?A standalone research suite of test and benchmark crates you clone and run with cargo, not a library you depend on. Sort implementations in Rust, C++ and C are vendored inside for comparison.
A standalone research suite of test and benchmark crates you clone and run with cargo, not a library you depend on. Sort implementations in Rust, C++ and C are vendored inside for comparison.How do I run the tests and benchmarks?Clone the repository and use cargo: it runs the test suite and the benchmark suite, and you can pass a custom regex to filter which benchmarks run.
Clone the repository and use cargo: it runs the test suite and the benchmark suite, and you can pass a custom regex to filter which benchmarks run.What do I need to have installed?Rust with cargo for the core suite; cargo fuzz and cargo afl for fuzzing; Python plus the requirements.txt dependencies if you want to generate graphs from collected results.
Rust with cargo for the core suite; cargo fuzz and cargo afl for fuzzing; Python plus the requirements.txt dependencies if you want to generate graphs from collected results.Anything to watch out for when running it?Most functionality is disabled by default via cargo features — check Cargo.toml to enable what you need — and some options are switched through environment variables, e.g. in benches/bench.rs.
Most functionality is disabled by default via cargo features — check Cargo.toml to enable what you need — and some options are switched through environment variables, e.g. in benches/bench.rs.Who is this for — people building sort implementations, or general Rust developers?Mostly sort implementers and performance researchers: it checks correctness properties not commonly upheld and benchmarks across types, patterns and sizes — useful when writing or evaluating a sort itself.
Mostly sort implementers and performance researchers: it checks correctness properties not commonly upheld and benchmarks across types, patterns and sizes — useful when writing or evaluating a sort itself.Can it test and benchmark C and C++ sorts, or only Rust ones?Most tests and benchmarks work on non-Rust implementations: the benchmark types are exposed as #[repr(C)] with a defined C API that you implement to wrap your C or C++ sort, like the vendored cpppdqsort.
Most tests and benchmarks work on non-Rust implementations: the benchmark types are exposed as #[repr(C)] with a defined C API that you implement to wrap your C or C++ sort, like the vendored cpppdqsort.What is ipnsort?ipnsort (Instruction-Parallel-Network-Sort) is the novel sort implementation developed in this repo: an efficient, generic and robust unstable sort. The same research produced driftsort, a stable counterpart.
ipnsort (Instruction-Parallel-Network-Sort) is the novel sort implementation developed in this repo: an efficient, generic and robust unstable sort. The same research produced driftsort, a stable counterpart.What came out of the research?Results are published as papers: the unreasonable effectiveness of modern sort algorithms, a novel branchless partition implementation, a Safety vs Performance case study of C, C++ and Rust sorts, and performance analyses of Intel's x86-simd-sort (AVX-512) and of glidesort/ipnstable.
Results are published as papers: the unreasonable effectiveness of modern sort algorithms, a novel branchless partition implementation, a Safety vs Performance case study of C, C++ and Rust sorts, and performance analyses of Intel's x86-simd-sort (AVX-512) and of glidesort/ipnstable.Can it turn benchmark results into graphs?Yes: runbenchmarks.py collects result sets, and graphall.py builds graphs from them — install the Python dependencies from requirements.txt first.
Yes: runbenchmarks.py collects result sets, and graphall.py builds graphs from them — install the Python dependencies from requirements.txt first.What are similar projects?pgrust, m4-sme-exploration, CalcKernel, Tov, spinel, libvips, libevent, cpu-performance-engineering
pgrust, m4-sme-exploration, CalcKernel, Tov, spinel, libvips, libevent, cpu-performance-engineeringWhich topics is it in?sorting-algorithms, fuzzing, scientific-computing, papers, systems-programming, algorithms, c, testing, cpp, benchmark, performance, rust
sorting-algorithms, fuzzing, scientific-computing, papers, systems-programming, algorithms, c, testing, cpp, benchmark, performance, rust