Reusing buffers instead of allocating per iteration

Count how many values have each decimal length.

pub fn digit_histogram(values: &[u64]) -> [u32; 20]

out[i] is the number of values whose decimal rendering has i + 1 digits. 0 has one digit. u64::MAX has twenty, which is why the array is that size. The return type is a fixed-size array, so the output itself never allocates.

The hidden case runs 200 000 values and allows a total of 4 heap allocations.

Why four

Because four is enough for one reusable buffer and nowhere near enough for one buffer per value. That is the whole item.

The starter calls v.to_string() inside the loop. It is correct, it is the clearest thing to write, and it performs 200 000 allocations and 200 000 frees to produce twenty counters. Allocating inside a loop is the single most common avoidable cost in day-to-day code, and it hides behind whichever convenience method you reached for — to_string, format!, collect, clone, to_vec, to_owned.

The pattern: allocate once, clear() inside

use std::fmt::Write as _;

let mut buf = String::new();
for &v in values {
    buf.clear();            // length 0, capacity kept
    write!(buf, "{v}")?;
    // ...use buf...
}

clear() sets the length to zero and keeps the capacity — Rust collections never shrink on their own. After a handful of iterations the buffer is as large as the longest item it has seen and never allocates again. That is why this works, and it is why writing

buf = String::new();        // <-- throws the buffer away

inside the loop looks identical and destroys the entire benefit. The same applies to Vec::clear, HashMap::clear, VecDeque::clear.

This generalises far beyond string formatting: a scratch Vec in a parser, a line buffer around read_line, a working set in a graph traversal, an accumulator in a serialiser. Hoist the allocation out of the loop, clear it at the top of each iteration.

The measurement, and the answer that beats it

Rendering 200 000 integers four ways:

format!("{x}")                        3.80 ms
x.to_string()                         2.12 ms
reused String + write!                1.46 ms
pure integer arithmetic               0.118 ms

Buffer reuse is a solid 1.45× over to_string and 2.6× over format!. And then there is the last row, which is 12× faster than the best string version — because it never renders anything at all.

You do not need the digits of a number to count them:

let digits = if v == 0 { 1 } else { v.ilog10() as usize + 1 };

u64::ilog10 returns the base-10 logarithm floored, so a 6-digit number gives 5. It panics on zero (there is no logarithm of zero), which is why the guard is not optional — and checked_ilog10 is the Option-returning version if you prefer.

The budget of 4 is deliberately generous enough for the reused-buffer answer, because that is the transferable technique. But the fastest optimisation is still the one where you notice the work did not need doing.

::: question The reused-buffer version is 1.45x faster than to_string. Is that worth the extra lines? Usually not, and you should be able to say why without flinching.

Two extra lines and a mutable binding that lives outside the loop, for 1.45× on a loop that may not be your bottleneck, is a bad trade in most code. The version that reads best is values.iter().map(|v| v.to_string()), and it is the right default.

It becomes worth it when the loop is hot and long — a serialiser writing a million rows, a log formatter on a request path, an inner loop in a parser. Then the allocator traffic is real, and the pattern is small enough to contain in one function.

What is always worth doing is knowing that the choice exists, so that when a profile points at malloc you already know what to do instead of discovering it under pressure. :::

Where the borrow checker joins in

Reusing a buffer means handing out borrows of it and then mutating it again, and the borrow checker has opinions about the order:

let mut buf = String::new();
let mut last: &str = "";
for &v in values {
    buf.clear();               // error[E0502]: cannot borrow `buf` as mutable
    write!(buf, "{v}").unwrap();
    last = &buf;               // ...because it is also borrowed as immutable here
}

The rule is the one you already know — you cannot mutate something while a shared borrow of it is alive — but buffer reuse is where it bites, because the point is to mutate the thing everyone is looking at. Finish with the borrow (copy out the number you needed, push an owned value, complete the comparison) before the next clear(). If you genuinely need the previous iteration’s text in the next iteration, you need two buffers or an owned copy, and the compiler is right to make you say which.

You will also meet E0716, “temporary value dropped while borrowed”, from the related mistake of borrowing from a value that was never stored anywhere: let s = &format!("{v}")[..]; in a position that outlives the statement.

A clippy footnote

There is a lint called clear_with_drain for the habit of writing v.drain(..); where you meant v.clear();. Verified against clippy 0.1.95: it is in the nursery group and allow-by-default, so -D warnings will not catch it for you; when enabled it reports “drain used to clear a Vec“ and it only fires on the full-range form on a local binding — it stays silent on v.drain(1..) and on a container reached through a &mut parameter. Worth knowing about, not worth relying on.

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