How does rust optimize this code to increase the performance so drastically?
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.