Chains versus loops: top-k, and a function that must not allocate

Two functions over the same slice, and one of them is graded on allocation behaviour, not just on its answer.

pub struct Item { pub id: u32, pub score: i64 }

pub fn top_k_by_score(items: &[Item], k: usize) -> Vec<u32>
pub fn count_matching(items: &[Item]) -> usize

top_k_by_score returns the ids of the k highest-scoring items, ordered by score descending, ties broken by id ascending. k == 0 gives an empty vector; k larger than the slice gives every id.

ids    = [1,  2,  3,  4]
scores = [10, 30, 20, 30],  k = 2   ->  [2, 4]
ids    = [3, 1, 2], scores = [7, 7, 7], k = 2  ->  [1, 2]

Keep a bounded structure of size k while you scan — a BinaryHeap you evict from — rather than sorting the whole input. For n items that is O(n log k) instead of O(n log n), and it is the shape you want when n is a stream and k is small.

count_matching returns how many items have a strictly positive score. It must allocate zero times. The test harness installs a counting global allocator, snapshots it around your call, and fails the case if the number moved.

Why the allocation check is here

These two lines return the same number:

items.iter().filter(p).collect::<Vec<_>>().len()   // allocates
items.iter().filter(p).count()                     // does not

The first builds a Vec, grows it by repeated reallocation (filter‘s size_hint lower bound is 0, so collect cannot pre-reserve — item 9.22), reads its length, and frees it. The second is a counter in a register.

Nothing in the type system distinguishes them and — as item 9.25 explains at length — clippy::needless_collect is allow-by-default, so the normal gate says nothing. That is exactly why this problem measures it instead of linting it. The starter ships the collect().len() version, and the failure message is:

count_matching allocated 1 time(s); a counting pipeline allocates nothing

Are iterators as fast as loops?

This is the question everyone arriving from C or C++ asks, and the honest answer is “usually, sometimes faster, occasionally much slower” — with a mechanism attached. Four measured pairs:

Absolute numbers depend on machine and allocator; the directions reproduce.

Row three is the one that surprises people. Indexing two slices in one loop forces two bounds checks per iteration, and LLVM usually cannot elide both. zip does the bounds reasoning once, structurally, so the inner loop has none. The iterator is not “as fast as” the loop; it is faster, because it carries more information.

Row four is the counterexample, and item 9.22 explains it: flatten reports size_hint (0, None), so collect reallocates its way up from nothing, while concat asks every inner slice for its length, allocates once, and memcpys.

The correct summary: iterators are free when the adaptor chain preserves length information and the closures inline. Not “iterators are always free”. Say the long version; the short one is wrong in both directions.

Measuring, if you go looking yourself

std::hint::black_box (stable since 1.66) is the standard way to stop the optimiser deleting a benchmark whose result is unused. Two caveats worth having before you trust a number:

• It is documented as best-effort and platform-dependent. It is a hint, not a barrier, and it makes no guarantees across compiler versions.
• Its input is still optimised. black_box(5 * 10) folds to 50 before the barrier ever applies. Wrap the input to the work, not the arithmetic: f(black_box(input)), not black_box(f(input)) — and usually both.

Also: measure a release build, run it more than once, and be suspicious of any difference under about 10%.

The tie rule, concretely

Getting “higher score first, then lower id first” out of a BinaryHeap takes a moment’s thought, because BinaryHeap is a max-heap and you want to evict the worst element.

Build a rank key where larger means better: (score, Reverse(id)) — higher score is larger, and for equal scores a smaller id makes Reverse(id) larger. Then store Reverse(key) in the heap, so pop() removes the smallest key, which is the worst of your current best k. At the end, drain the heap and sort descending by the same key.

std::cmp::Reverse is a one-field tuple struct whose Ord is its inner type’s, inverted. Nesting one inside the other is not a trick; it is the intended way to build mixed-direction orderings without writing impl Ord.

Grade is compile + tests + clippy -D warnings — plus, on this problem, the allocation counter.