Implementing Iterator in Assembly
Rust's iterator combinators — map, filter, fold, collect — read like high-level functional code. The trick: chains of them compile down to the same tight loops you'd hand-write. This lesson cracks open the assembly to show the abstraction really is zero-cost.
A Simple Iterator vs a Manual Loop
// Iterator versionfn sum_doubled(data: &[i32]) -> i32 { data.iter().map(|x| x * 2).sum()}
// Manual loop versionfn sum_doubled_manual(data: &[i32]) -> i32 { let mut total = 0; for i in 0..data.len() { total += data[i] * 2; } total}Both compile to the same machine code with -C opt-level=2. The listings in this lesson are hand-simplified for reading: real rustc --emit=asm output carries mangled labels, and for a loop this simple LLVM also vectorises it (see the SIMD section at the end). Here's the scalar core:
; Both versions produce the same code (scalar core, simplified):sum_doubled: xor eax, eax ; total = 0 test rsi, rsi ; len == 0? je .done
.loop: mov ecx, DWORD PTR [rdi] ; Load data[i] lea ecx, [rcx+rcx] ; ecx = data[i] * 2 add eax, ecx ; total += data[i] * 2 add rdi, 4 ; Advance pointer dec rsi ; Decrement counter jnz .loop ; Continue if not done
.done: retThe chain .iter().map(|x| x * 2).sum() lowered to the exact same loop as the index version. No heap-allocated closure, no temporary Vec, no call overhead. The compiler fused the whole chain into one loop body.
Iterator Fusion: Chained Operations
fn process(data: &[i32]) -> i32 { data.iter() .filter(|&&x| x > 0) .map(|&x| x * x) .take(100) .sum()}Four operations chained: filter, map, take, sum. Watch them collapse into one loop. Hover an adaptor on the left to light up the instructions it turned into:
One loop, four adaptors
x86-64Hover over code lines or mapping badges to see correspondences
Four adaptors, one loop body. filter is a conditional jump. map is an imul. take is a counter check. sum is an accumulating add. Nothing in between — no scratch arrays, no allocator calls.
You can watch the fusion without reading a line of assembly. Put a println! in each closure and the output shows every element going through the whole chain before the next one starts, with take cutting the walk short. Predict the printout before you run it.
How the Compiler Achieves This
The trick lives in the iterator trait design. Each adaptor is a struct that wraps the previous iterator:
// Simplified iterator types (what the compiler sees):// data.iter() -> Iter<'_, i32>// .filter(|&&x| x > 0) -> Filter<Iter<'_, i32>, closure>// .map(|&x| x * x) -> Map<Filter<Iter<'_, i32>, closure>, closure>// .take(100) -> Take<Map<Filter<Iter<'_, i32>, closure>, closure>>// .sum() -> calls fold() on the aboveEach adaptor's next() calls the inner iterator's next() and transforms the result on the way out. These are all concrete types — not trait objects — so the compiler inlines every next() call straight through to the source slice. The fused loop falls out of inlining.
Comparing to C: The Equivalent
Here's the C you'd write by hand:
int process(const int *data, size_t len) { int sum = 0; int count = 0; for (size_t i = 0; i < len && count < 100; i++) { if (data[i] > 0) { sum += data[i] * data[i]; count++; } } return sum;}Same loop shape, same instructions in the body. The functional chain in Rust produces the machine code you'd get from the hand-tuned C. Zero-cost abstraction, on the hoof.
collect() and Allocation
collect() is the one that does allocate — it has to, since it builds a fresh collection:
fn get_positives(data: &[i32]) -> Vec<i32> { data.iter().filter(|&&x| x > 0).copied().collect()}get_positives: ; filter() can't promise any elements, so its size hint is (0, Some(len)). ; rustc skips ahead to the first match, allocates room for 4 i32s, ; then pushes the rest, growing when full. Conceptually: ; let mut result = Vec::new(); ; for &x in data { ; if x > 0 { result.push(x); } ; } ; result
; ... allocation call ...
.loop: mov ecx, DWORD PTR [rdi] ; Load element test ecx, ecx jle .skip
; Push to Vec (with possible reallocation) cmp rbx, r12 ; Check capacity je .grow ; Grow if full mov DWORD PTR [r13+rbx*4], ecx ; Store element inc rbx ; Increment size
.skip: add rdi, 4 dec rsi jnz .loopcollect flips the lazy iterator into an eager loop that pushes into a fresh Vec. Even here, the filter still merges into the loop body — there's no intermediate filtered collection sitting on the heap.
fold() and reduce(): The General Case
sum() is implemented in terms of fold():
// This:data.iter().sum::<i32>()
// Is equivalent to:data.iter().fold(0, |acc, &x| acc + x)The fold compiles to a loop with an accumulator:
xor eax, eax ; acc = 0 (initial value).loop: add eax, DWORD PTR [rdi] ; acc += *iter add rdi, 4 ; iter++ dec rsi jnz .loop retThe closure |acc, &x| acc + x is inlined right into the loop body. No function pointer, no indirect call, no boxed closure parked on the heap.
enumerate() Is Free
fn find_first_negative(data: &[i32]) -> Option<usize> { for (i, &val) in data.iter().enumerate() { if val < 0 { return Some(i); } } None}find_first_negative: xor eax, eax ; i = 0.loop: cmp rax, rsi ; i >= len? (unsigned compare) jae .not_found
cmp DWORD PTR [rdi+rax*4], 0 ; data[i] < 0? js .found
inc rax ; i++ jmp .loop
.found: mov rdx, rax ; Payload: the index mov eax, 1 ; Tag: Some ret
.not_found: xor eax, eax ; Tag: None (rdx is ignored) retOption<usize> has no niche to borrow (every usize value is legal), so it comes back as a pair of registers: the tag in rax, the index in rdx. And since lengths are unsigned, the bounds check uses jae, not the signed jge.
enumerate() tacks a counter onto the iterator. In the assembly, that's a single register inc — same thing a manual index variable would compile to.
zip() Fuses Two Iterators
fn dot_product(a: &[f64], b: &[f64]) -> f64 { a.iter().zip(b.iter()).map(|(&x, &y)| x * y).sum()}dot_product: ; Determine the shorter length cmp rsi, rcx cmovbe rcx, rsi ; n = min(a.len, b.len) xorpd xmm0, xmm0 ; sum = 0.0
.loop: test rcx, rcx je .done movsd xmm1, QWORD PTR [rdi] ; Load a[i] mulsd xmm1, QWORD PTR [rdx] ; a[i] * b[i] addsd xmm0, xmm1 ; sum += a[i] * b[i] add rdi, 8 ; Advance a add rdx, 8 ; Advance b dec rcx jnz .loop
.done: retzip fuses into a single loop that walks both pointers in lockstep. The exact loop you'd write in C for a dot product, beat for beat.
SIMD Auto-Vectorisation
Hand the compiler a large enough array and it'll auto-vectorise:
fn sum_array(data: &[i32]) -> i32 { data.iter().sum()}You don't need anything special for this. -C opt-level=2 already runs LLVM's loop vectoriser (Cargo's --release uses level 3, which mostly adds more aggressive inlining), and SSE2 is part of the x86-64 baseline. Here's a trimmed version of what rustc 1.97 emits for x86_64-unknown-linux-gnu at opt-level=2:
sum_array: test rsi, rsi je .empty cmp rsi, 8 jae .vector ; 8 or more elements: SIMD path xor ecx, ecx xor eax, eax jmp .tail.vector: ; rcx = len rounded down to a multiple of 8, rax = that many bytes pxor xmm0, xmm0 ; two 4-lane accumulators xor edx, edx pxor xmm1, xmm1.vector_loop: movdqu xmm2, XMMWORD PTR [rdi+rdx] ; unaligned load of 4 i32s paddd xmm1, xmm2 movdqu xmm2, XMMWORD PTR [rdi+rdx+16] ; next 4 paddd xmm0, xmm2 add rdx, 32 cmp rax, rdx jne .vector_loop
; Horizontal sum of the lanes paddd xmm0, xmm1 pshufd xmm1, xmm0, 238 paddd xmm1, xmm0 pshufd xmm0, xmm1, 85 paddd xmm0, xmm1 movd eax, xmm0 jmp .check_tail.tail: ; scalar loop for the leftovers add eax, DWORD PTR [rdi+rcx*4] inc rcx.check_tail: cmp rsi, rcx jne .tail ret.empty: xor eax, eax retThe compiler took the iterator's sum() call and lowered it to SIMD adds, eight integers per loop trip, with movdqu loads because a slice has no 16-byte alignment guarantee. The scalar .tail loop mops up whatever doesn't divide by eight. How much faster that runs than the scalar loop depends on the CPU and on whether the data is already in cache; for large arrays memory bandwidth often sets the limit. The source still reads .iter().sum().
Key Takeaways
-
Iterator chains compile to single loops. The compiler fuses
map,filter,take,fold,sum, and the rest into one tight loop body. -
No intermediate allocations. Each element flows through the whole chain on its own. No scratch arrays, no temporary collections — unless you explicitly
collect(). -
Closures are inlined. Closures you hand to
map,filter, and friends have known types, so the compiler inlines them completely. -
The assembly matches hand-written C. Feed both to the same LLVM backend and you usually get the same loop.
-
Auto-vectorisation works through iterators. The compiler is just as happy applying SIMD to iterator code as it is to a manual loop.
Rust's iterator design is a clinic in zero-cost abstraction. You write expressive, composable, high-level code; the compiler emits the exact machine code you'd write by hand in assembly.