Example iterator fold vs. loop emit different code

[ghost]

This simple example of a naive factorial (n!) implementation emits different code for using a range fold, and a loop over the iteration. Notably, the iterator fold emits many more instructions than the basic loop. This is unexpected, as this should be a zero-cost abstraction.

https://rust.godbolt.org/z/3cMMh67rE

type T = usize;

pub fn factorial1(n: u8) -> T {
 let mut y = 1;
 for k in 1..=n {
  y *= T::from(k);
 }
 y
}

pub fn factorial2(n: u8) -> T {
 (1..=n)
  .map(T::from)
  .fold(1, std::ops::Mul::mul)
}

@rustbot label I-heavy I-slow

[mqudsi]

On your wasm target, this was nicely optimized in 1.33.0, 1.34.0 introduced a change, 1.56.0 made it much worse.

On x86, 1.34 actually improved the results considerably over 1.33.0. 1.42.0 has nice and compact asm but 1.43.0 messed that up.

We're probably dealing with multiple issues. I'd be surprised if at least one of them hasn't already been reported, but I'm not familiar enough with the backlog to be able to tell one way or the other.

@rustbot label +regression-from-stable-to-stable +A-codegen +T-compiler

[apiraino]

probably this also needs some bisection to start narrowing down where these codegen regressions come from. I'll try to signal this by adding:

@rustbot label E-needs-bisection

[paolobarbolini]

Notably, the iterator fold emits many more instructions than the basic loop

Could this simply be the case for factorial2 getting unrolled and even vectorized if the configuration allows for it, while factorial1 doesn't?

See https://rust.godbolt.org/z/vE51sGWY5

[ghost]

That sure does explain what is occurring! Yet, not why?

(i.e. Wouldn't we want them both vectorised for opt-level=3?)

[paolobarbolini]

If I use a while loop it works, so I guess something is preventing LLVM from optimizing the for loop

https://rust.godbolt.org/z/sha96Ga3a

[apiraino]

I'll nominate for T-compiler meeting for an opinion on how to proceed (e.g. understand how impacting this could be due to the unclear origin, possibly find an owner if it turns out to be worth being investigated soon)

@rustbot label I-compiler-nominated

[the8472]

so I guess something is preventing LLVM from optimizing the for loop

Inclusive ranges optimize poorly. Switch to an exclusive range and the for-loop does the same unrolling as the iterator.
So this likely is a dup of #45222

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-medium

[apiraino]

Discussed in T-compiler meeting (notes)

@rustbot label -p-high +p-medium