Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fastest branchless binary search

mhdm.dev

Post reply on HN
Print view View original

1–10 of 155 posts

Re: Fastest branchless binary search

#2

Post by foldr »

>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩

I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.

Re: Fastest branchless binary search

#3

Post by shmageggy »

> If only there was a clean fast bare-metal language to write all this in..

The author includes a footnotes for "BUT RUST.." and "BUT ZIG..", but how about Nim? Looks like there is a native library implementation of `lowerBound` https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al... Yes, it's not a "bare-metal" language, but it compiles to one (or two), so it would be interesting to see what it compiles to here.

Also, what's wrong with C?

Re: Fastest branchless binary search

#5

Post by twoodfin »

foldr wrote: post #2

>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.

Presumably it’s not about matching the dynamic branch prediction estimate but rather exploiting static (or profile-provided) information to assist other optimizations.

Inlining seems like a natural application: Inlining is perhaps the most critical optimization to get right, and getting it right is a complex balance of frequency of use vs. added code bloat and associated further optimization cost. Having more than one bit of branch-likelihood as input to these decisions could easily be helpful.

Re: Fastest branchless binary search

#6

Post by matklad »

shmageggy wrote: post #3

> If only there was a clean fast bare-metal language to write all this in.. The author includes a footnotes for "BUT RUST.." and "BUT ZIG..", but how about Nim? Looks like there is a native library implementation of `lowerBound` https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al... Yes, it's not a "bare-metal" language, but it compiles to one (or two), so it would be interesting to see what it compiles to h…

> BUT ZIG.. There’s no binary search implementation in Zig that I could find, rather it calls to C++.

Zig’s binary search is here, it’s an unoptimized textbook version: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

At TigerBeetle, we have our own branchless implementation here:

https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...

Re: Fastest branchless binary search

#7

Post by gpderetta »

foldr wrote: post #2

>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.

I think it is used for code layout: typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted.

I also tried (and failed) to use expect with probability to generate a cmov, but in retrospect it is obvious: the parameter is not the prediction probability, but the taken/not-taken probability, and even a branch that goes either way with 50% probability can still be predicted perfectly (for example a branch that switches every other iteration), so the parameter can't be used to decide between predication and prediction.

edit: what we really need is an [[unpredictable]] attribute.

Re: Fastest branchless binary search

#8

Post by djoldman »

Interesting that the results don't hold up with a more complicated comp comparison function:

> For somewhat realistic scenarios of binary searching with a slower comp() function I’ve thought of searching through ids, phone numbers, accounts and keywords. I’ve thus settled on testing searching 8-byte strings.

> ...

> In this case std::lower_bound is very slightly but consistently faster than sb_lower_bound. To always get the best performance it is possible for libraries to use sb_lower_bound whenever directly working on primitive types and std::lower_bound otherwise.

I would like to see the analysis here.

Re: Fastest branchless binary search

#9

Post by LoganDark »

Does anyone know where the "BUT RUST" link was supposed to lead? It seems to be already out of date due to being unversioned, I can't tell whether it's supposed to lead to the middle of the `starts_with` doc comment or not.
Post reply on HN