Improve bounds check elision in indexing

[bluss]

Note: We encourage higher level functionality including map, Zip, azip!() and so on before resorting indexing.

Still, it is a good benchmark to consider bounds check elision in the most trivial cases — assuming it will improve it in some less trivial cases too.

Set the goal that the following examples compile without extra bounds checks, because their loop counters are already in bounds.

pub fn test1d(a: &Array1<f64>) -> f64 {
    let mut sum = 0.;
    for i in 0..a.len() {
        sum += a[i];
    }
    sum
}

pub fn test2d(a: &Array2<f64>) -> f64 {
    let mut sum = 0.;
    for i in 0..a.rows() {
        for j in 0..a.cols() {
            sum += a[[i, j]];
        }
    }
    sum
}

• test1d_single Tweak bounds checked indexing code (Index, IndexMut) #350
• test1d
• test2d Tweak bounds checked indexing code (Index, IndexMut) #350

[chmnchiang]

Is this possible? I thought it is rust compiler's job to do this kind of optimization.

[bluss]

Sure, it is possible to a degree. It would be to write Rust code that the compiler understands like we want it to understand it.

Sure, there are some road blocks. The following doesn't even remove the bounds checks in a test where a is a &Vec<f64>, but it does with &[f64]:

    for i in 0..a.len() {
        sum += a[i];
    }

so a component of it could be to fix that as a bug in rustc.

[bluss]

To clarify, we will look for a way to implement the same thing but that the compiler optimises like we want. It requires some analysis of the current code, and experiments with actual results. Current checked indexing is relatively high level and computes a cumulative pointer offset as an optional isize, no surprise the compiler does not see through it.

To be honest I'd probably work on the vector case first.. if it can't do it we don't have much chance.

[bluss]

We can put up a lower goal to start. (Edit: This goal and a bit more was been achieved in ndarray 0.10.6 🎆)

Rewrite indexing code so that the following does not have a possible panic for bounds check:

pub fn test1d_single(a: &Array1<f64>, i: usize) -> f64 {
    if i < a.len() { a[i] } else { 0. }
}

currently there is a bounds check for this code.