- Author
- Itamar Turner-Trauring
- Published
- 11 July 2026 (last updated 18 July 2026)
- Kind
- Company blog post with a worked, benchmarked Rust example
- Original
- pythonspeed.com/articles/branchless-binary-search/
- Subject
- Systems and hardware
- Themes
- Close to the machine
What it is
Itamar Turner-Trauring wrote this for the Python Speed site. The post comes from work done at Quansight on scikit-learn. It teaches mechanical sympathy, meaning code written to suit how the CPU runs it.
What it says
- The post takes one step of scikit-learn's histogram boosting, which maps floats into 255 buckets.
- Using hardware counters, the classic binary search mispredicts 16.6% of its branches.
- A branchless search with a fixed loop count cuts the time to 9,849.3 microseconds.
- Removing bounds checks reaches 7,278.5 microseconds. Precomputing halves alone added no speed.
- Handling 16 values at once lifts instructions per cycle to 4.9, at 5,453.4 microseconds.
- The title promises an 8 times speedup, while the intro says 6 times.
What evidence it gives
The post gives full Rust code for four versions. Tables list time, instructions, branches, misprediction rate and instructions per cycle. All numbers come from one test of 1,000,000 random values and evenly spaced boundaries.
Interests and limits
The author sells a Python performance book and consulting through the site. The tests use one synthetic data set and the post names no CPU. The final code is a simplified Rust example, not the scikit-learn change itself. The post admits it only briefly introduces low-level topics.
Connections
These links are this wiki's own reading, not claims the sources make.
- C Is Not a Low-level Language. Chisnall traces speculation to chips built to keep sequential code fast. Turner-Trauring's search gets faster by no longer depending on that prediction. Handling 16 values at once then makes the essay's case on one small loop.