[a bit noisy] Optimizing Generic Algorithms
summary
Claims concrete wins and the measurement setup: use Google Benchmark and perf on a single compiler/machine, watch for code alignment effects. Replacing midpoint with half_non_negative yields about 30% faster lower_bound on integers. Unrolling the merge loop cuts branches and speeds merge roughly a third. Sorting pointers then rearranging the array drastically reduces moves (order-of-magnitude fewer), but pays in cache locality; validate with targeted benchmarks and stabilizer/perf permutations.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 2:48Microbenchmarking pitfalls
- 7:51Binary search optimization
- 15:41Merge optimization
- 25:45Stable sort optimizations
- 37:06Generic component strategies
- 41:24Q&A
related talks
58mOptimizing Binary Search
57mA Long Journey of Changing std::sort Implementation at Scale
01h 01mWant fast C++? Know your hardware!
01h 00mIntroduction to Hardware Efficiency in Cpp
01h 05mThe Most Important Optimizations to Apply in Your C++ Programs
04mZero-Overhead Compiler Pessimization
01h 06mUtilize your CPU power
46mA little order