🎓 A1Learner
🔍

Rust Iterator Performance

Iterator chains compile to code that runs as fast as a hand-written loop. A chain is a zero-cost abstraction in Rust.

Consumers stop early

find stops at the first match — the 9 is never even looked at:

let hit = [5, 7, 9].iter().find(|n| **n > 6);
println!("{hit:?}");

Same answer, two spellings

A hand-written loop and a chain, given the same job — keep the even numbers, multiply each by 10. Whatever the chain costs, it does not cost correctness:

let numbers = 1..=6;
let by_loop = {
    let mut acc = vec![];
    for n in numbers.clone() {
        if n % 2 == 0 {
            acc.push(n * 10);
        }
    }
    acc
};
let by_chain: Vec<i32> = numbers.filter(|n| n % 2 == 0).map(|n| n * 10).collect();
println!("same = {}", by_loop == by_chain);

One pass, counted

A pull counter on the front of a chain. Each source item is pulled exactly once, however many steps follow it — no step re-walks the data:

let mut pulls = 0;
let total: i32 = (1..=5)
    .inspect(|_| pulls += 1)
    .filter(|n| n % 2 == 1)
    .map(|n| n * n)
    .sum();
println!("total = {total} pulls = {pulls}");

collect reserves the right space once

An honest size_hint lets collect allocate once — the finished Vec's capacity is exactly its length:

let v: Vec<i32> = (0..5).collect();
println!("len = {} capacity = {}", v.len(), v.capacity());

Example

fn main() {
    let data: Vec<i32> = (1..=10).collect();
    let mut loop_total = 0;
    for n in &data {
        if n % 3 == 0 {
            loop_total += n * n;
        }
    }
    let chain_total: i32 = data.iter().filter(|n| *n % 3 == 0).map(|n| n * n).sum();
    println!("loop = {loop_total} chain = {chain_total}");
    let mut visits = 0;
    let first_two: Vec<i32> = (0..)
        .inspect(|_| visits += 1)
        .filter(|n| n % 2 == 0)
        .take(2)
        .collect();
    println!("first two = {first_two:?} visits = {visits}");
    let v: Vec<i32> = (0..5).collect();
    println!("hint = {:?} capacity = {}", v.iter().size_hint(), v.capacity());
}

Key points

  • A chain compiles down to roughly the loop you would write by hand.
  • Iterators are what Rust calls a zero-cost abstraction.
  • What you do not use, you do not pay for.
  • What you do use is as fast as hand-written code
  • The Rust Book ran its own benchmark.
  • It searched the text of The Adventures of Sherlock Holmes for one word.
  • A for loop took 19,620,300 ns per pass.
  • Iterators took 19,234,900 ns per pass.
  • A dead heat
  • Keep chains whole and let one consumer finish them.

In this example, the loop and the chain do the same job. Both square the multiples of 3 from 1 to 10 and add them. Both agree on 126. That is 9 + 36 + 81. The middle part proves early stopping. The endless range 0.. feeds a filter and take(2). The visits counter shows the chain pulled only 3 items (0, 1, 2). Those items produce its two even answers. An eager walk-everything-first design would never have finished at all. The last lines prove the third reason. The Vec reports an exact hint of (5, Some(5)). Its capacity is exactly 5. collect reserved the right space in one go. Put together, that is why the Book's benchmark ends in a dead heat. One pass. No middle collections. No wasted pulls. No repeated growing.

Note

Zero-cost does not mean thought-free: an accidental collect() in the middle of a chain really does build that collection.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

Why can a long adapter chain run as fast as a hand-written loop?