Step 3 of 6

Allocate less

A Vec (and a String, which is a Vec<u8> inside) keeps its elements in one heap buffer with room to spare: its capacity. When you push past the capacity, it allocates a bigger buffer (about double), copies everything over and frees the old one.

fn main() {
    let mut grown = Vec::new();
    let mut allocations = 0;
    let mut last_capacity = grown.capacity();
    for i in 0..1000 {
        grown.push(i);
        if grown.capacity() != last_capacity {
            allocations += 1;
            last_capacity = grown.capacity();
        }
    }
    println!("Vec::new: {allocations} allocations, capacity {}", grown.capacity());

    let mut sized = Vec::with_capacity(1000);
    let start = sized.capacity();
    for i in 0..1000 {
        sized.push(i);
    }
    println!("with_capacity: capacity {} -> {}", start, sized.capacity());
}

Vec::new: 9 allocations, capacity 1024
with_capacity: capacity 1000 -> 1000

Doubling keeps pushes cheap on average, but when you know the final size, Vec::with_capacity(n) or String::with_capacity(n) allocates once. The exact growth steps are an implementation detail; the guarantee is that with_capacity(n) gives at least (in practice exactly) n.

You often get this for free: collect() asks the iterator for its size first, so (0..n).map(f).collect::<Vec<_>>() allocates once. join and concat add up the lengths before allocating, too.

Building strings

format! always creates a new String. Inside a loop that appends to a result, that's an extra allocation per line, and result = format!("{result}{line}") even copies everything built so far, every time: quadratic. Write straight into one buffer instead with push_str, or with write! and writeln! (from the std::fmt::Write trait), which format directly into an existing String:

use std::fmt::Write;

fn report(items: &[(&str, u32)]) -> String {
    let mut out = String::with_capacity(items.len() * 16);
    for (name, qty) in items {
        writeln!(out, "{name:<8}{qty:>4}").unwrap();
    }
    out
}

fn main() {
    print!("{}", report(&[("potion", 3), ("arrow", 120), ("map", 1)]));
}

potion     3
arrow    120
map        1

writeln! into a String returns a fmt::Result that can never actually be an error, so .unwrap() is fine here. (std::fmt::Write and std::io::Write share the name Write, so a file that needs both imports one anonymously: use std::io::Write as _; still brings its methods into scope.)

Reuse buffers

When a loop needs a temporary String or Vec, create it once outside the loop and clear() it each time round. clear keeps the capacity, so after the first few rounds the loop stops allocating. The classic case is reading input line by line with read_line(&mut line) and line.clear().

Common mistakes

Capacity isn't length. with_capacity reserves room but the Vec is still empty, so indexing panics:

fn main() {
    let mut v: Vec<u32> = Vec::with_capacity(10);
    println!("len {} capacity {}", v.len(), v.capacity());
    v[0] = 1;
}

len 0 capacity 10

Use push, or vec![0; 10] if you really want ten zeros to overwrite.

• Guessing huge capacities "to be safe" wastes memory. Use exact counts when you know them; otherwise let the Vec grow.

Your task

Write join_path, which joins path parts with / (["usr", "local", "bin"] gives "usr/local/bin") and allocates exactly once: compute the final length first (all the parts plus one / between each pair, careful with an empty list), create the String with that capacity, then push_str and push. A test checks the capacity equals the length. (parts.join("/") does exactly this internally; here you write it yourself.)

Challenge 2

Write render_table, which turns (name, quantity) rows into lines like potion: 3, each ending with \n. Build everything in one String created with with_capacity (a rough estimate is fine), and append each line with writeln! instead of format!.

Challenge 3

numbered_list rebuilds the whole string on every line with format!, so the total copying grows with the square of the list length: 200,000 items take far longer than the time limit. Make it linear by appending to one String instead. The output format stays the same: 1. first\n2. second\n....

Previous: Borrow, don't clone Next: Iterator chains and avoiding intermediate collections