Idiomatic Rust? Implementing binary search (part 2)
shane-o.dev
shane-o.dev
let middle = (high + low) / 2;
This (famous) mistake risks overflow in the intermediate calculation. `low + (high - low) / 2` is a common trick to avoid it.
Rust can only do so much!
32 bit:
middle, high and low can be 32 bit unsigned integers. The array we are bisecting has entries that are at minimum four bytes; we are not going be binary searching an array of 8 bit bytes.
But, suppose we are binary searching bytes. We can limit the integers to 31 bit range, so our array is restricted to 2GB. Adding 31 bit integers in 32 bit width does not overflow. Binary searching through a 2GB array of bytes is an unlikely application of the binary search. There are only 256 unique values, surely some better structure can be found. The 2GB limit seems generous. On some 32 bit OSes, that was about you could get in user space.
Suppose we are not searching through bytes, but through an array of pointers, or 32 bit integers or 32 bit floats or something useful that is plausibly subject to binary searching. The array can only have one billion entries in it, assuming our OS would let us use the entire 4GB address space. That is to say, the indices are at most 28 bit integers. high + low absolutely does not overflow 32 bits.
64 bit:
We make high and low 64 bits wide. We positively do not have an array in which high uses anywhere near all 64 bits, and therefore high + low does not overflow.
16 bit:
Similar analysis to 32. If the array is of bytes, 16 bit indices let us have a 32768 element array without high + low overflow. That's half the memory. If the elements are two bytes or larger, the overflow problem is nonexistent.
16 bit with 8 bit registers:
Here is where we have a problem. mid, high and low are 8 bit values from 0 to 255. We have arrays that large. We'd like to do the bisecting arithmetic entirely in 8 bit. Hello, low + (high - low) / 2.
https://play.rust-lang.org/?version=stable&mode=debug&editio...
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;
mid = (char) (((int) high + (int) low) / 2);
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.
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.
Would that be just to prototype something before going to other data structures, or in production too?
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;https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
However the function signature still looks for [i32].