Hacker News Reader

Comment by matklad | Hacker News Reader

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

View on HN

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.

Rust's binary search used to be branchless but due to some issues down in LLVM land, the codegen doesn't issue a `cmov` where it should. https://github.com/rust-lang/rust/issues/53823

old branchless version: https://github.com/rust-lang/rust/pull/45333/files

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

Such an overflow could still be problematic for slices of zero-sized types, which can contain up to usize::MAX elements, since the total size in bytes is always 0. But (left + right) / 2 doesn't actually occur anywhere in the code, only left + size / 2, which clearly can't overflow as long as size is sane.

> I see (left+right)/2.

There is no (left+right)/2 on that page.

   let mid = left + size / 2;

It's only size that is being divided by 2, which is the size of the segment still under consideration (which is initially the whole array). left is the starting index of segment still under consideration (which is initially 0).

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?

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

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

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.

Reply on news.ycombinator.com