Module 13 · binary_search, lower_bound, upper_bound and equal_range
Under the Hood: GCC's Halving Loop, Branches and the Cache
ProReading
Kenji runs a price lookup service. Every request calls lower_bound on a sorted vector of a million prices, and his profiler says most of the time goes there. A blog post told him the library's search is branch-free, so it must already be the fastest one. Maria asks the question this lesson answers: "But why would a search have branches at all, and why would they cost anything?" We will open GCC's loop, count its comparisons and measure its branch.
Checking what this lesson needs for you…
What is inside Under the Hood: GCC's Halving Loop, Branches and the Cache
- GCC 12's lower_bound, line by line
- Why five comparisons for 100 and four for 800
- binary_search and equal_range: the same loop, plus a little
- Is the library's search branch-free? GCC 12 says no
- The performance lab: GCC's loop, the branch-free loop and a prefetch
- The cache: one block of 4 bytes a value against a node per value