5 ms·
Idiomatic Rust? Implementing binary search (part 2)
- ridiculous_fish 5y agolet middle = (high + low) / 2; oh no! 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!
- kazinator 5y agoI'm calling the bluff here. 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.
- ridiculous_fish 5y agoYou 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 agoWhy 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 agoYou 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
- deleted 5y ago[deleted]
- leetrout 5y agoDo you have more information on this being a famous mistake? I don’t understand.
- Charon77 5y agoIt seems at the last part we're using the ordering trait so that future improvements can allow any arrays that's orderable. However the function signature still looks for [i32].