Iterator performance: where the abstraction leaks

Rust iterators are famously zero-cost, and mostly they are: map, filter and sum over a slice compile to the same loop you would have written by hand. This item is about the place where the abstraction leaks, why it leaks there, and how to fix it.

size_hint is a real contract

Every iterator answers one question about itself:

fn size_hint(&self) -> (usize, Option<usize>)

A lower bound and an optional upper bound. The default implementation is (0, None) — “somewhere between nothing and infinity” — which is always correct and almost never useful.

collect into a Vec reads the lower bound and calls with_capacity on it. extend does the same. So an iterator that under-reports makes every downstream consumer allocate badly, and the cost is invisible at the call site: rows.iter().flatten().copied().collect() looks exactly as clean as the version that allocates once.

Part 1: flatten

pub fn flatten_rows(rows: &[Vec<i32>]) -> Vec<i32>

Concatenate every row into one vector, in order.

rows.iter().flatten().copied().collect()   // correct, and it fails the gate

Flatten‘s size_hint cannot promise much: it knows how many rows remain but not how long they are, so its lower bound is roughly the current inner iterator’s. collect therefore starts small and grows by doubling — around twenty allocations and twenty full memcpys for a million elements.

The budget is one allocation for a 2000 × 500 input. Two ways to get there:

let total: usize = rows.iter().map(Vec::len).sum();
let mut out = Vec::with_capacity(total);
for row in rows { out.extend_from_slice(row); }

or simply rows.concat(), which does exactly this internally. Note the second half matters as much as the first: extend_from_slice on a Vec<i32> is a memcpy, where pushing element by element is a loop.

This is the general shape of the fix — if you know the size, say so.

Part 2: implement size_hint yourself

pub struct RunLength { ... }
pub fn run_length(runs: Vec<(i32, usize)>) -> RunLength
impl Iterator for RunLength { type Item = i32; ... }

A run-length decoder: [(7, 3), (9, 2)] yields 7, 7, 7, 9, 9. Runs with a count of 0 yield nothing and must be skipped.

Unlike Flatten, this iterator does know exactly how many elements are left — the sum of the remaining counts. So implement size_hint to return that number as both the lower and the upper bound.

The tests read the hint before consuming anything and again after taking three elements, and they check that the final collect allocates once. A default (0, None) fails all three.

The rules for writing one

• The lower bound must never overstate. A consumer may pre-allocate that much and it must be safe.
• The upper bound is a promise too: Some(n) means the iterator will not yield more than n.
• Getting it wrong is not unsafe — Vec re-checks — but it is a bug, and it silently degrades every consumer.
• If your bounds are exact, also implementing ExactSizeIterator lets callers ask .len() directly.

Related lints

iter_cloned_collect (.iter().cloned().collect() on a slice — to_vec() is a memcpy), extend_with_drain, manual_memcpy, iter_count (.iter().count() where .len() is O(1)), iter_nth. And in pedantic: needless_collect — collecting into a Vec only to iterate it again allocates for nothing — and from_iter_instead_of_collect.

The takeaway

Iterator chains are zero-cost when the compiler can see through them. Adaptors that hide the length — flatten, filter, flat_map, chars — are exactly where it cannot, and exactly where you should either compute the size yourself or reach for the bulk operation that already knows it.

Remember the grade is compile + tests + clippy -D warnings.