A Long Journey of Changing std::sort Implementation at Scale
summary
Google replaces std::sort replacement in LLVM libc++ and measures hundreds of thousands of calls, then ships a new mix of block quicksort and ninther pivoting; performance improves up to ~50% on random ints and ~10% on strings and shows ~78% production speedup. Engineering work adds strict weak ordering checks, ASAN and debug-only sampling of the first ~100 elements plus randomized golden-tests to expose flaky expectations, fixes thousands of comparator bugs, prevents out‑of‑bounds reads, and takes months of incremental fixes and rollouts.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:05Sorting in C++ history
- 3:55Quick sort limitations
- 8:12LLVM libc++ at Google
- 10:20Good sorting algorithm
- 14:13Production failures testing
- 16:24Randomization for testing
- 21:50Stable sort determinism
- 25:29Weak ordering validation
- 33:59Debugging comparators
- 36:09Comparator bugs
- 41:30Floating-point pitfalls
- 44:01Comparator exploits
- 47:11Block quicksort PDQ
- 50:04Default sort instability
- 51:55Comparator sanitizer gains
- 52:57Improve your sorting
- 54:24Q&A
related talks
46mA little order
30mOptimising stable sort in Rust and mostly failing
48m[a bit noisy] Optimizing Generic Algorithms
01h 01mWant fast C++? Know your hardware!
59mBetter Algorithm Intuition
01h 00mSTL Features And Implementation Techniques
01h 05mThe Most Important Optimizations to Apply in Your C++ Programs
01h 05mTaming the performance Beast