Iterator internals: why for and fold are not the same loop

Everyone arriving from C or C++ asks the same question in the first week: are iterators actually as fast as a hand-written loop? The usual answer is “yes, zero-cost abstraction”, delivered with enough confidence that nobody follows up.

The usual answer is a slogan. The real answer is “usually yes, sometimes faster, occasionally slower” — and it is only useful if you can attach a mechanism to each of those three. This article is the mechanism.

Two ways to drive an iterator

External iteration is what you have been doing. You hold the iterator; you call next(); you decide when to stop.

let mut it = v.iter();
while let Some(x) = it.next() {
    total += x;
}

Every step goes through the iterator’s state machine. next() must record where it got to, so that the next call can resume — which means loading state, branching on it, and storing it back, once per element. For a slice that state is a pointer comparison and is nearly free. For an adapter that has to decide which underlying source to pull from, it is a branch.

Internal iteration inverts the control. You hand the iterator a closure and the iterator runs the loop:

let total = v.iter().fold(0, |acc, x| acc + x);
v.iter().for_each(|x| { .. });

Now the iterator is free to run whatever loop it likes. It never has to be able to resume, because it never yields control back until it is finished. That freedom is the whole story.

💡fold has a perfectly good default implementation in the Iterator trait, written in terms of next(). If every adaptor inherits that default, internal and external iteration would generate the same code. Why doesn't that happen? click to reveal

Because fold is a provided method, not a final one — and several std adaptors override it.

A provided method is a default body, and any implementor may replace it with something better. Chain, Flatten and FlatMap all do exactly that for fold and try_fold, and so do the concrete iterators underneath them — slice::Iter, vec::IntoIter, Range.

Take Chain. Its next() has to answer “am I still on the first iterator, or have I moved to the second?” on every single call, because it must be resumable. Its fold does not: it folds the entire first iterator, then folds the entire second, and the branch happens once instead of once per element.

Flatten is the same idea one level up: next() must remember which inner iterator it is inside; fold can loop over the outer iterator and fold each inner one to completion.

So for x in a.chain(b) and a.chain(b).fold(..) are not two spellings of one loop. They are two different loops, and the compiler was given more freedom in the second.

try_fold is the piece that makes it general

The obvious objection to internal iteration: fine, but most of my loops stop early. find, any, all, position all short-circuit, and a plain fold cannot.

That is what try_fold is for.

fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
where F: FnMut(B, Self::Item) -> R, R: Try<Output = B>;

The closure returns something try-able, and returning the “break” case stops the whole thing. It is internal iteration with an exit, and it is the primitive on which the short-circuiting consumers are built. any, all, find, position and find_map are all defined in terms of try_fold rather than in terms of next — which is why they get the same override benefit that fold does.

Note the receiver: &mut self, not self. That is what lets you search an iterator and then carry on consuming it — the property item 9.18 relies on, and it falls out of try_fold‘s signature rather than being bolted on.

Why the type of your iterator is a nest of structs

Ask the compiler what an iterator chain is and it will tell you:

let it = v.iter().filter(|&&x| x > 1).map(|&x| x * 2);
let _: () = it;

error[E0308]: mismatched types
  |
4 |     let _: () = it;
  |            --   ^^ expected `()`, found `Map<Filter<Iter<'_, i32>, ...>, ...>`

Every adapter is a struct that owns the one below it, plus your closure. Map<Filter<Iter<'_, i32>, {closure}>, {closure}> is a value with three layers, and the layers are visible in the type because they are real.

They cost nothing at runtime, for two reasons that work together:

Monomorphisation. Filter<I, P> is generic over both the inner iterator and the predicate, and each closure has its own unique anonymous type (item 9.1). So the compiler generates a separate copy of Filter::next for your specific I and your specific P. There is no dyn, no vtable, no indirect call — the call target is statically known at every layer.

Inlining. Once the call target is known and the body is small, LLVM inlines it. Map::next inlines Filter::next, which inlines Iter::next, which is a pointer bump. The three-layer tower flattens into one loop body with no function calls in it at all.

This is why “the abstraction is free” is broadly true, and it is also why it stops being true in exactly the places where one of those two conditions fails.

💡Where does the "free" argument break down? Name the conditions, not the examples. click to reveal

Three, and they are the ones to check whenever a chain is slower than you expected.

1. Length information is lost. collect reads size_hint to pre-allocate. An adaptor that reports (0, None) — flatten, flat_map, str::split — forces collect to grow by repeated reallocation. That is not a code-generation problem at all; it is an allocation problem, and it is why chunks.iter().flatten().collect() loses badly to chunks.concat(). Item 9.22 has the measurements.

2. The closure does not inline. Small closures inline reliably. A closure that is large, or recursive, or behind a dyn Fn (as in item 9.1’s boxed pipeline), does not. The moment there is an indirect call in the loop body, the whole tower stops collapsing and you are paying a call per element per layer.

3. The iteration is dominated by something else. If each element does a heap allocation, a system call, or a cache miss, the difference between a branch-per-element and no branch is unmeasurable. Most real loops are in this category, which is the honest reason the question matters less than people think.

Note what is not on the list: “iterators are an abstraction, therefore slow”. The cost model is specific, and each entry is checkable.

The case where the chain is genuinely faster

Worth stating, because it is the direction people never expect.

let dot: i64 = a.iter().zip(b.iter()).map(|(x, y)| x * y).sum();

versus

let mut dot = 0;
for i in 0..a.len() { dot += a[i] * b[i]; }

The indexed loop must bounds-check both slices on every iteration. LLVM can often eliminate one of them by proving i < a.len() from the loop condition, but it usually cannot eliminate the other, because nothing in the loop relates b.len() to a.len(). zip does that reasoning once, structurally: it stops when either side stops, so no per-element check exists to eliminate. The measured pair in item 9.26 has the chain about 1.5× faster.

The general principle: iterators are faster than loops when they carry an invariant the compiler would otherwise have to rediscover. Bounds are the common one.

Measuring it yourself, honestly

If you go looking, expect to be humbled. Here is a real result from writing this article — summing a Vec<Vec<u64>> of 50 000 four-element chunks, three ways, three runs each:

for-loop 190µs   fold 175µs   sum 164µs
for-loop 148µs   fold 155µs   sum 163µs
for-loop 142µs   fold 158µs   sum 176µs

The ranking changes between runs. The spread within one variant is larger than the difference between variants. This measurement shows nothing, and reporting the first row as “fold is 8% faster” would have been a lie.

That is the normal outcome for micro-benchmarks of this kind on a modern out-of-order CPU, and it is why the mechanism matters more than any single number. Rules that follow:

• Use std::hint::black_box on the inputs so the optimiser cannot constant-fold your benchmark away — and remember it is documented as best-effort, and that its input is still optimised (black_box(5 * 10) folds to 50 first).
• Run it several times, in both orders, and look at the spread before you look at the mean.
• Be suspicious of any difference under 10%.
• Measure a release build. In debug, nothing inlines and iterators lose to loops by a mile — which tells you about -O0, not about iterators.

What to carry forward

1. External iteration means you call next(); internal means you hand over a closure and the iterator drives.
2. fold and try_fold are provided methods that adaptors override — notably Chain, Flatten and FlatMap — removing a per-element branch. So for and fold are genuinely different loops.
3. try_fold exists so that short-circuiting consumers can be internal too, and any/all/find/position are built on it.
4. The adapter-struct nest in error messages costs nothing, because of monomorphisation plus inlining — and it stops being free precisely when one of those two fails.
5. Do not say “iterators are always zero-cost.” Say: free when the chain preserves length information and the closures inline. That sentence is both true and useful.