tiny_sort 二进制大小优化的排序实现

tiny_sort 包提供了两种排序实现 tiny_sort::stable::sort 和 tiny_sort::unstable::sort。该包是 no_std，并且可以通过设置 default-features = false 来禁用这两个版本。 tiny_sort::stable::sort 需要 alloc，而 tiny_sort::unstable::sort 不需要。除了 fn sort<T: Ord>(v: &mut [T]) 外，这两个排序实现还提供了 fn sort_by<T, F: FnMut(&T, &T) -> Ordering>(v: &mut [T], mut compare: F)，以便使用自定义比较函数进行排序。

如果你更关心二进制大小而不是性能，请使用这些排序实现。否则请使用 slice::sort 和 slice::sort_unstable。

更深入地了解这些实现。

稳定排序::sort

稳定的排序是无分支归并排序。这意味着

• 保证 O(N * log(N)) 的情况下最坏情况性能
• 无适应性
• 分支预测不受比较函数结果的 影响
• 分配 N 个辅助内存。

不稳定::sort

不稳定排序是一种无分支堆排序。这意味着

• 保证 O(N * log(N)) 的情况下最坏情况性能
• 无适应性
• 分支预测不受比较函数结果的 影响

基准测试

设置

Linux 6.3
rustc 1.76.0-nightly (f704f3b93 2023-12-19)
clang version 15.0.7
gcc (GCC) 13.1.1 20230429
AMD Ryzen 9 5900X 12-Core Processor (Zen3 micro-architecture)
CPU boost enabled.

参赛者

- rust_tinymergesort_stable    | This crate' `stable::sort`
- rust_std_stable              | `slice::sort` https://github.com/rust-lang/rust (1)
- cpp_std_gnu_stable           | libstdc++ `std::sort_stable` (2)
- cpp_std_libcxx_stable        | libc++ `std::sort_stable` (3)

- rust_tinyheapsort_unstable   | This crate' `unstable::sort`
- rust_std_unstable            | `slice::sort_unstable` https://github.com/rust-lang/rust (1)
- cpp_std_gnu_unstable         | libstdc++ `std::sort` (2)
- cpp_std_libcxx_unstable      | libc++ `std::sort` (3)

脚注

1. 约于 2022 年中旬发布。
2. 使用 gcc 构建。
3. 使用 clang 构建。

二进制大小

一个最小程序使用 --release，lto = "thin" 和 opt-level = "s" 对 Rust 代码进行编译，以及 -Os 仅对头文件 C++ 代码进行编译。C++ 代码使用 gcc 编译。生成的二进制文件使用 strip 去掉符号。

#[inline(never)]
fn instantiate_sort<T: Ord + std::fmt::Display>(mut v: Vec<T>) {
    tiny_sort::unstable::sort(&mut v);

    // side-effect
    println!("{}", v[v.len() - 1]);
}

fn main() {
    use std::env;
    let len = env::args().len();

    // The vec pattern is hard to predict for the compiler.
    // And the len is unknown by design.
    // Plus instantiate_sort is forced to inline never which means it has to be
    // compiled in a way that could accept all possible layout of v.
    instantiate_sort((0..len as u64).rev().collect());
}

未取消注释排序的基线是： 292_864 字节。下面的值是去除符号的二进制大小与基线之差。

- rust_tinymergesort_stable    | 528 bytes
- rust_std_stable              | 2928 bytes
- cpp_std_gnu_stable           | 5528 bytes
- cpp_std_libxx_stable         | 4368 bytes

- rust_tinyheapsort_unstable   | 320 bytes
- rust_std_unstable            | 3848 bytes
- cpp_std_gnu_unstable         | 2128 bytes
- cpp_std_libcxx_unstable      | 1272 bytes

运行时间

一个粗略估计，说明使用这些排序实现可以得到什么样的性能。 如果您关心性能，请使用 slice::sort 和 slice::sort_unstable。

稳定排序::sort

hot-u64-10k

cold-u64-scaling-random

不稳定::sort

hot-u64-10k

cold-u64-scaling-random

最小 required rustc 版本

所需的最小 rustc 版本是 1.51。

最小版本是尽力而为的，并可能随着任何新的主要版本发布而更改。

贡献

在贡献时请尊重 CODE_OF_CONDUCT.md。

版本控制

我们使用 SemVer 进行版本控制。有关可用的版本，请参阅 此存储库上的标签。

作者

• Lukas Bergdoll - 初始工作 - Voultapher

还可以查看参与此项目的 贡献者列表。

许可证

此项目根据 Apache 许可证第 2 版许可 - 请参阅 LICENSE.md 文件以获取详细信息。