"Help, iterators made my Rust program slower!"

Monday, September 18, 2023

Recently in a programming community I belong to, someone presented a problem. They had a Rust program which was using threads and for loops. When they updated the code to use iterators, it got dramatically slower. Why did this happen?

For a Rust veteran, the problem might not be surprising, but it trips up a lot of people because of how iterators work. Let's set the stage first with an example program.

Here's a program similar to what they presented originally. Instead of doing real work, though, we'll just use sleeps.

use std::thread;
use std::time;

fn do_work(i: usize) -> thread::JoinHandle<()> {
    thread::spawn(move || {
        let duration = time::Duration::from_millis(100);
        thread::sleep(duration);
        println!("thread {i} done");
    })
}

fn main() {
    let mut handles = Vec::new();

    for i in 0..10 {
        let handle = do_work(i);
        handles.push(handle);
    }

    for handle in handles {
        handle.join();
    }
}

When I run this one on my machine, it takes 103 milliseconds.

Now let's see it using iterators, in a way you might expect to work.

use std::thread;
use std::time;

fn do_work(i: usize) -> thread::JoinHandle<()> {
    thread::spawn(move || {
        let duration = time::Duration::from_millis(100);
        thread::sleep(duration);
        println!("thread {i} done");
    })
}


fn main() {
    (0..10)
        .map(do_work)
        .for_each(|handle| {
            handle.join();
        });
}

And this one takes... 1008 milliseconds! It takes 10 times longer. It's easier to read in a lot of ways, because it doesn't require separately keeping track of the join handles, but it's so much slower. Why?

The clue is in being nearly exactly 10 times longer. That's suspiciously similar to the number of things we're iterating over for a good reason: because we have lost all parallelism here.

In Rust, iterators are lazy, which means that nothing happens with them until next is called on it, or it's iterated over (same thing, really). This lets you do really neat things, like create an infinite-length iterator which you zip with a finite-length iterator (this can be a way to implement enumerate).

The code above chains together a few iterators. First, we have (0..10), which creates a Range, which is an iterator over a particular range of numbers. Then we call .map on it, which transforms it into an iterator which will have a number for each iteration and call do_work on that number. The first iterator isn't evaluated, but is transformed: when evaluated, it won't create the numbers in one go, then the threads in another; it will just do all the work for each iteration one step at a time. And then the final step is we call for_each on it. This returns nothing and does iterate over the underlying iterator. But as we've noted, it doesn't collect the elements of the iterator then iterate over them: it applies its closure to each element individually in turn.

So here we're really doing this:

for i in 0..10 {
    let handle = do_work(i);
    handle.join();
}

And so because we create the handle then immediately join it, we never achieve any parallelism and it's much slower!

In this sort of program, for loops are pretty idiomatic. But you can still write it with iterators if that's more your speed, you just have to do it a little differently. Omitting the repeated definition of do_work, here's an example of that.

fn main() {
    let handles: Vec<_> = (0..10).map(do_work).collect();
    handles.into_iter().for_each(move |handle| {
        handle.join();
    });
}

This is admittedly much wordier. But critically, it does allow using iterators here and still achieving parallelism. The key is that creating the join handles, and joining on them, are separated into two distinct steps which each consume the underlying iterators. (A side note: that last for_each would be much cleaner as a simple for loop, but I wanted to demonstrate this. Don't do this, probably.)

And there you have it! If your code is a lot slower when you use iterators, this might be why.


If this post was enjoyable or useful for you, please share it! If you have comments, questions, or feedback, you can email my personal email. To get new posts and support my work, subscribe to the newsletter. There is also an RSS feed.

Want to become a better programmer? Join the Recurse Center!
Want to hire great programmers? Hire via Recurse Center!