Optimizing Binary Search
summary
Claims concrete speedups over std::lower_bound with measurable tradeoffs: up to ~15× faster on small arrays and ~7× on large ones. Achieves this by replacing textbook binary search with a preprocessed layout (Eytzinger-style permutation then a B+tree-like layout whose nodes hold 16 32-bit keys to fit a 64‑byte cache line), using branchless conditional-move logic, targeted prefetching, and AVX2 vector compares producing masks so each node search is few cache-line reads and wide SIMD comparisons rather than many unpredictable branches.
AI-written summary · about
chapters (28)
- 0:00Introduction
- 1:37Agenda
- 2:47Formalization
- 3:53Comparisons
- 6:36Average Time
- 8:31Pipeline
- 9:11Hazards
- 12:29Loop Condition
- 17:57Cache Efficiency
- 18:47Cache Lines
- 19:58Memory Optimization
- 21:15Ancestor Number System
- 22:44Binary Tree
- 24:41Example
- 27:57Performance
- 31:07Risk
- 33:17Node Size
- 38:02Vector procedure
- 39:24Bitrees
- 40:22Two fundamental problems
- 41:01Btrees
- 42:16Performance improvements
- 44:52Adaptive tree growth
- 46:02Layer modifications
- 47:04Other data types
- 48:51B3 inspired approach
- 49:35Results
- 50:44Question
related talks
48m[a bit noisy] Optimizing Generic Algorithms
35mBuilding High Performance Search Indexes in Rust with SIMD
01h 01mWant fast C++? Know your hardware!
01h 01mHigh performance data structures in boost
01h 14mEfficiency with Algorithms, Performance with Data Structures
09mTrees in C++
01h 04mCPU design effects
01h 06mUtilize your CPU power