turbosort

SIMD-accelerated radix sort for primitive types in Rust.

Performance

Benchmarked on an Intel i7-8665U (4C/8T, AVX2) with random data, full-sample criterion runs. Large arrays carry roughly ±15% run-to-run variance from thermal throttling on this 15W chip, so the speedup ratios are steadier than the absolute times. Run cargo bench (add --features parallel for the parallel benchmarks) to reproduce.

Serial — u32

The algorithm dispatch table (see below) explains the mid-range dip: sizes 128–512 fall in the quicksort + SIMD-leaf tier, where std::sort_unstable still wins because its branch predictor warms up quickly on sorted sub-runs. Once arrays exceed ~4K elements the LSD radix pass takes over and turbosort pulls ahead, reaching 2.4x over std and 1.4x over voracious at 10M. Small arrays (n ≤ 16) sort through branch-free AVX2 sorting networks.

Serial — u64

u64 is a 2-pass radix sort (two 32-bit halves). At 4K–1M the double-scatter cost shows: turbosort trails std by ~10% and voracious (which uses a wider radix for 64-bit keys) by ~37%. If you sort large volumes of u64, prefer voracious or std::sort_unstable.

Serial — f32

Floats require a sign-flip step (IEEE 754 negative numbers sort backwards in bit-order), but turbosort absorbs that into the radix pass. The result is a strong win: 2.9x over std at 1M.

Serial — i32

Signed integers use a bias step to remap the sign bit before radix sorting. At 1M elements turbosort reaches 2.55x over std and 1.57x over voracious.

Parallel (turbosort::sort_parallel, requires parallel feature)

sort() is always single-threaded; sort_parallel() is the opt-in multi-core path. It splits the histogram and scatter phases across cores without locks or atomics. On these four cores the gain is real but sub-linear: about break-even at 1M (setup cost cancels the work saved), rising to 1.21x over serial at 10M, where it reaches 3.1x over std. The scatter phase is bound by memory bandwidth rather than compute, so extra cores help less than they would for a CPU-heavy workload.

Usage

// Sort any primitive numeric type
let mut data = vec![5u32, 3, 8, 1, 9, 2, 7, 4, 6];
turbosort::sort(&mut data);
assert_eq!(data, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);

// Signed integers
let mut v = vec![3i32, -1, 4, -1, 5, -9];
turbosort::sort(&mut v);
assert_eq!(v, vec![-9, -1, -1, 3, 4, 5]);

// Floats (total order: -inf < -0.0 < +0.0 < +inf < NaN)
let mut v = vec![1.0f32, f32::NAN, -0.0, 0.0, f32::NEG_INFINITY];
turbosort::sort(&mut v);
assert_eq!(v[0], f32::NEG_INFINITY);
assert!(v[4].is_nan());

// Zero-allocation sorting with caller-provided buffer
let mut data = [42u64, 7, 99, 1, 0];
let mut buf = [0u64; 5];
turbosort::sort_with_buffer(&mut data, &mut buf);

Supported types

All 10 primitive numeric types: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64.

Algorithm dispatch

With the parallel feature, sort_parallel() hands arrays larger than 131K to rayon. See the parallel benchmarks above.

Features

[dependencies]
turbosort = "0.1"

# For parallel sorting:
turbosort = { version = "0.1", features = ["parallel"] }

For no_std, disable default features and call sort_with_buffer() with your own scratch buffer.

Architecture support

On x86_64, turbosort detects AVX2 at runtime via CPUID, so one binary runs on any CPU.

License

Dual-licensed under MIT or Apache 2.0.