Iterators vs loops, with skip

I've been comparing the performance of simple methods to access an array and came across something weird. The performance of the iterator-, while-unchecked, for-unchecked,slice-iter-methods is the same for the standard step of one. However, when I use a skip of 4. The iterator method falls behind the slice iterator method and the get_unchecked method with a for loop falls behind its while-loop counterpart. Why is this so?? (compiled in release mode)

To clarify: The program builds a vector of the given size and iterates over it - switching entries with the number of repetitions.

Here are my results:

Enter length:
1000000
Enter repetitions:
1000
Index:
Average time: 325.859µs, Best time: 286.5µs
Unchecked with range:
Average time: 355.375µs, Best time: 311.4µs
Get with range:
Average time: 400.481µs, Best time: 358µs
Unchecked with while:
Average time: 135.6µs, Best time: 116.1µs
Iterator:
Average time: 227.038µs, Best time: 199.8µs
Slice:
Average time: 145.709µs, Best time: 115.2µs
Press enter to exist...

And the code:

use std::io;
use std::time::{Duration, Instant};

fn main() {
    println!("Enter length:");
    let mut inp = String::new();
    io::stdin().read_line(&mut inp);
    let len = inp.trim().parse().unwrap();
    let mut test = vec![0; len];

    println!("Enter repetitions:");
    inp.clear();
    io::stdin().read_line(&mut inp);
    let num = inp.trim().parse().unwrap();

    {
        println!("Index:");
        test.iter_mut().for_each(|x| { *x = 0 });
        let mut times = Vec::new();
        for _ in 0..num {
            let start = Instant::now();
            {
                for idx in (0..len).step_by(4) {
                    test[idx] = num;
                }
            }
            times.push(start.elapsed());
        }
        let mut median: Duration = times.iter().sum();
        median /= times.len() as u32;
        let best = *times.iter().min().unwrap();
        println!("Average time: {:?}, Best time: {:?}", median, best);
    }

    {
        println!("Unchecked with range:");
        test.iter_mut().for_each(|x| { *x = 0 });
        let mut times = Vec::new();
        for _ in 0..num {
            let start = Instant::now();
            {
                for idx in (0..len).step_by(4) {
                    unsafe {
                        *test.get_unchecked_mut(idx) = num;
                    }
                }
            }
            times.push(start.elapsed());
        }
        let mut median: Duration = times.iter().sum();
        median /= times.len() as u32;
        let best = *times.iter().min().unwrap();
        println!("Average time: {:?}, Best time: {:?}", median, best);
    }

    {
        println!("Get with range:");
        test.iter_mut().for_each(|x| { *x = 0 });
        let mut times = Vec::new();
        for _ in 0..num {
            let start = Instant::now();
            {
                for idx in (0..len).step_by(4) {
                    if let Some(item) = test.get_mut(idx) {
                        *item = num;
                    }
                }
            }
            times.push(start.elapsed());
        }
        let mut median: Duration = times.iter().sum();
        median /= times.len() as u32;
        let best = *times.iter().min().unwrap();
        println!("Average time: {:?}, Best time: {:?}", median, best);
    }

    {
        println!("Unchecked with while:");
        test.iter_mut().for_each(|x| { *x = 0 });
        let mut times = Vec::new();
        for _ in 0..num {
            let start = Instant::now();
            {
                let mut idx = 0;
                while idx < len {
                    unsafe {
                        *test.get_unchecked_mut(idx) = num;
                    }
                    idx += 4;
                }
            }
            times.push(start.elapsed());
        }
        let mut median: Duration = times.iter().sum();
        median /= times.len() as u32;
        let best = *times.iter().min().unwrap();
        println!("Average time: {:?}, Best time: {:?}", median, best);
    }

    {
        println!("Iterator:");
        test.iter_mut().for_each(|x| { *x = 0 });
        let mut times = Vec::new();
        for _ in 0..num {
            let start = Instant::now();
            {
                for item in test.iter_mut().step_by(4) {
                    *item = num;
                }
            }
            times.push(start.elapsed());
        }
        let mut median: Duration = times.iter().sum();
        median /= times.len() as u32;
        let best = *times.iter().min().unwrap();
        println!("Average time: {:?}, Best time: {:?}", median, best);
    }

    {
        println!("Slice:");
        test.iter_mut().for_each(|x| { *x = 0 });
        let mut times = Vec::new();
        for _ in 0..num {
            let start = Instant::now();
            {
                test[..].iter_mut().step_by(4).for_each(|item| {
                    *item = num;
                });
            }
            times.push(start.elapsed());
        }
        let mut median: Duration = times.iter().sum();
        median /= times.len() as u32;
        let best = *times.iter().min().unwrap();
        println!("Average time: {:?}, Best time: {:?}", median, best);
    }

    println!("Press enter to exist...");
    io::stdin().read_line(&mut String::new()).unwrap();
}

The iterator and slice version only really differ by the usage of for_each vs a for loop. Calling iter_mut on a vector does return the same iterator as the corresponding slice does. Unfortunately, for loops can be slower than for_each if the iterator has some additional internal state that needs a case distinction. AFAIK the skip Iterator has internal state distinguishing the first vs later items. Similar problems occur with e. g. chain.

The difference is that a for-loop uses only repeated calls to next which check the state of the iterator on each iteration while the implementation of for_each can be more efficient.

2 Likes

Thanks for the answer.
This suggests writing simple for-loops is inefficient and using either for_each or while loops should be preferred for performance critical code..

No, not at all. In general, for loops and iterators perform approximately the same. Sometimes one of them is faster for some superficial reason. Sometimes, it's the iterator, sometimes it's the imperative loop.

First and foremost, you should consider which formulation is clearer. Then, if and only if you find that you have a bottleneck, measure for your specific situation. Never speculate about what is and isn't "performance-critical", and especially don't generalize from such microbenchmarks to "loops are always faster". It's just not true.

5 Likes

@Xeno Remember that the differences, the few times they exist, are usually only measurable for tiny loop bodies. Any time you're doing a material amount of work in the body, it really doesn't matter whether you use a for or a for_each.

3 Likes