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

31–40 of 155 posts

Re: Fastest branchless binary search

#31

Post by Phemist »

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?

Left and right are both usizes, which are 64-bit pointers. You will need work on an array of 2^63 elements before you have to worry about integer overflow issues.

This array would not fit in any kind of memory for the foreseeable future :)

Re: Fastest branchless binary search

#32

Post by vulcan01 »

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?

In debug mode, integer overflow panics. In release mode, overflow does occur; that's why checked_add and friends exist.

Re: Fastest branchless binary search

#36

Post by fn-mote »

andyg_blog wrote: post #25

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.

Can you do binary search without random access? I would not expect so. Am I missing a point that someone could explain?

Re: Fastest branchless binary search

#37

Post by marcianx »

josephg wrote: post #30
abhishekjha wrote: post #27

Earlier quoted context omitted.

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?

I'm pretty sure it's not undefined behavior in rust in release mode if it does overflow. It's fully specified behavior, I believe.

Re: Fastest branchless binary search

#38

Post by eru »

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…

> Also, what's wrong with C?

Oodles and oodles of undefined behaviour, for example.

C ain't clean.

Re: Fastest branchless binary search

#39

Post by [deleted] »

josephg wrote: post #30
abhishekjha wrote: post #27

Earlier quoted context omitted.

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?

[deleted]

Re: Fastest branchless binary search

#40

Post by klysm »

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 reply on HN