The unreasonable effectiveness of modern sort algorithms
Rust: «неразумная» скорость сортировки
- Сортировка в Rust быстрее C++ и Go благодаря LLVM, агрессивному векторизатору и ручным оптимизациям.
- Алгоритм: pdqsort (pattern-defeating quicksort) + векторизованный партиционер.
- Ключевые приёмы:
- 128-битные SIMD-операции (SSE/AVX) для фильтрации элементов;
- branchless-код, предикты, минимизация кэш-промахов;
- специализированные пути для малых типов (u8, u16, u32, u64, f32, f64) и копируемых структур;
- ручная развёртка циклов, инлайн, отказ от стандартных абстракций.
- Сравнение: на случайных u64 Rust ~2× быстрее libstdc++, ~3× быстрее Go; на почти отсортированных — ещё больше.
- Память: всё делается in-place, доп. буфер 1 КБ максимум.
- Сложность: O(n log n) в среднем, O(n log n) worst-case (pdqsort гарантирует).
- Код открыт, можно подсмотреть и перенести на другие языки.