Zero-cost abstractions, examined

"Zero-cost abstraction" is a common description of Rust features such as iterators, generics, closures and ownership. This article explains what the phrase claims, describes four situations where an abstraction does cost something or moves the cost somewhere else, and shows how to check a particular case instead of assuming.

Two terms first. An abstraction here is any language or library feature that lets you write code at a higher level than the machine instructions it becomes: an iterator chain instead of an index loop, a generic function instead of one copy per type, a trait object instead of a hand-written table of function pointers. The optimizer is the part of the compiler that rewrites the program to make it faster or smaller; by default rustc uses LLVM for this. Most statements in this article describe what the optimizer usually does, not what it is required to do, which is why they say "usually" and "can".

What the phrase claims

The idea comes from C++. Bjarne Stroustrup describes C++'s zero-overhead principle this way:

What you don't use, you don't pay for. And further: What you do use, you couldn't hand code any better.

Both halves are comparisons. The first is about features you do not use: their existence in the language should not slow down programs that ignore them. The second is about features you do use: the result should run as fast as the code a competent programmer would write by hand for the same job.

So "zero-cost" means no extra runtime cost compared with a hand-written equivalent. It does not mean the work itself is free (summing a million numbers still takes a million additions), and it says nothing about compile time, binary size or how easy the code is to read. Many disagreements about the phrase come from people using different meanings of "cost".

It is also a description of what optimized builds typically achieve, not a rule in the language definition. Unoptimized (debug) builds keep most of the abstraction overhead, so speed comparisons only make sense on optimized builds, such as those produced by cargo build --release.

// (a) index loop
let mut total = 0u64;
for i in 0..v.len() {
    total += v[i];
}

// (b) iterator
let total: u64 = v.iter().sum();

// (c) trait object versus generic
fn area_dyn(s: &dyn Shape) -> f64 { s.area() }
fn area_generic<S: Shape>(s: &S) -> f64 { s.area() }

Four places where the cost is real

1. collect from iterators that do not know their length

Iterator::size_hint returns a pair (lower, upper): the iterator will produce at least lower more items and, if upper is Some(n), at most n. collect::<Vec<_>>() and Vec::extend use the lower bound to decide how much memory to reserve before they start.

Adaptors whose output length depends on the data cannot give a useful lower bound. Applied to a slice iterator over n items, filter, take_while and skip_while report (0, Some(n)) with the current standard library, and flat_map over a vector of vectors starts at (0, None) because it has not looked at the inner vectors yet. The documentation only requires a hint not to be wrong, so a lower bound of zero is always allowed.

When the reservation is too small, the vector grows as items arrive. Each time it runs out of space it allocates a larger buffer and moves the existing items into it. The current implementation at least doubles the capacity each time, so the number of reallocations grows with the logarithm of the final length and the total copying stays proportional to the output size. That is efficient in the long run, but it is still extra allocation and copying that a hand-written loop starting from Vec::with_capacity avoids.

For example, here are three ways to flatten a vector of vectors into one vector:

let nested: Vec<Vec<u32>> = vec![vec![1, 2], vec![3], vec![4, 5, 6]];

// Starts from a lower bound of 0, then grows as needed.
let a: Vec<u32> = nested.iter().flat_map(|row| row.iter().copied()).collect();

// Computes the total length first and allocates once.
let b: Vec<u32> = nested.concat();

// The same idea, written by hand.
let mut c = Vec::with_capacity(nested.iter().map(Vec::len).sum());
for row in &nested {
    c.extend_from_slice(row);
}

assert_eq!(a, [1, 2, 3, 4, 5, 6]);
assert_eq!(a, b);
assert_eq!(b, c);

All three produce [1, 2, 3, 4, 5, 6]. With 1,000 inner vectors of 10 items each, the flat_map version performs several allocations while it grows, and the other two perform one.

Reallocation is not the only difference. flat_map produces items one at a time and checks on every step whether the current inner iterator is finished, while concat and extend_from_slice copy each inner slice as a block. How much these differences matter depends on the sizes involved and on the machine, so measure your own case. The general point: collect can only reserve what the hint tells it. When you know the final size and the adaptor chain does not, Vec::with_capacity followed by extend, or a method such as concat that computes the size itself, provides that information.

