In-place mutation vs rebuild, measured

Compact an event log: remove every event older than a cutoff, return the removed ones, and leave the survivors in the vector in their original order.

pub struct Event { pub id: u64, pub ts: u64 }

pub fn compact_log(log: &mut Vec<Event>, cutoff: u64) -> Vec<Event>

“Older than” is strict: ts < cutoff is removed, ts == cutoff stays. Both halves keep their input order.

The Event struct is declared in the starter and the harness constructs and reads it — do not rename the struct or its fields, or nothing will compile.

The hidden case runs a 500 000-event log with half of it removed, and asserts at most 20 heap allocations for the whole operation.

The three answers, and how the budget separates them

Measured on exactly this case:

log.extract_if(.., pred).collect()                  17 allocations
drain into two fresh Vecs, then reassign `*log`     34 allocations
log.remove(i) in a loop                              0 allocations, times out

The middle one is what most people write, and it is correct. It rebuilds the retained half into a brand new vector and then throws away the old backing store, which is why it doubles the count — and, invisibly, why it holds twice the memory at its peak.

The third one is what people write when they hear “don’t rebuild”. It allocates nothing at all and it is catastrophically slow: each remove(i) shifts every later element down one, so removing 250 000 items from a 500 000 item vector moves on the order of $10^{11}$ bytes. That is the shape of an accidental quadratic — no allocation, no warning, no lint, just a request that never comes back.

The first one does the whole job in a single pass over the vector, moving each survivor at most once. extract_if is the operation you want, and this problem exists so that you meet it, because most standard libraries have no equivalent and so most people have never looked for one.

The error in the starter

The starter reaches for retain, which is the right family of operation:

error[E0507]: cannot move out of `*e` which is behind a shared reference

retain‘s predicate has signature FnMut(&T) -> bool. It lends you each element so you can inspect it and answer yes or no. It does not give it to you, because at that moment the element is still in the vector — retain has not yet decided what to do with it, and handing out ownership of something that is still there would leave a hole.

So retain can drop elements but cannot hand them back, and removed.push(*e) is asking for exactly that. That is not a limitation to work around — it is the reason extract_if exists as a separate method:

log.extract_if(.., |e| e.ts < cutoff).collect()

extract_if removes the matching elements from the vector and yields them as an iterator, so ownership transfers cleanly and the survivors close up behind them in one pass. Its first argument is a range — pass .. for the whole vector.

If you are attached to retain, the legitimate escape is to add #[derive(Clone)] to Event and push a clone — and now you are allocating a copy of every removed element, which is precisely the cost you were trying to avoid.

::: question retain gives you &T. What if you genuinely need to modify the survivors as you filter? Use retain_mut, whose predicate is FnMut(&mut T) -> bool. Without it you get:

error[E0594]: cannot assign to `e.ts`, which is behind a `&` reference

which is E0507’s sibling: E0507 is “you cannot take it”, E0594 is “you cannot change it”. Both come from the same fact — the predicate holds a shared borrow — and both are fixed by choosing the method whose signature grants what you need. Rust’s collection APIs tend to come in these small families (iter/iter_mut/into_iter, get/get_mut, retain/retain_mut), and the suffix is always telling you which kind of access you are being handed. :::

drain has a surprise in it

let removed: Vec<Event> = log.drain(..).collect();

drain(range) returns an iterator over the removed elements. The thing that catches people is what happens if you do not consume it:

log.drain(..);   // the elements are removed anyway

When the Drain iterator is dropped, its destructor finishes the job — removing everything in the range and closing the gap — whether or not you ever called next. That is deliberate: it keeps the vector in a consistent state no matter how you abandon the iteration. But it means drain is not lazy in the way filter is, and a stray drain(..) on a line by itself is a data-losing statement, not a no-op.

(extract_if behaves the same way for the range you gave it.)

The general number

Filtering a million-element Vec of integers, rebuild versus in place:

v.iter().copied().filter(..).collect()     0.420 ms
v.retain(..)                               0.211 ms

Two times faster, and one allocation rather than a doubling sequence of them. Not a life-changing constant — but it is free, it reads better, and unlike the rebuild it does not double peak memory. Reach for the in-place method first and rebuild only when you actually want a second collection.

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