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

41–50 of 155 posts

Re: Fastest branchless binary search

#41

Post by Pannoniae »

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.

Re: Fastest branchless binary search

#42

Post by creata »

Phemist wrote: post #31
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?

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 :)

Not that it makes much of a difference, but Rust does compile to 32-bit platforms.

https://doc.rust-lang.org/nightly/rustc/platform-support.htm...

Re: Fastest branchless binary search

#44

Post by Phemist »

creata wrote: post #42
Phemist wrote: post #31

Earlier quoted context omitted.

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 :)

Not that it makes much of a difference, but Rust does compile to 32-bit platforms. https://doc.rust-lang.org/nightly/rustc/platform-support.htm...

Ah yes, fair point. It makes it a bit more subtle, in that the cases where you have to worry about integer overflows on the pointer addition, are cases where you have an array of 2^((64 or 32) - 1) bools... which seems rather silly to do a binary search on?

Re: Fastest branchless binary search

#45

Post by cornstalks »

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?

> And its undefined behaviour in release mode.

No, it uses 2’s complement and is well defined in release mode. From [1]:

> When you’re compiling in release mode with the --release flag, Rust does not include checks for integer overflow that cause panics. Instead, if overflow occurs, Rust performs two’s complement wrapping.

[1]: https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...

Re: Fastest branchless binary search

#46

Post by [deleted] »

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

[deleted]

Re: Fastest branchless binary search

#48

Post by cornstalks »

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?

It’s bounded precision, but Rust limits the max size of an object/array to isize’s max[1], not usize’s max. So adding two isize::MAX values using usize will never overflow.

[1]: https://doc.rust-lang.org/stable/reference/types/numeric.htm...

Re: Fastest branchless binary search

#49

Post by someplaceguy »

epilys wrote: post #21
quietbritishjim wrote: post #12

Earlier quoted context omitted.

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, saf…

Furthermore, it's an optional optimization (you could just copy the code and replace the unsafe access with a safe one, if you're paranoid) and it's not like if you write it in C++ it will be any safer than Rust's unsafe?!
Post reply on HN