Subtleties of boxed slice allocations

[TomFryersMidsummer]

I think the follow sentence is a bit misleading.

Alternatively, a boxed slice can be constructed directly from an iterator with Iterator::collect, avoiding the need for reallocation.

The implementation of Box::<[_]>::from_iter is

impl<I> FromIterator<I> for Box<[I]> {
    fn from_iter<T: IntoIterator<Item = I>>(iter: T) -> Self {
        iter.into_iter().collect::<Vec<_>>().into_boxed_slice()
    }
}

I think this means that collecting an iterator with a known length into a boxed slice will be exactly one allocation, but if the iterator has an unknown length, then the Vec<_> will re-allocate a few times while collecting, and then (usually) re-allocate again to shrink to fit the boxed slice.

Here's an example on Compiler Explorer. The boxed slice version has some extra code, which I assume is for the re-allocation.

This trade-off seems fairly fundamental: your collection either grows one element at a time, in O(n²) time, or uses amortisation, overshoots, and has to row back.