Hacker News Reader

Comment by abhishekjha | Hacker News Reader

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?

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.

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

Reply on news.ycombinator.com