4 ms·

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 mea

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)

tialaramex 4y ago
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 4y ago
  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 4y ago
    > 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.
    - ReactiveJelly 4y ago
      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 4y ago
        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 4y ago
        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.
    - brundolf 4y ago
      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)
oconnor663 4y ago
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.
- brundolf 4y ago
  Yeah, I wondered about those too. Less straightforward than pure iterator usage but still plausible
- ridiculous_fish 4y ago
  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 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 https://rust.godbolt.org/z/PEsbeGxWP
  - akshaykarthik 4y ago
    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 4y ago
      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.
winrid 4y ago
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.

tialaramex 4y ago

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 4y ago
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 4y ago
  > 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.
  - ReactiveJelly 4y ago
    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 4y ago
      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 4y ago
        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.
  - brundolf 4y ago
    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)

oconnor663 4y ago

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.

brundolf 4y ago
Yeah, I wondered about those too. Less straightforward than pure iterator usage but still plausible
ridiculous_fish 4y ago
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 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 https://rust.godbolt.org/z/PEsbeGxWP
- akshaykarthik 4y ago
  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 4y ago
    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.

winrid 4y ago

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.