4 ms·

You have to think smaller! Here's a binary search that trips over intermediate overflow. You can run it and everything! https://play.rust-lang.org/?version=sta

You have to think smaller! Here's a binary search that trips over intermediate overflow. You can run it and everything! https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e8b017021bf34361533e56654084d0e3 https://play.rust-lang.org/?version=stable&mode=debug&editio...

kazinator 5y ago
Why would anyone do a silly thing like work with integers smaller than the register size of the machine? Yet, even C gets this sort-of right, in an obsolescent way. When integer types narrower than int are manipulated in expressions, they promote to either int or unsigned int (whichever can represent the original type's value range). So for instance, this doesn't overflow, unless sizeof(char) == sizeof(int). char mid, high, low; ... mid = high + low / 2; Reason being that this is actually doing something like: mid = (char) (((int) high + (int) low) / 2); (When sizeof(char) == 1, we are almost certainly on some DSP chip, where char is wider than 8 bits possibly as much as 32. Portable code using unsigned for array indexing would not assume that it goes beyond 255.) It would be useful in a C like language if the declaration of a custom integer type could separately specify promotion semantics (possibly that it has none). I would make it the default behavior that all integer values promote to the widest available type in their signedness. (E.g. the thing that corresponds to intmax_t or uintmax_t in C). If someone wanted to optimize around that (due to the widest type not being the fastest, say), they could declare a custom type that promotes to something narrower, or doesn't promote.
- ridiculous_fish 5y ago
  You misunderstood! In my code, all arithmetic is performed with 64-bit unsigned integers. The "trick" is a type whose size is zero bytes. If T is size zero, Vec<T> does not allocate any memory: it just keeps a count. You can make a Vec<()> with usize::max() for free, if you can finesse the compiler. The binary search itself does not access any memory: it's just pure arithmetic, and it overflows.
  - kazinator 5y ago
    How do you use this object in an application, such that it's useful to do a binary_search on it and part of the application? Would that be just to prototype something before going to other data structures, or in production too?
rstuart4133 5y ago
I get your point, but you have cardinality(usize) elements in your array. So you need to use an indexing type and operations that let you exploit that full cardinality. usize does have the required range, but then you combine it with std::ops::Add(). In this case std::ops::Add()'s overflow check just gets in the way, preventing you from fearlessly exploiting all 64 bits in the usize. Had you used usize.wrapping_add(), it would not only have not hit the overflow panic, it would have been faster. Maybe that's your point? The final version of his code is indeed buggy, because middle should have been calculated like this: let middle = high.wrapping_add(low) / 2;

kazinator 5y ago

Why would anyone do a silly thing like work with integers smaller than the register size of the machine? Yet, even C gets this sort-of right, in an obsolescent way. When integer types narrower than int are manipulated in expressions, they promote to either int or unsigned int (whichever can represent the original type's value range). So for instance, this doesn't overflow, unless sizeof(char) == sizeof(int). char mid, high, low; ... mid = high + low / 2; Reason being that this is actually doing something like: mid = (char) (((int) high + (int) low) / 2); (When sizeof(char) == 1, we are almost certainly on some DSP chip, where char is wider than 8 bits possibly as much as 32. Portable code using unsigned for array indexing would not assume that it goes beyond 255.) It would be useful in a C like language if the declaration of a custom integer type could separately specify promotion semantics (possibly that it has none). I would make it the default behavior that all integer values promote to the widest available type in their signedness. (E.g. the thing that corresponds to intmax_t or uintmax_t in C). If someone wanted to optimize around that (due to the widest type not being the fastest, say), they could declare a custom type that promotes to something narrower, or doesn't promote.

ridiculous_fish 5y ago
You misunderstood! In my code, all arithmetic is performed with 64-bit unsigned integers. The "trick" is a type whose size is zero bytes. If T is size zero, Vec<T> does not allocate any memory: it just keeps a count. You can make a Vec<()> with usize::max() for free, if you can finesse the compiler. The binary search itself does not access any memory: it's just pure arithmetic, and it overflows.
- kazinator 5y ago
  How do you use this object in an application, such that it's useful to do a binary_search on it and part of the application? Would that be just to prototype something before going to other data structures, or in production too?

rstuart4133 5y ago

I get your point, but you have cardinality(usize) elements in your array. So you need to use an indexing type and operations that let you exploit that full cardinality. usize does have the required range, but then you combine it with std::ops::Add(). In this case std::ops::Add()'s overflow check just gets in the way, preventing you from fearlessly exploiting all 64 bits in the usize. Had you used usize.wrapping_add(), it would not only have not hit the overflow panic, it would have been faster. Maybe that's your point? The final version of his code is indeed buggy, because middle should have been calculated like this: let middle = high.wrapping_add(low) / 2;