为何Rust的sort_unstable比C++ std::sort性能高出数倍？

AI 小北

2026-6-1

基准测试结果

g++ .\test_sort.cpp -O3 -march=native -mtune=native -flto -funroll-loops -fomit-frame-pointer -DNDEBUG

C++: 8577.17 ms
-------------------------------
rustc -C opt-level=3 main.rs

Rust: 1379.375 ms

问题描述

我在基准测试中发现，Rust的排序函数（尤其是sort_unstable）比C++的std::sort快很多。

我知道Rust的sort_unstable基于ipnsort（之前与pdqsort相关），而C++的std::sort通常基于内省排序（introsort），具体实现取决于标准库。

我想知道具体是什么让Rust的实现在实际场景中更快？

主要是算法差异（ipnsort vs 内省排序）导致的吗？
是因为Rust对原始类型的特化更激进吗？
分支预测、分区策略或重复元素处理是主要差异点吗？
有没有C++的std::sort性能相当甚至更优的场景？

我特别关注实现层面的原因，而非简单的“不稳定排序比稳定排序更快”这类结论，希望熟悉两种标准库实现的人能给出解答。

测试代码

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <chrono>
#include <execution>
typedef unsigned long long uint64;
static uint64 _seed64 = 1;

static void srand64(uint64 seed) {
    _seed64 = seed;
}

static uint64 rand64(void) {
    _seed64 = (_seed64 * 6364136223846793005ULL) + 1442695040888963407ULL;
    return (uint64) _seed64;
}

int main() {
    srand64(77);
    uint64 N = 100000000;
    std::vector<uint64> v;
    for (uint64 i = 0; i < N; i++) {
        v.push_back(rand64());
    }
    std::chrono::system_clock::time_point t_beg = std::chrono::system_clock::now();

    std::sort(v.begin(), v.end());

    std::chrono::system_clock::time_point t_end = std::chrono::system_clock::now();
    std::chrono::duration<double, std::milli> ms = t_end - t_beg;
    std::cout << "C++: " << ms.count() << " ms" << std::endl;
}

Rust

use std::time::Instant;

type Uint64 = u64;
static mut SEED64: Uint64 = 1;
fn srand64(t: u64) {
    unsafe {
        SEED64 = t;
    }
}
fn rand64() -> Uint64 {
    unsafe {
        SEED64 = SEED64
            .wrapping_mul(6364136223846793005)
            .wrapping_add(1442695040888963407);
        SEED64
    }
}

fn main() {
    srand64(77);
    let n: usize = 100_000_000;
    let mut v: Vec<Uint64> = Vec::with_capacity(n);

    for _ in 0..n {
        v.push(rand64());
    }

    let t_beg = Instant::now();
    v.sort_unstable();
    let elapsed = t_beg.elapsed();
    println!("Rust: {:.3} ms", elapsed.as_secs_f64() * 1000.0);
}

解答

1. 算法差异是核心因素之一

Rust的sort_unstable基于ipnsort（衍生自pdqsort），C++std::sort多采用内省排序，两者核心设计差异显著：

ipnsort/pdqsort针对真实场景做了大量优化：快速排序阶段会动态调整pivot选择（比如采样多元素取中位数），减少最坏情况出现；递归深度超阈值时，不会直接切换堆排序，而是用更高效的方式处理小片段数据。
内省排序设计更保守，核心是保证O(n log n)最坏时间复杂度，pivot选择通常较简单（比如首/尾/中间元素），面对部分数据分布时分区效率不如ipnsort。

2. Rust对原始类型的特化更激进

Rust标准库对sort_unstable针对u64这类原始类型做了高度特化：

直接跳过通用比较逻辑，生成针对特定类型的机器码，避免函数调用开销；
利用CPU的SIMD指令进行批量比较和交换，进一步提升效率。
而多数C++标准库实现的std::sort特化程度较低，通用模板带来的开销在大规模数据排序时会被放大。

3. 分支预测、分区与重复元素处理的优化

分支预测友好性：ipnsort的代码路径更规整，减少不可预测分支。比如分区时尽量让比较结果更有规律，帮助CPU分支预测器做出正确判断；内省排序的递归深度检查、堆排序切换等分支相对不可预测。
重复元素处理：ipnsort专门针对大量重复元素场景优化，检测到分区后两边存在大量重复元素时，会跳过递归改用高效方式处理；传统内省排序无此优化，面对重复元素多的数据时效率明显下降。
分区策略：ipnsort采用双向扫描+减少交换次数的分区算法，比内省排序常用的Hoare或Lomuto分区更少产生缓存失效，提升内存访问效率。

4. C++ `std::sort`性能更优的场景

虽然Rust的sort_unstable多数场景更快，但C++也有反超情况：

稳定排序场景：Rust的稳定排序sort基于timsort，而部分C++标准库（如MSVC的STL）的std::stable_sort针对部分有序数据优化程度很高，可能比Rust稳定排序更快。
极小数据量排序：当排序元素数量极少（几十以内），内省排序切换插入排序的逻辑比ipnsort更简单，开销更低。
接近完全有序的数据：部分C++std::sort实现会检测这种情况并切换插入排序，而ipnsort的检测逻辑有额外开销，此时C++实现可能更快。

内容的提问来源于stack exchange，提问作者KimBomm

为何Rust的sort_unstable比C++ std::sort性能高出数倍？

基准测试结果 #

问题描述 #

测试代码 #

C++