I am not good at English. Sorry if there are any funny expressions.

I've been experimenting with Rust optimizations and noticed an interesting behavior: The fold version is optimized into the closed-form formula n*(n+1)/2.

this is the for loop version:

pub fn sum(n: i32) -> i32 {
    let mut s = 0;
    for i in 1..=n{
	s += i;
	
    }
    s
}

and i use cargo build --release and cargo asm crate::sum to generate the asm

 test    edi, edi
 jle     .LBB0_1
 mov     ecx, 1
 xor     eax, eax
.LBB0_3:
 xor     edx, edx
 cmp     ecx, edi
 setl    sil
 add     eax, ecx
 cmp     ecx, edi
 jge     .LBB0_5
 mov     dl, sil
 add     ecx, edx
 cmp     ecx, edi
 jle     .LBB0_3
.LBB0_5:
 ret
.LBB0_1:
 xor     eax, eax
 ret

this is the fold version:

pub fn sum(n: i32) -> i32 {
    (1..=n).fold(0,|sum,item| sum + item )

}

this is the asm of fold version

 xor     eax, eax
 test    edi, edi
 jle     .LBB1_4
 cmp     edi, 1
 je      .LBB1_3
 lea     eax, [rdi, -, 2]
 lea     ecx, [rdi, -, 3]
 imul    rcx, rax
 shr     rcx
 lea     eax, [rcx, +, 2*rdi]
 add     eax, -3
.LBB1_3:
 add     eax, edi
.LBB1_4:
 ret

My questions are:

1. Is there something in Rust's compiler (rustc) that specifically recognizes Iterator::fold or Iterator::sum and applies special-case optimizations for ranges?

2. Or is this purely due to LLVM's backend optimizations (like induction variable analysis)?

3. Where in the Rust compiler source code or standard library would such an optimization (if it exists) be implemented?

I’d love to understand why iterators sometimes get optimized to closed-form formulas, but plain loops often don’t.

Thanks in advance for any insights!

1 post - 1 participant

Read full topic