[brundolf]

One thing that I assume reduces this problem even further is the prevalent use of iterators in Rust. I almost never index an array or vector directly, which means it's impossible for me to use an out of bounds index, and I'd be really surprised if rustc and/or LLVM don't somehow take advantage of that fact (maybe just through unchecked indexing in the standard library's iterator functions)

[oconnor663]

I think LLVM is smart enough to optimize regular `for i in 0..stuff.len()` loops into the same assembly as `for i in &stuff` loops in almost all cases. I imagine this sort of "we can tell that i is always less than len" optimization is a big contributor to the low cost of bounds checks. In some large portion of cases where they're not needed, the optimizer can already see that.

[ridiculous_fish]

IME loops with induction variables (integer indexes) often produces better codegen than with iterators. Compare the these two Rust functions for inverting bits: https://rust.godbolt.org/z/cE4vPdbdY

This got improved in Rust 1.65 just this month, but the point stands.

edit: ARM64 compilation is even sillier. https://rust.godbolt.org/z/PEsbeGxWP

[akshaykarthik]

Interestingly enough, with `-C opt-level=3` both functions yield the same assembly.

I wonder if there's some pass that's missing or not done at the lower opt level.

[masklinn]

Might be a problem of the number of pass repetitions, where O2 does not rerun the vectorisation after whatever manages to unroll everything but O3 does.

[brundolf]

Yeah, I wondered about those too. Less straightforward than pure iterator usage but still plausible

[tialaramex]

Yes, for example the relatively modern (didn't exist two years ago) implementation of IntoIterator for arrays themselves, gives you an iterator which doesn't use bounds checks since it is going to give exactly each of the things in the array once and it knows exactly how many of them there are.

[est31]

It will still implement that with a loop over the array where there is a (bounds) check for the integer when it's being incremented (the i < len in int i; for(i = 0; i < len; i++)). That's no different from a loop over a slice, both of which eliminate the bounds check in the body of the loop (the one in list[i]). Arrays do have an advantage however, compilers can see their size so if you have an array (or array reference) and index it with a constant, then that bounds check will be eliminated. Also, array references are cheaper than slices because slices always contain the length.

[nindalf]

> Arrays do have an advantage however, compilers can see their size

Wouldn’t vectors have the same advantage in Rust? If we’re iterating over a vector, it’s proveable at compile time that the length is not being modified during the iteration.

[brundolf]

Length not being modified during iteration sure, but not the exact length. It's not possible in the general case to determine the exact length of a Vec at compile time, whereas Rust arrays can never change length so their exact length is know statically (unless you've got a slice, which is different)

[ReactiveJelly]

I think they mean a one-off constant index should never check.

    let arr = [1, 2, 3, 4];
    // Will not compile a bound check
    let x = arr [3];
    
    let v = vec! [1, 2, 3, 4];
    // Imagine other code separates these two lines
    // Might compile a bound check
    let x = v [3];

[clarkmoody]

In this case, v is not declared mutable, so you could ignore. In fact, the compiler will probably end up assigning x = 4 at compile time.

[est31]

A better comparison is:

    fn foo_arr(v: &[u8; 5]) -> u8 {
        v[2]
    }

    fn foo_vec(v: &Vec<u8>) -> u8 {
        v[2]
    }

In the foo_arr case, the index lookup can be optimized out. In the foo_vec case, it can't be, because theoretically you might pass something with only 2 elements or less to foo_vec, and access to the third element will fail.

Same goes for e.g. the slice::windows vs slice::array_windows functions. In windows, you get a slice in the closure, and while the size is guaranteed by the implementation, without there being inlining the optimizer doesn't know about this guarantee. With array_windows, this size guarantee is communicated.

[winrid]

IIRC the Rust in Action book claimed iterators usually omit bounds checks, but if you manually index into the array then it's more likely the bounds check won't be optimized out.