2. Bounds checks are removed only when the optimizer can prove them unnecessary

Indexing a slice with v[i] checks that i < v.len() and panics if it is not. In an optimized build, the optimizer removes the check when it can prove the condition always holds, as in for i in 0..v.len() { ... v[i] ... }. Iterators such as iter() and zip do not index at all, and chunks_exact(k) produces slices whose length is exactly k, which often lets the optimizer remove checks on indexes below k inside each chunk.

It cannot always prove it. A common case is indexing two slices with the same index:

fn dot(a: &[f64], b: &[f64]) -> f64 {
    let mut sum = 0.0;
    for i in 0..a.len() {
        sum += a[i] * b[i]; // a[i] is provably in bounds; b[i] is not
    }
    sum
}

The loop bound proves i < a.len(), but nothing says b is at least as long as a, so the check on b[i] has to stay. Adding assert_eq!(a.len(), b.len()); before the loop supplies the missing fact: the function now panics once, up front, if the lengths differ, and with rustc 1.98 the bounds check inside the loop disappears. Writing the loop as a.iter().zip(b).map(|(x, y)| x * y).sum::<f64>() avoids indexing entirely, but note that zip stops at the end of the shorter slice instead of panicking, which is a different contract for unequal lengths.

The compiler does not report which checks remained. To find out, inspect the generated assembly, for example with cargo rustc --release -- --emit=asm or a tool such as cargo-show-asm, and look for calls to core::panicking::panic_bounds_check; or benchmark. A surviving check is usually cheap on its own: a comparison and a branch that the processor almost always predicts correctly. It matters most in hot loops, where it can also block other optimizations such as vectorization (processing several elements per instruction). The cost of indexing therefore depends on facts that are not visible in the source code.

3. async has costs outside the state machine

An async fn compiles to a future: a value of an anonymous type that stores the function's local variables and records which .await it is paused at. Calling poll on it resumes from that point. This is close to what you would write by hand as an enum with one variant per pause point and a match on it, so the core transformation fits the zero-cost description. A future does not need its own thread stack. The executor that runs futures decides where each one is stored; many executors allocate once per spawned task to hold it.

Other costs are real, even though a benchmark of a single poll does not show them:

• Pin. A future can hold references to its own fields across an .await. Moving such a value would leave those references pointing at the old location, so once a future has been pinned in place for polling, it must not move again. Pin expresses that rule in the type system, and it makes futures and combinators written by hand harder to get right. Many hand-written combinators require their inner futures to be Unpin (safe to move even when pinned) to keep the code simple, which moves the pinning work to whoever calls them.
• async fn in traits. This has been stable since Rust 1.75 (December 2023), with limits. A trait containing an async fn is not dyn compatible, so it cannot be used directly as dyn Trait (error E0038). On stable Rust, a caller also cannot write a bound requiring the future returned by such a method to be Send; the syntax for that, return type notation, is still unstable (E0658). For public traits the compiler warns about this through the async_fn_in_trait lint, and the usual workaround is to declare the method as fn method(&self) -> impl Future<Output = T> + Send.
• Send requirements. Multi-threaded executors move tasks between threads, so their spawn functions usually require the future to be Send (Tokio's tokio::spawn, for example, requires Send + 'static). A future is Send only if everything it keeps alive across an .await is Send, so a single Rc held across one .await makes the whole future unusable with such a function. The compiler reports "future cannot be sent between threads safely" at the call that requires Send, with a note pointing to the .await across which the value was held.
• Boxed futures. Storing futures of different concrete types in one collection, or returning one from a method on a trait object, usually means Pin<Box<dyn Future<Output = T>>>. That costs one heap allocation when the box is created and an indirect call on each poll. Those are runtime costs that code using a single concrete future type would not pay.

