Optimizing Binary Search
People generally don’t get very excited over 5-10% performance improvements in some databases. Yes, this is what software engineers are paid for, but these types of optimizations tend to be too intricate and system-specific to be readily generalized to other software.
Instead, the most fascinating showcases of performance engineering are multifold improvements of textbook algorithms: the kinds that everybody knows and deemed so simple that it would never even occur to try to optimize them in the first place. These optimizations are simple and instructive and can very much be adopted elsewhere — and they are surprisingly not as rare as you would think.
In this talk, we will focus on one such fundamental algorithm — binary search — and discuss several ways of making it faster using branchless programming, memory layout optimization, and SIMD instructions, and eventually develop an algorithm that is up to ~15x faster than std::lower_bound.
Sergey Slotin
Sergey Slotin is the author of Algorithms for Modern Hardware (en.algorithmica.org/hpc).