Achieving 6x Faster Binary Search Through Mechanical Sympathy and Branchless Code
Faster binary search: from compiled code to mechanical sympathy
I discovered how to make binary search six times faster by understanding CPU mechanics rather than just switching languages. By eliminating unpredictable branches that cause mispredictions in scikit-learn's gradient histogram boosting, I optimized the code to run smoothly on modern hardware. This approach demonstrates that deep knowledge of instruction-level parallelism and branch prediction can yield massive performance gains beyond simple algorithmic changes.
A reasonable mental model of Python code is that the code is executed one instruction at a time, but once you switch to a compiled language, that mental model is no longer correct.
- pillmillipedes
I think putting the buckets in eytzinger layout might help with cache locality here? though on the other hand they might all fit into cache anyways..
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.
- itamarst
When this was posted to lobsters someone shared this relevant link: https://curiouscoding.nl/posts/static-search-tree/
- wrsh07
I'm somewhat curious about the initial problem:
> Consider the following real problem, one of the steps in scikit-learn’s gradient histogram boosting algorithm:
> You have a large array of floating point numbers.
> You want to assign them to the integer range 0-254, spread out evenly.
Naively I would consider sorting the initial array and then using something like `batched` from itertools to chunk them into the 255 buckets - binary search will give you a bunch of random accesses, and sorting can be cache-oblivious (eg efficient for arbitrary data sizes)
But I'm somewhat concerned I don't fully understand the underlying problem being solved with this step, so I might be misunderstanding the intended result