String and text performance, graded

Building a string in a loop is one of the two or three things every program does, and it is where the difference between “correct” and “correct and not embarrassing” is largest. The naive version of this problem is 590× slower than the reference. Not 59%. Five hundred and ninety times.

What to write

pub fn render_report(rows: Vec<(String, i64)>) -> String

One line per row, formatted as

"{name:<12}{value:>10}\n"

— the name left-aligned in a field of 12, the value right-aligned in a field of 10, then a newline. Names longer than 12 are not truncated; the field simply grows. After all the rows, one more line in the same format with the name TOTAL and the sum of every value. An empty input still produces the TOTAL line, with 0.

abc                  0
fghi                 1
klmno                2
TOTAL                3

The gate

The whole call may perform at most two heap allocations, and one test drives it with 3000 rows.

The version that fails is the one everybody writes first:

out = format!("{}{:<12}{:>10}\n", out, name, value);

Read what that does. format! allocates a brand-new String, copies the entire report built so far into it, appends one line, and drops the old buffer. Two allocations per row, and — far worse — O(n²) bytes copied. At 3000 rows you move about 100 MB to produce 69 KB.

The version that passes allocates once, up front, and writes into that buffer forever:

let mut out = String::with_capacity(rows.len() * 24 + 32);
...
writeln!(out, "{name:<12}{value:>10}").unwrap();

write! and writeln! on a String come from std::fmt::Write — you have to use std::fmt::Write as _; to get them. They format directly into the existing buffer: the padding is emitted as it goes, and the integer is rendered into a small stack buffer. No intermediate String is created at all.

They return a Result because the same trait serves io::Write, where failure is real. Writing into a String cannot fail, so .unwrap() there is correct and is not a code smell.

The family of lints that live here

All default-on, all worth recognising on sight:

• format_in_format_args — format!("{}", format!("{}", x)). The inner one allocates a String that the outer one immediately copies and drops.
• to_string_in_format_args — format!("{}", x.to_string()). Same shape: Display was going to be called anyway, the to_string() just adds an allocation in front of it.
• useless_format — format!("{}", s) where s is already a String.
• manual_str_repeat — a loop pushing the same string n times; use "ab".repeat(n).
• single_char_add_str — s.push_str("x") should be s.push('x').
• collapsible_str_replace — chained .replace() calls that could be one replace with a &['a', 'b'][..] pattern.
• manual_ignore_case_cmp — a.to_lowercase() == b.to_lowercase() allocates twice to answer a question eq_ignore_ascii_case answers with no allocation at all.

And in pedantic: format_collect (.map(|x| format!(..)).collect::<String>() allocates per element — fold into one buffer with write! instead) and inefficient_to_string.

The general principle

Every one of those lints is the same idea wearing a different hat: decide where the bytes are going to live, allocate that once, and write into it. Once you see text formatting that way, the whole family becomes obvious rather than a list to memorise.

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