Faster binary search: from compiled code to mechanical sympathy | Hacker News Reader

Faster binary search: from compiled code to mechanical sympathy

pythonspeed.com

71 pointsenz15 comments

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.

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.

Binary search is log time but otherwise pretty awful. If you don’t specifically need a sorted array, use something like a B-tree instead.

> I'd also want to try interpolation search for this

Years ago, when ORC unwinding tables were being implemented for the Linux kernel, the main performance bottleneck was binary search to turn a virtual address into an unwind record. I suggested adding a little array to reduce the range to be binary searched, and this was a huge speed up.

The same trick could work for floats as in the article: use an order-preserving float to int mapping and find the range of mapped integers that actually exist in the data set. Divide it equally into, say, a few thousand buckets. For each bucket, record the first index in the actual table that corresponds to that bucket. Then, to look up an actual entry, query two adjacent table entries to find the subrange that needs to be binary searched and search that.

The benefit will depend on the distribution of the table. In the best case it will eliminate the log factor entirely and make each lookup take a small constant number of queries.

I imagine a similar trick could be used with B-trees, but it would be more complex.

There's only 254 entries to search from. No locality issue in sight.

When this was posted to lobsters someone shared this relevant link: https://curiouscoding.nl/posts/static-search-tree/

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

The bucket boundaries are often chosen from a random sample of the data, if the input data is very large. Sorting is O(nlogn), but using binary search per value to assign a bucket is O(n), plus the cost of creating the buckets on a sample. So once you hit a large enough number of values this scales better.

Binary search does give random access but in this case there's only up to 255 buckets typically, so it's random access on cached memory.

Can you say more about what happens for bucket assignment? Eg is it appending to a file or writing to a 2d array?

Agreed on linear vs n log n, ofc, and streaming considerations might also be relevant

This bit is interestingly unintuitive - to go faster, do more iterations:

> As far as the number of while loop iterations, I’m instead going to iterate a fixed number of times, log2 of the number of buckets. For some value this might involve a bit more work, if previously the bucket would be found in an iteration or two, but the saving in speed from avoiding branch mispredictions will make it worth it.

For small arrays that can fit in L1 cache, it's ok to do more loops. For bigger arrays, cache miss could remove all the gains.

Regardless of the array's size, the expected win from early exit on random keys is a constant number of iterations.

<code> let middle = min_idx + ((max_idx - min_idx) / 2); </code>

Respect!

“ 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.

Literally bullet 2:

> 2. Use a compiled language to write a Python extension.

It's fine to be grumpy about languages, but python is the de facto standard in many industries, and a lot of people don't get to choose.

So, yes, asking "how do you speed up computational python code?" is a good, fine, normal question.

The point of python is to be a scripting language. Writing the main code in a systems languages and making it available to python is a very promising way of using it.

Reply on news.ycombinator.com