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

21–30 of 155 posts

Re: Fastest branchless binary search

#21

Post by epilys »

quietbritishjim wrote: post #12
LoganDark wrote: post #9

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.

Looking at the archive.org captures just before [1] and just after [2] the article was published, it looks like it was meant to be this line of code, now on line 2779 [3]: let mid = left + size / 2; [1] https://web.archive.org/web/20230602210213/https://doc.rust-... [2] https://web.archive.org/web/20230709221353/https://doc.rust-... [3] https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779

So this is basically a *safe* optimization, since the index will always be valid and there's no need for the compiler to do a check and unwrap, panic.

This is how unsafe {} should be used. Sometimes some things are true but the compiler can't know that. And here the unsafe {} means that it dereferences a raw pointer (the index that we know is valid). If the unsafe {} safety condition is valid, unsafe {} is, well, safe.

Re: Fastest branchless binary search

#23

Post by w0mbat »

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.

Re: Fastest branchless binary search

#24

Post by gpderetta »

pclmulqdq wrote: post #17
djoldman wrote: post #8

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…

I believe this happens because branch prediction lets you pipeline multiple simultaneous comparisons, and rewind whenever the branch predictor is wrong (about half the time for truly random data and inputs). The CMOV approach blocks after each comparison function due to the data dependency. On average, you're doing two comparisons at a time with branches, and one with CMOV, so when comparison time is greater than bra…

Switching to an N-way search (for N>2) could help extract the lost parallelism. At the cost of touching more cachelines though, so it is not necessarily a win.

Re: Fastest branchless binary search

#25

Post by andyg_blog »

This is not a valid drop in replacement for lower_bound. Accessing iterators as front[index] is only for random access iterators like vector has. The author may have realized this if they benchmarked on other containers.A forward iterator must be advanced and then dereferenced.

Re: Fastest branchless binary search

#26

Post by josephg »

matklad wrote: post #6
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...

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.

Re: Fastest branchless binary search

#27

Post by abhishekjha »

josephg wrote: post #26
matklad wrote: post #6

Earlier quoted context omitted.

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

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?

Re: Fastest branchless binary search

#28

Post by [deleted] »

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?

[deleted]

Re: Fastest branchless binary search

#30

Post by josephg »

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?

Integer overflows cause panics in debug mode. And its undefined behaviour in release mode.

Where do you see that in the code? I can't see (left+right)/2 anywhere in the code I linked?

Post reply on HN