百科.dev
全部条目在线工具AI 编程趋势榜开源项目技术资讯提交条目
登录
< 返回工具列表
S

sort-research-rs

> 编程语言
开源

用于测试和基准测试排序实现的套件。

539 stars0 点赞1 次浏览
访问官网GitHub

工具介绍

用于测试和基准测试排序实现的套件。

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 ----

# 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:

bash
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:

bash
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

bash
cd fuzz
cargo fuzz run libfuzzer_main

Fuzzing with afl

bash
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.

Issues· 0 开放

查看全部 Issues在 GitHub 打开

暂无开放 Issues,或尚未同步最近议题。

> 标签

Rust

暂无评论,来聊聊你的看法吧

> 工具信息

发布日期2026年8月1日
最后更新2026年9月17日
分类编程语言
定价开源

> 相关工具

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言