Capacity, Amortisation, and Why Rust Collections Never Shrink

A Vec<T> is three machine words: a pointer to a heap buffer, a length, and a capacity. Length is how many elements are actually there. Capacity is how many the buffer has room for before it has to move. Everything in this article follows from the gap between those two numbers.

let mut v: Vec<i32> = Vec::new();   // ptr dangling, len 0, cap 0 — no heap yet
v.push(1);                           // allocates

Vec::new() does not allocate. That is not an optimisation detail you can ignore — it is why Vec::new() is const and why a struct full of empty Vecs costs nothing until you fill it. The first push is where the heap gets involved.

The doubling rule, in real numbers

When a push finds len == capacity, Vec asks for a bigger buffer, copies the elements over, and frees the old one. It roughly doubles each time, with a small floor for the first allocation. Here is a Vec<i32> taking 1000 pushes, measured with a counting global allocator:

Vec::new()            + 1000 pushes  ->  9 allocations, 8176 bytes requested
Vec::with_capacity(1000) + 1000 pushes  ->  1 allocation,  4000 bytes requested

Nine allocations, because the capacities go 4, 8, 16, 32, 64, 128, 256, 512, 1024 — and $4 \times (4+8+\cdots+1024) = 8176$ bytes asked for across the sequence, to end up holding 4000 bytes of data. Every one of those steps also copied every element that already existed.

That copying is why push is amortised O(1) rather than plain O(1). Any individual push may be O(n). But because the capacity doubles, a resize of size $n$ only happens after $n/2$ cheap pushes have paid for it, so the total work across $n$ pushes is $O(n)$ and the average is constant. The word “amortised” is doing real work in that sentence: it is a statement about the sum, not about any single call. If you are writing something latency sensitive, a push can still spike.

The number that surprises people

Here is the honest half of the story. The same experiment over one million pushes:

Vec::new()               1 000 000 pushes   0.843 ms
Vec::with_capacity(1e6)  1 000 000 pushes   0.716 ms

A 15% improvement. Not 10×. The allocation count collapses from twenty to one, and the elapsed time barely moves.

Both numbers are true and you should hold them together. Allocation count collapsed because the doubling rule is exponential — twenty allocations covers a million elements. And each of those twenty is a realloc, which a modern allocator often satisfies by extending the existing mapping without copying at all. Meanwhile the loop itself is memory-bound: writing four megabytes to RAM costs what it costs, and that dominates.

So when is with_capacity worth reaching for?

• When the loop body is cheap and the count is known. 15% is 15%.
• When you are inside another loop, so the allocations multiply.
• When the element type is expensive to move — a resize memcpy of Vec<[u8; 4096]> is a very different cost from Vec<i32>.
• When you care about peak memory, not throughput. Doubling can leave you holding nearly 2× what you need.

And when is it not? When you do not know the count, when you would have to guess, and — most of all — when reaching for it turns a clear line into three murky ones. with_capacity is a hint, not a correctness feature.

size_hint: the iterator protocol carries performance metadata

This is the first place you see that Rust’s Iterator trait carries more than values. Every iterator has:

fn size_hint(&self) -> (usize, Option<usize>)

a lower bound and an optional upper bound on how many items remain. collect() into a Vec calls it and pre-reserves the lower bound, which is why v.iter().map(f).collect::<Vec<_>>() performs one allocation rather than twenty. Measured:

[1, 2, 3].iter().size_hint()   ->  (3, Some(3))    exact
"a,b,c".split(',').size_hint() ->  (0, None)       no idea

A slice iterator knows exactly. str::split cannot know without scanning, so it promises nothing — which means collecting a split into a Vec gets no pre-sizing and grows the hard way. That is a small, concrete reason to prefer split_once or a with_capacity when you are parsing a very large string, and a good example of why “it’s just an iterator” hides real differences.

size_hint is a hint in the strict sense: it is not unsafe to get it wrong, so no code may rely on it for memory safety. ExactSizeIterator is the trait for iterators that promise an exact count.

Collections never shrink on their own

Removing elements does not give memory back. Measured:

let mut x = vec![1i32, 2, 3, 4, 5, 6, 7, 8];
before clear:          len 8  cap 8
after  clear():        len 0  cap 8
after  shrink_to_fit(): len 0  cap 0

clear(), truncate(), pop(), remove(), drain() — none of them reallocate. String, HashMap and VecDeque behave the same way. The buffer stays exactly as big as the high-water mark until you explicitly call shrink_to_fit() or shrink_to(n).

This is a deliberate design decision, and it cuts both ways.

It is a feature most of the time, because it is what makes buffer reuse work. The pattern

let mut buf = String::new();
for record in records {
    buf.clear();               // keeps the capacity
    render_into(&mut buf, record);
    consume(&buf);
}

allocates a handful of times total instead of once per record, and it only works because clear is not allowed to hand the buffer back. Writing buf = String::new() inside the loop instead looks equivalent and throws the whole benefit away.

It is a leak-shaped surprise the rest of the time. A Vec that briefly held ten million elements holds forty megabytes forever, even at len() == 0, unless you say otherwise. If a long-lived struct has a field that spikes, shrink_to_fit() after the spike is the fix — and note that it may itself allocate and copy, so it is not free either.

Three lints that catch the common mistakes

clippy -D warnings will stop you at three related shapes. All three messages below are verbatim from clippy 0.1.95.

vec_init_then_push — “calls to push immediately after creation”:

let mut v = Vec::new();
v.push(1);
v.push(2);          // just write vec![1, 2]

slow_vector_initialization — “slow zero-filling initialization”:

let mut v = Vec::with_capacity(n);
v.resize(n, 0);     // write vec![0; n] — it can go straight to calloc

vec![0; n] is not sugar for a loop. For zeroable element types it can ask the allocator for pre-zeroed pages, so the zeroing is effectively free rather than a memset of $n$ bytes.

repeat_vec_with_capacity — “repeating Vec::with_capacity using vec![x; n], which does not retain capacity”. This one is worth seeing measured, because the failure is completely silent:

let nested = vec![Vec::<i32>::with_capacity(64); 3];
// capacities: [0, 0, 64]

vec![x; n] produces n - 1 clones plus the original. Cloning a Vec gives you a vector whose capacity matches its length — and the length here is zero. So two of the three reservations evaporate, and the third only survives because it is the original value moved into the last slot. Every reservation you thought you made is gone, and nothing warns you but the lint.

let nested: Vec<Vec<i32>> = (0..n).map(|_| Vec::with_capacity(64)).collect();

What to take away

1. Length and capacity are different numbers, and only length is part of the public meaning of your data.
2. capacity() is an implementation detail. The standard library documents the amortised complexity and explicitly declines to guarantee the exact growth sequence — so never write a test that asserts on it. (That is precisely why this item is an article and not a graded problem.)
3. with_capacity reliably collapses the allocation count, and moves wall-clock less than you expect. Measure before you clutter code with it.
4. Nothing shrinks unless you ask. Lean on that for buffer reuse; remember it when a long-lived structure is holding a spike.