Capacity and pre-sizing, graded

The simplest optimisation in the language, on the simplest possible problem, with a hard budget attached. This is the first item in the course where the cost of your code — not just its correctness — decides whether it passes.

What to write

pub fn build_index(words: Vec<String>) -> Vec<u32>

Return the prefix sums of the byte lengths: a vector of words.len() + 1 offsets, starting at 0, where offset i is the total number of bytes in the first i words.

["ab", "abab"]  ->  [0, 2, 6]
[]              ->  [0]

That is a string index — exactly the shape a zero-copy parser or an arena of interned strings uses to find slice i without storing a pointer per entry.

The gate

The whole call must perform at most one heap allocation, and one test drives it with 200 000 words.

Vec::new() allocates nothing, then grows by doubling: capacities 4, 8, 16, … 262144. That is nineteen allocations for 200 001 elements, and — worse — nineteen memcpys of a buffer that ends up 800 KB long, so you copy about 1.6 MB of data to build 800 KB of answer.

Vec::with_capacity(words.len() + 1) asks for the whole thing once. One allocation, zero copying, and every push afterwards is a store and a length increment. The length is knowable before the loop starts, so there is no excuse not to say so.

(An iterator chain that collects also works, provided its size_hint is exact — collect asks the iterator how many elements are coming and pre-sizes from the answer. That is the same optimisation wearing different clothes, and a later item is about what happens when the hint is wrong.)

Three things people get wrong about capacity

Over-applying it. Vec::with_capacity(3) for a vector that will hold three elements saves you nothing measurable and costs a line of noise. The lever matters when the count is large or the loop is hot; below that it is cargo cult.

Under-applying it. The one place it genuinely matters — a loop building a large collection whose size is known — is exactly where people forget, because the naive version looks fine and never fails a test. Until now.

shrink_to_fit is not free. It can allocate a new, smaller buffer and memcpy into it, so calling it reflexively after building a vector can cost you an allocation and a copy. Use it when you are about to hold the vector for a long time and the slack is large.

And a related fact worth internalising: Vec::new() does not allocate at all. An empty Vec is three words on the stack: a dangling aligned pointer, length 0, capacity 0. That is why Option<Vec<T>> is almost always pointless — an empty Vec already costs nothing, and None buys you no memory saving while forcing every reader through an extra unwrap.

Related lints

vec_init_then_push (build the vector with vec![..] if you know the elements up front), slow_vector_initialization (a loop pushing zeroes where vec![0; n] would do — and would use alloc_zeroed, which the OS can serve from already-zeroed pages), repeat_vec_with_capacity, and manual_string_new (pedantic).

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