Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Vec::reserve should use alloc_excess #71383

Open
hsivonen opened this issue Apr 21, 2020 · 7 comments
Open

Vec::reserve should use alloc_excess #71383

hsivonen opened this issue Apr 21, 2020 · 7 comments
Labels
A-allocators Area: Custom and system allocators A-collections Area: `std::collection` C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@hsivonen
Copy link
Member

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 hsivonen added the C-bug Category: This is a bug. label Apr 21, 2020
@hsivonen
Copy link
Member Author

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
Copy link
Member Author

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 Mark-Simulacrum added the T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. label Apr 21, 2020
@Mark-Simulacrum
Copy link
Member

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
Copy link
Member

Amanieu commented Apr 21, 2020

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.

@jonas-schievink jonas-schievink added A-allocators Area: Custom and system allocators A-collections Area: `std::collection` C-enhancement Category: An issue proposing an enhancement or a PR with one. and removed C-bug Category: This is a bug. labels Apr 21, 2020
@hsivonen
Copy link
Member Author

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
Copy link
Member

Amanieu commented Apr 21, 2020

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
Copy link
Member

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-allocators Area: Custom and system allocators A-collections Area: `std::collection` C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

5 participants