Apart from boxing, and from whatever change you make to satisfy Send (replacing Rc with Arc, for example, makes every reference-count update an atomic operation), these are costs in how hard the code is to write and read, not in speed. The design of async Rust accepted them in exchange for futures that need no stack per task and no garbage collector. Calling that a trade-off is more accurate than calling it free.

4. Monomorphization moves the cost to compile time and binary size

A generic function is compiled separately for each set of concrete type arguments it is used with. That is why area_generic in the question above can call area directly and inline it. It also means the compiler generates and optimizes one copy per instantiation, so heavily generic code can take longer to compile and can produce a larger binary. Some copies disappear (inlined into their callers, or merged when the generated code is identical), so the growth is not always proportional to the number of types, but the direction is real.

Using dyn Trait instead compiles the function once and pays with an indirect call at runtime. A common middle ground keeps a small generic wrapper that converts its argument and immediately calls a non-generic inner function containing most of the code:

use std::path::Path;

pub fn file_len<P: AsRef<Path>>(path: P) -> std::io::Result<u64> {
    fn inner(path: &Path) -> std::io::Result<u64> {
        Ok(std::fs::metadata(path)?.len())
    }
    inner(path.as_ref())
}

Only the one-line wrapper is duplicated for each path type (&str, String, PathBuf and so on); inner is compiled once. The standard library's std::fs::read uses the same pattern.

So monomorphization does not remove the cost of supporting many types; it moves it from runtime to compile time and binary size. That is usually a good trade, but it is a trade.

Where the claim holds

The cases above are specific. In much everyday code the claim holds well in optimized builds:

• Iterator chains such as v.iter().filter(|x| **x > 0).map(|x| x * 2).sum::<i64>() usually compile to the same kind of loop you would write by hand. The adaptor structs and closures are inlined away, as in the (a) and (b) example above. Inlining is a heuristic, so check the output when a specific loop matters.
• Generic functions and impl Trait arguments use direct calls that can be inlined.
• Option<&T> has the same size as &T. A reference is never null, so None can be stored as the null value. The standard library documents this guarantee, and the same holds for Option<Box<T>> and Option<NonZeroU32> (compared with Box<T> and NonZeroU32).
• Other enums often benefit from the same idea without a documented guarantee. For example, with current rustc, Result<(), E>, where E is an enum whose variants carry no data and which has between 2 and 255 variants, takes one byte, the same as E: a byte value that E never uses can represent Ok(()). (With a single variant, E takes zero bytes, so the Result needs one byte for its own tag.) With 256 variants every byte value is taken, and the Result needs a second byte. Treat these sizes as implementation details.
• A struct with one field (a newtype, such as struct Meters(f64);) has the same size as its field with current rustc, and #[repr(transparent)] guarantees that it has the same layout and calling convention as the field.
• Ownership and borrowing rules are checked at compile time. There is no garbage collector, and references (&T and &mut T) carry no reference count or object header. The runtime work ownership causes is mostly the drop calls you would otherwise write by hand, plus occasionally a hidden drop flag: when a value is moved out on only some paths, the program records at runtime whether it still has to drop it.

Not all of Rust's safety is checked at compile time. Bounds checks (section 2), the borrow counter inside a RefCell and the reference count inside an Rc are runtime checks. You pay for them only when you use those operations or types, which fits the first half of Stroustrup's principle.

Treat the claim as a starting assumption

When writing Rust, it is reasonable to assume that a common abstraction compiles to code as good as the hand-written version. When a profiler or benchmark says otherwise, trust the measurement, and check the places described above first: a collect from an iterator with a weak size hint, bounds checks the optimizer could not remove, dyn calls (including boxed futures) that could not be devirtualized, and many instantiations of large generic functions.

Comparisons with C++ need the same care. rustc and Clang both use LLVM, while GCC and MSVC have their own optimizers. Both languages compile generic code separately for each type. Rust's reference rules let rustc tell LLVM that many references do not alias (do not point to overlapping memory), which C++ compilers usually cannot assume without extensions such as __restrict. Which language produces faster code for a particular workload depends on the code, the compilers and the settings, so a general claim in either direction needs a measurement behind it.