6× faster binary search: from compiled code to mechanical sympathy
28 points by itamarst
28 points by itamarst
Every time I read a post about faster binary search, I feel obligated to bring up one of the most in-depth articles I've read: https://curiouscoding.nl/posts/static-search-tree/
That is awesome, thank you!
Not mentioned in the article, but the real-world use case is not a high priority for optimizing anymore, even if there is more to be done (I stopped after step 1). It's just part of a larger algorithm, and other parts are much more of a bottleneck at this point, and moreover with parallelism the benefits of faster binary search (or equivalent) get undermined by memory bandwidth becoming a bottleneck.
And also this was just a side-quest, my current main project is fixing thread oversaturation.
My big picture takeaway is that most software projects could be an order of magnitude faster with enough effort. And most of the time it doesn't matter, but for some widely used open source it's massively impactful... and woefully underfunded.
So much this. Every time I see someone optimizing binary search, my first thought is: don't do binary search. You can add vectorization, and ad-hoc branchless logic, and parallelism, and so on, but most of the time you can simply choose a different layout and achieve the same performance with much better maintainability.
In the real motivating case this really was a small change +54, -15, https://github.com/scikit-learn/scikit-learn/pull/34194/changes
If this was in a decent programming language like Rust I might've seen if there's a library to create Eytzinger layout, or made my own, but given it's in bastard C I just want to do a simple change that makes it faster.
That makes total sense! I erroneously assumed you used vectorization in Python as well, simply making the code branchless is very reasonable.
Second, notice the calculation for half/remaining_size is exactly the same for every single binary search. That’s wasted work. So I’m going to try to precalculate those values, doing less computational work.
This seems to be replacing a single right-shift instruction by a memory load. Is this really an optimisation? Surely the CPU has ample IPC headroom here to squeeze in a single shr at zero cost.
My memory is that when I did that its own, it sped things up slightly, but either I misremember or that it was slightly different version of the code—You are correct, I tried just now and it does seem not to do much, yeah, you do indeed get slightly higher IPC without precalculating so same speed.
So I will try to update the article.
The only problem then is presentation of safety invariants, which are easier to see with the current pre-calculating halves. So I might just keep the code as is and tweak the explanation. But I'll think about it.