6× faster binary search: from compiled code to mechanical sympathy(pythonspeed.com)
pythonspeed.com
6× faster binary search: from compiled code to mechanical sympathy
https://pythonspeed.com/articles/branchless-binary-search/
3 コメント
Better guesses reduce the number of guesses, so there will be less branch misprediction, but there will still be mispredictions for each remaining branch. So I would guess branchless interpolation search would still help.
In practice because the real code in scikit-learn is used in parallel, memory bandwidth starts being a problem in real usage. Plus, in the overall algorithm (this is just a small part) the time spent on binary search is now low enough that there are other, more significant bottlenecks elsewhere. So in practice the branchless optimization had enough impact on the original motivating code base that there didn't seem much point spending more time on it.
In practice because the real code in scikit-learn is used in parallel, memory bandwidth starts being a problem in real usage. Plus, in the overall algorithm (this is just a small part) the time spent on binary search is now low enough that there are other, more significant bottlenecks elsewhere. So in practice the branchless optimization had enough impact on the original motivating code base that there didn't seem much point spending more time on it.
“ How do you speed up computational Python code? A common, and useful, starting point is”
A better starting point is: use a better language. Python is terrible and unbearably slow. If you need anything serious or performant, switch to something else.
A better starting point is: use a better language. Python is terrible and unbearably slow. If you need anything serious or performant, switch to something else.
I'd also want to try interpolation search for this (not necessarily linear interpolation since we're doing floats) - you can take much better guesses than "it's in the middle somewhere" by not having to look at the data through a 1-bit-wide pinhole as comparison algorithms do.