4 ms·

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 pr

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 3y ago
[deleted]
josephg 3y ago
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 3y ago
  [deleted]
- marcianx 3y ago
  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.
- cornstalks 3y ago
  > 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#integer-overflow https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...
Phemist 3y ago
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 :)
- creata 3y ago
  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.html https://doc.rust-lang.org/nightly/rustc/platform-support.htm...
  - Phemist 3y ago
    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?
vulcan01 3y ago
In debug mode, integer overflow panics. In release mode, overflow does occur; that's why checked_add and friends exist.
cornstalks 3y ago
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.html#machine-dependent-integer-types https://doc.rust-lang.org/stable/reference/types/numeric.htm...
- LegionMammal978 3y ago
  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.
quietbritishjim 3y ago
> 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).

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 3y ago

[deleted]

josephg 3y ago

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 3y ago
[deleted]
marcianx 3y ago
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.
cornstalks 3y ago
> 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#integer-overflow https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...

Phemist 3y ago

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

creata 3y ago
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.html https://doc.rust-lang.org/nightly/rustc/platform-support.htm...
- Phemist 3y ago
  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?

vulcan01 3y ago

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

cornstalks 3y ago

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.html#machine-dependent-integer-types https://doc.rust-lang.org/stable/reference/types/numeric.htm...

LegionMammal978 3y ago
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.

quietbritishjim 3y ago

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