How does rust optimize this code to increase the performance so drastically?

48 points tandonhiten

So, I was implementing a base 256 lsd radix sort algorithm with intention to compare it with rust's sort(Tim Sort) and sort\_unstable(Pattern defeating quick sort) algorithms The program generates a vec of n random numbers (n being input from user) and clones it twice, so the same data is compared.

Following is the code for radix sort, I wrote

const RADIX : usize = 256;

pub fn radix_sort(vec : &mut Vec<u32>, len : usize) {
    let mut count : [usize; RADIX] = [0; RADIX];//array to store counts of each digit
    let mut max_ele : u32 = *vec.iter().max().unwrap();//variable to store maximum element of the vec, so that, it can act as control for the loop while sorting the array
    let mut exp : u32 = 0;//stores which element from right we're on right now

    while max_ele > 0 {
        let mut temp : Vec<u32> = vec![0; len];
        vec
        .iter()
        .for_each(|&x| count[(x >> (exp << 3)) as usize & (RADIX - 1)] += 1);//building up the counts array, to count digits

        count[0] -= 1;//subtracting 1 from the 0th index so that after the prefix sum we get 0-based indexing
        (1..RADIX).for_each(|i| count[i] += count[i - 1]);//calculating the prefix-sum / the rolling sum of the vec
        
        (0..len)
        .rev()
        .for_each(|i| { 
            let idx = &mut count[(vec[i] >> (exp << 3)) as usize & (RADIX - 1)];
            temp[*idx] = vec[i];
            if *idx > 0 {*idx -= 1};
        });

        vec.copy_from_slice(&temp);
        count = [0; RADIX];
        max_ele >>= 8;
        exp += 1;
    }
}

I ran this code without optimizations and the following were the results

Enter the size of the array
100000
Radix Sort (stable)                     | 68.442ms
Tim Sort (stable)                       | 56.221ms
Pattern Defeating Quick Sort (unstable) | 92.060ms

With optimizations, the results were

Enter the size of the array
100000 
Radix Sort (stable)                     | 2.470ms
Tim Sort (stable)                       | 11.096ms
Pattern Defeating Quick Sort (unstable) | 3.502ms

I know, it might just be that, I by some chance landed on the best case for all the 3 algorithms, but I tried this about 10 times and every time the result was similar. So, I got curious, How does rust optimize this piece of code to literally make it 34 times faster, Tim Sort about 5 times faster and Pattern Defeating Quick Sort about 30 times faster.

PS : Although It's not the main issue here, I'd also be grateful, if you could tell me, how good is my code overall, I am not very experienced in rust after all.