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
– Shepmaster, Commented Oct 13, 2015 at 20:05

Matthieu M. · Accepted Answer · 2015-10-14 06:17:57Z

5

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.

answered Oct 14, 2015 at 6:17

Matthieu M.

303k58 gold badges495 silver badges754 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jerry Coffin Over a year ago

This is essentially similar to the answer I had before editing, in response to Benjamin Lindley's comment.

Matthieu M. Over a year ago

@JerryCoffin: I am afraid I never saw the previous version of your answer :/

Jerry Coffin · Accepted Answer · 2015-10-14 02:14:39Z

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, 2015 at 2:14

answered Oct 13, 2015 at 18:41

Jerry Coffin

494k83 gold badges657 silver badges1.2k bronze badges

2 Comments

Benjamin Lindley Over a year ago

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.

Jakub Over a year ago

@BenjaminLindley Yes, that's exactly what I meant.

Collectives™ on Stack Overflow

Does Rust optimize for loops over calculated ranges?

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related