Vec::reserve should use alloc_excess

[hsivonen]

When calling reserve() on a Vec whose capacity is zero, afterwards the capacity() method always returns the exact argument that was passed to reserve(). Even though the contract of reserve() allows Vec to make the capacity larger than requested, if the previous capacity is zero, Vec does not make use of this. When the underlying allocator is bucketed, rounding to the bucket size never wastes memory, so Vec should use alloc_excess to make the slop available to the user.

Use case: We're going to write at least best_case items and at most worst_case items, such that best_case < worst_case, but we don't know how many items exactly. The common case can be expected to be close to best_case but often at least one more. It would make sense to first allocate for best_case rounded up to allocator bucket size, then start writing, then if not everything fits, resize to worst_case, write the rest, and finally resize to the size actually written and shrink_to_fit().

This would guarantee at most three allocations and in the common case one.

This issues comes up often with low-level string code.

[hsivonen]

This would guarantee at most three allocations and in the common case one.

Simply allocating for worst_case first would result in two allocations in the common case.

[hsivonen]

For clarity: This is about writing via mutable slice, not by pushing items one-by-one, so the application code benefits from knowing the rounded-to-allocation-bucket capacity and it's not just a matter of realloc internals.

[Mark-Simulacrum]

Seems like a reasonable change to me, let's cc @Amanieu who has been working on the allocator APIs recently I believe.

I suspect a PR would be the best way to fix this, though.

[Amanieu]

I believe that this has already been done in #70362: RawVec will use the excess returned by the AllocRef::alloc/grow methods. However the issue is that GlobalAlloc doesn't return an excess, so it doesn't do anything with the default global allocator.

[hsivonen]

However the issue is that GlobalAlloc doesn't return an excess, so it doesn't do anything with the default global allocator.

Is there any chance of this getting fixed? glibc has malloc_usable_size and macOS has malloc_size, so this information is available. I have no idea how expensive it would be to call these as a matter of routine, though.

[Amanieu]

The proper solution to this is to deprecate GlobalAlloc in favor of AllocRef, which is the plan of the allocators WG: rust-lang/wg-allocators#48 (cc @TimDiekmann)

If you are looking for a short-term solution then we could add an unstable usable_size method to GlobalAlloc which would default to a no-op. The System allocator would then override this method as appropriate for the target.

[TimDiekmann]

Can confirm, that this was changed in #70362.

alloc_excess does not exists anymore in AllocRef. Instead, alloc and grow returns the actual allocated size as MemoryBlock. Vec relies on RawVec, which internally uses the returned size from alloc and grow to return the maximum usable capacity (since #70362). As @Amanieu stated, this has no effect in the current Vec implementation, as Vec relies on Global, which does not have an excess-API. In the implementation of AllocRef for Global, alloc and grow returns the requested size as excess.