Does Rust optimize for loops over calculated ranges?

Question

As an exercise I'm trying to micro-optimize code in Rust 1.3.0. I have a loop of a loop over an array. Something like this:

loop {
    for i in 0..arr.len() {
        // something happens here
    }
}

Since arrays are fixed size in Rust, will the compiler optimize the code by evaluating arr.len() just once and reusing the value, or will the expression be evaluated with each pass of the top-level loop? The question can be expanded to more calculation-heavy functions without side-effects, other than arr.len().

In other words, would the above code be equivalent to this:

let arr_len = arr.len();

loop {
    for i in 0..arr_len {
        // something happens here
    }
}

Note that if you are interested in optimization, it's usually a good idea to try and use an iterator instead of indexing into the slice, which has a bit of overhead for bounds checks. Use `for v in &arr` instead when possible. — Shepmaster, Oct 13 '15 at 20:05

score 4 · Accepted Answer · answered Oct 14 '15 at 06:17

The .. is a range operator, which forms a Range<Idx> object (or a derivative: RangeFrom, RangeFull or RangeTo). Those objects only contain indexes (the Idx type), so you can rest assured that .len() is only evaluated once.

In general, it is a good idea to inspect the LLVM IR. If you have a synthetic example, you can use the playground easily enough. For example:

// A black-box prevents optimization, and its calls are easy to spot.
extern {
    fn doit(i: i32) -> ();
}

fn main() {
    let arr = [1, 2, 3, 4, 5];

    for i in 0..arr.len() {
        unsafe { doit(arr[i]); }
    }
}

Yields the following function:

; Function Attrs: uwtable
define internal void @_ZN4main20hd87dea49c835fe43laaE() unnamed_addr #1 {
entry-block:
  tail call void @doit(i32 1)
  tail call void @doit(i32 2)
  tail call void @doit(i32 3)
  tail call void @doit(i32 4)
  tail call void @doit(i32 5)
  ret void
}

In this case, with a fixed length, there is no loop at all: it has been unrolled.

This is essentially similar to the answer I had before editing, in response to Benjamin Lindley's comment. — Jerry Coffin, Oct 14 '15 at 16:08
@JerryCoffin: I am afraid I never saw the previous version of your answer :/ — Matthieu M., Oct 14 '15 at 16:12

Jerry Coffin · Answer 2 · 2015-10-14T02:14:39.760

3

At least in a quick check with using arr.len() nested inside another loop, no code seems to be generated for the "call" to arr.len() at all. In the generated code, the size of the array is simply hard-coded into the output.

In other words, I would not expect your second snippet to execute any faster than the first one.

edited Oct 14 '15 at 02:14

answered Oct 13 '15 at 18:41

Jerry Coffin

476,176
80
629
1,111

2

I think the OP is referring to multiple executions of the entire for loop body, whereas you are addressing (correct me if I'm wrong) the iterations of a single execution of the for loop. In other words, he wants to know if, each time the for loop begins, if the range extents are calculated again, even though they cannot change (because the array length cannot change). Notice his for loop is nested in another loop. – Benjamin Lindley Oct 14 '15 at 01:17
@BenjaminLindley Yes, that's exactly what I meant. – Jakub Oct 14 '15 at 15:48

Does Rust optimize for loops over calculated ranges?

2 Answers2

Linked