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
I noticed that Rust’s sorting functions, especially sort_unstable, often seem significantly faster than C++’s std::sort in benchmarks.
I understand that Rust’s sort_unstable is based on ipnsort (previously pdqsort-related work), while C++ implementations of std::sort are typically introsort-based depending on the standard library implementation.
What specifically makes Rust’s implementation faster in practice?
Is it mainly due to algorithmic differences (ipnsort vs introsort)?
Is it because Rust specializes more aggressively for primitive types?
Does branch prediction, partitioning strategy, or handling of duplicates make the main difference?
Are there cases where C++ std::sort should perform similarly or even better?
I’m especially interested in implementation-level reasons rather than just “unstable sort is faster than stable sort.”
Would appreciate insights from people familiar with both standard library implementations.
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);
}
