[Rust Guide] 13.10. Performance Comparison - Loops vs. Iterators

13.10.0 Before We Begin

During its design, Rust drew inspiration from many languages, and functional programming had a particularly strong influence on Rust. Functional programming often includes passing functions as values to parameters, returning them from other functions, assigning them to variables for later execution, and so on.

In this chapter, we will discuss some Rust features that are similar to what many languages call functional features:

• Closures
• Iterators
• Improving the I/O Project with Closures and Iterators
• Performance of Closures and Iterators (this article)

If you find this helpful, please like, bookmark, and follow. To keep learning along, follow this series.

13.10.1 A Test

To run a benchmark test, load all of The Adventures of Sherlock Holmes by Sir Arthur Conan Doyle into a String and search the contents for the word the. Here are the benchmark results for the search version that uses a for loop and the version that uses iterators:

test bench_search_for  ... bench:  19,620,300 ns/iter (+/- 915,700)
test bench_search_iter ... bench:  19,234,900 ns/iter (+/- 657,200)

The iterator version is slightly faster!

We will not explain the benchmark code here, because the point is not to prove that the two versions are equivalent. The point is to get a rough idea of how these two implementations compare in performance.

Iterators are a high-level abstraction in Rust, yet the code they generate after compilation is almost the same as the low-level code we would write by hand. This is called a zero-cost abstraction.

13.10.2 Zero-Cost Abstraction

Zero-cost abstraction means that using an abstraction does not introduce extra runtime overhead.

Rust iterators can achieve zero-cost abstraction because:

1. Generics and Monomorphization

Rust iterators make heavy use of generics to define operations, such as the Iterator trait. During compilation, the compiler instantiates generic code for each concrete type and generates efficient machine code specialized for those types. This process is called monomorphization.

• Static dispatch: The compiler generates code that calls functions directly for concrete types, so there is no need to look up function addresses at runtime, unlike dynamic dispatch through a virtual table.

• Optimization opportunities: Because the types are known at compile time, the compiler can deeply optimize the code, such as eliminating function-call overhead and inlining.

2. Inlining and LLVM Optimization

Rust uses LLVM as its backend compiler. The compiler can optimize iterator chains in the following ways:

• Function inlining: The Rust compiler inlines operations inside iterators, such as map and filter, expanding them into compact code without function-call overhead.

• Loop unrolling and merging: Multiple iterator method calls, such as map().filter().collect(), can be merged into a single loop at compile time.

• Redundancy elimination: For example, the compiler can directly remove some unnecessary intermediate variables or operations.

The result is that the final code executed by an iterator chain is almost as efficient as a hand-written loop.

3. Lazy Evaluation

Rust iterators are lazy, which means:

• Before a terminal method is called, such as collect() or for_each(), the iterator does not perform any actual work.

• Each intermediate operation, such as map and filter, only creates a new iterator and does not apply the operation immediately.

This lazy design allows the compiler to generate code optimized for the final use case when the iterator is actually used, without introducing unnecessary intermediate data structures or calculations.

4. No Runtime Overhead

One of Rust’s design principles is to avoid runtime costs. Iterator implementations avoid dynamic allocation and runtime polymorphism:

• Rust iterators are based on static types, so they usually do not require heap allocation, unless you explicitly use Box or dyn Iterator.

• The Iterator trait uses static dispatch, which avoids dynamic dispatch. Even when dynamic dispatch is needed, you must explicitly declare dyn Iterator.

5. No Extra Abstraction Cost

Rust iterators provide functionality by operating directly on the underlying data structures, without introducing extra abstraction layers. For example:

• An iterator created by calling .iter() operates directly on the underlying slice or collection, so the overhead is very low.

• Intermediate iterators, such as Map and Filter, are optimized at compile time into a compact set of instructions instead of introducing unnecessary wrapping.

13.10.3 An Example: An Audio Decoder

The following code comes from an audio decoder. The decoding algorithm uses linear prediction math to estimate future values from a linear function of previous samples. This code uses an iterator chain to perform several mathematical operations on three variables in a range: a buffer slice of data, an array of 12 coefficients, and the amount of data shifting in qlp_shift. We declare the variables in this example but do not assign values to them. Although this code does not mean much outside its original context, it is still a concise, real-world example of how Rust turns high-level ideas into low-level code.

let buffer: &mut [i32];
let coefficients: [i64; 12];
let qlp_shift: i16;

for i in 12..buffer.len() {
    let prediction = coefficients.iter()
                                 .zip(&buffer[i - 12..i])
                                 .map(|(&c, &s)| c * s as i64)
                                 .sum::<i64>() >> qlp_shift;
    let delta = buffer[i];
    buffer[i] = prediction as i32 + delta;
}

To compute the prediction value, this code iterates over each of the 12 values in coefficients and uses zip to pair each coefficient with the previous 12 values in buffer. Then, for each pair, it multiplies the values, sums all the results, and shifts the total to the right by qlp_shift bits.

All coefficients are stored in registers, which means accessing these values is very fast. There are no bounds checks on array access at runtime. All of these optimizations that Rust can apply make the generated code extremely efficient. Now that you know this, you can use iterators and closures without fear! They make the code look higher level without causing runtime performance loss.