Fastest branchless binary search

Post by gpderetta » Fri, Aug 11, 2023, 2:10 PM UTC

Pannoniae wrote: post #41

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.

Read https://en.algorithmica.org/hpc/pipelining/branching/ and the following chapter. TL;DR: you can generate different, and more efficient code if you know how much it is going to be mispredicted.

Post by quietbritishjim » Fri, Aug 11, 2023, 2:16 PM UTC

abhishekjha wrote: post #27

josephg wrote: post #26

Earlier quoted context omitted.

Rust's binary search is here. Also a pretty textbook version of the function: https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c... How much faster is the branchless version in practice? I make heavy use of binary search in some code I maintain, and I wonder if it would make much of a difference to switch to a more efficient version of the function.

I don't know much about Rust data types or Rust in general but does it not have any integer overflow? I see (left+right)/2. Is it like python with unbounded precision?

   let mid = left + size / 2;

Post by commandlinefan » Fri, Aug 11, 2023, 2:23 PM UTC

klysm wrote: post #40

w0mbat wrote: post #23

Is that still lower_bound? Maybe I am misreading the code but it looks like this returns any match, not the earliest match (when there are dupes). It’s common to have multiple matches even in a unique list if the comparison function is say looking for a certain string prefix to do autocomplete, but we want the earliest in the list.

I guess it’s good to have the option of not caring if you want even more speed

Post by JonChesterfield » Fri, Aug 11, 2023, 2:31 PM UTC

Post by plagiarist » Fri, Aug 11, 2023, 2:53 PM UTC

jfk13 wrote: post #66

commandlinefan wrote: post #65

Earlier quoted context omitted.

Or, less contentiously - if you know you don't care/don't need to disambiguate dups, look how much efficiency you're losing on a case that isn't important. The most common argument against optimization is "just use the existing code", but the "existing code" _always_ attempts to handle special edge cases that probably don't apply in your case. We programmers waste a lot of end-user time saving a bit of programmer tim…

On the other hand, assuming it's OK to ignore the special edge cases (or not even thinking of them) can come back to bite you (or your users) when eventually one of them does show up in a situation you didn't anticipate.