new UniformInt bound checks

[TheIronBorn]

The previous version of UniformInt allowed the compiler to remove bounds checks. It can't do the same for our new widening multiply method.

You can verify with RUSTFLAGS='--emit=asm' cargo build --release:

extern crate rand;
use rand::{XorShiftRng, Rng};

pub fn foo(rng: &mut XorShiftRng) -> usize {
    let arr = [1; 77];
    // `rand = "0.4"`, no bounds checking
    // `rand = "0.5"`, bounds checking
    arr[rng.gen_range(0, arr.len())]
}

Is there something we could do to fix this? A change in UniformInt? Some sort of compiler hint? Or would this require a smarter compiler?

If we can't fix it, perhaps we should document this behavior. We should consider ways to mitigate the problem, such as using unchecked indexing in library code like shuffle, choose, etc.

[dhardy]

I guess this is a side-effect of the way compiler optimisations work; presumably the optimiser knows that x % y < y for positive y and non-negative x. In theory it shouldn't be hard to prove that x * y / X < y where y is positive and x < X, but the wmul implementation is potentially more convoluted (though probably not in common cases).

The new code is here and here. @alexcrichton any ideas, or know who better to ask?

[TheIronBorn]

There is some work on a standard u32/u64::wide_mul. Perhaps that could help.

[TheIronBorn]

An example which needs no rand code:

pub fn bar(rand: u64) -> usize {
    let arr = [1; 3];
    let mul = rand as u128 * arr.len() as u128;
    let hi = (mul >> 64) as u64;
    arr[hi as usize]
}

[alexcrichton]

@dhardy oh the best thing to do for something like this is to try and get a minimal example. With that it's relatively easy to inspect the LLVM IR and deduce why LLVM can't perform the optimization, and that will likely also lead to a solution one way or another. (I'm not too familiar here with the specifics, unfortunately)

[TheIronBorn]

Seems the only problem is proving the x * y / X != y case (only when the range is 3)

%1 = zext i32 %rand to i64
%2 = mul nuw nsw i64 %1, 3
%3 = lshr i64 %2, 32
%4 = icmp eq i64 %3, 3

from

pub fn bar(rand: u32, arr: [u8; 3]) -> u8 {
    let mul = rand as u64 * arr.len() as u64;
    let hi = (mul >> 32) as u32;
    arr[hi as usize]
}

https://play.rust-lang.org/?gist=da0698f29ba0d0c28c5adec4d6717a18&version=nightly&mode=release

[TheIronBorn]

>> 33 has no bounds checking

[dhardy]

>> 33 has no bounds checking

Only when it's known that arr.len() > 0 it seems?

In any case you have a valid minimal example (arr: &[u8; 3]), though I don't know whether this will generalise to the case where widening multiply has to emulate the operation due to lack of a larger type. But as long as LLVM considers u128 multiplication a simple operation, this won't matter on most platforms.

[TheIronBorn]

The widening multiply bounding technique is useful for a lot of problems, so it's likely to be used a lot in the future. It would be good if this problem were handled automatically.

Is there any chance of an upstream change in Rust/LLVM?

[TheIronBorn]

Paper describing the technique btw: https://arxiv.org/pdf/1805.10941.pdf#page=3

[TheIronBorn]

arr.len() as f64 * 0.5 works (when constant) which is similar to the technique: (range * rand / 2^32 ~= range * rand between 0 and 1).

Constant widening multiply works as well.

[TheIronBorn]

Does anyone know where I should start asking about an upstream change?

[dhardy]

Sorry, no. Perhaps @nikomatsakis has some idea how a proof of bounds can be added to widening multiply?

[vks]

Will this be fixed by #1154?

[TheIronBorn]

That new method still uses the widening multiply method so I doubt it will affect this.

[dhardy]

The widening_mul methods are still unstable (rust-lang/rust#85532).

Presumably we could use std::hint::assert_unchecked to solve this issue. Since this would add unsafe code with potential for UB (if there are bugs in our widening-mul code), I require proof of significant benefit before accepting such a PR.