Where the allocations are: the counting allocator

Timing is a terrible way to learn about allocation. It is noisy, it depends on your machine, your thermal state and what else is running, and it tells you that something is slow without telling you what.

Allocation counts have none of those problems. They are exact, they are reproducible, they are the same on your laptop and on CI, and every one of them is explainable from first principles. This item introduces the instrument that makes them visible — and that this platform uses to grade several later problems.

How it works

Rust lets you replace the global allocator with your own:

struct Counting;
unsafe impl GlobalAlloc for Counting {
    unsafe fn alloc(&self, l: Layout) -> *mut u8 {
        ALLOCS.fetch_add(1, Ordering::Relaxed);
        unsafe { System.alloc(l) }
    }
    // dealloc, realloc, alloc_zeroed likewise
}
#[global_allocator]
static COUNTING: Counting = Counting;

Every Box::new, every Vec growth, every String — everything in the program — goes through it. This harness installs exactly that, and hands you two functions:

alloc_reset();          // set the counter to zero
alloc_count() -> usize  // read the counter

Note realloc counts too. A Vec growing in place still asks the allocator for more memory and may still memcpy; calling that “free” would be a lie.

The caveat, stated plainly

The counter is process-global. It is already counting the JSON reader that parsed your test input, and it will keep counting anything else that runs. That is exactly why you must alloc_reset() immediately before the thing you want to measure and alloc_count() immediately after — and why later problems state allocation budgets as <= with a little slack rather than as exact equalities.

What to write

pub fn alloc_report(n: usize) -> Vec<usize>

Perform these four constructions, in this order, measuring each one independently, and return the four counts:

// 0
let mut grown: Vec<u64> = Vec::new();
for i in 0..n { grown.push(i as u64); }

// 1
let mut sized: Vec<u64> = Vec::with_capacity(n);
for i in 0..n { sized.push(i as u64); }

// 2
let mut joined = String::new();
for i in 0..n { joined = format!("{}{}", joined, PARTS[i % 5]); }

// 3
let mut built = String::with_capacity(n * 5);
for i in 0..n { built.push_str(PARTS[i % 5]); }

Wrap each finished value in std::hint::black_box before moving on. Without it the optimiser is entitled to notice you never read grown and delete the whole loop, and you would measure zero.

The numbers you are about to produce, and why

For n = 1000, the correct answer is [9, 1, 1999, 1].

9. Vec::new() does not allocate at all — an empty Vec is a null-ish dangling pointer, a zero length and a zero capacity, entirely on the stack. The first push allocates capacity 4, and each time it fills, Vec doubles: 4, 8, 16, 32, 64, 128, 256, 512, 1024. Nine allocations to hold a thousand elements. This doubling is what makes push amortised O(1) — each element is copied on average a constant number of times.

1. with_capacity asks for the whole thing up front. One allocation, no copying, no doubling. Every subsequent push is a store and a length bump.

1999. This is the one worth staring at. format!("{}{}", joined, part) does not append to joined — it builds an entirely new String containing a copy of the old one plus the new part, and then you throw the old one away. Two allocations per iteration (the new buffer, plus one growth inside the formatting machinery), minus one for the empty first round. It is also O(n²) in bytes copied: 6.6 MB moved to produce a 4.4 KB string.

1. with_capacity plus push_str writes into one buffer, in place, forever. One allocation, 4.4 KB copied. This is the same output as checkpoint 2, produced with 1999× fewer allocations.

That last comparison is the reason this instrument exists. You did not need a profiler, a stopwatch or a quiet machine to see it.

Related lints

vec_init_then_push (you built a Vec::new() and immediately pushed known elements — use vec![...]), slow_vector_initialization (you grew a vector in a loop where vec![0; n] or with_capacity would do), and repeat_vec_with_capacity. All default-on. None of them catch the format! accumulation, which is the expensive one — clippy helps least exactly where it would help most.

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