Explore advanced optimization techniques for binary search algorithms in this CppCon 2022 conference talk by Sergey Slotin. Delve into branchless programming, memory layout optimization, and SIMD instructions to achieve up to 15x performance improvements over std::lower_bound. Learn how to apply these techniques to fundamental algorithms, making them significantly faster and more efficient. Discover the potential for multifold improvements in textbook algorithms and gain insights into performance engineering that can be applied to various software projects. Follow along as Slotin demonstrates the development of an optimized binary search algorithm, covering topics such as pipeline hazards, cache efficiency, memory optimization, and adaptive tree growth.
Optimizing Binary Search - Advanced Techniques and Performance Improvements
Overview
Syllabus
Introduction
Agenda
Formalization
Comparisons
Average Time
Pipeline
Hazards
Loop Condition
Cache Efficiency
Cache Lines
Memory Optimization
Ancestor Number System
Binary Tree
Example
Performance
Risk
Node Size
Vector procedure
Bitrees
Two fundamental problems
Btrees
Performance improvements
Adaptive tree growth
Layer modifications
Other data types
B3 inspired approach
Results
Question
Taught by
CppCon
