# Needlessly weak promises on vector capacity?

#1

Continuing the discussion from [Solved] In place (128*N)-elem Vec<f32> into N-elem Vec<Vec<f32> of 128 size>:

Can somebody explain to me why methods of `Vec` like `shrink_to_fit` are so reluctant to provide guarantees about capacity when it is clearly always possible to produce a `Vec` where `len == cap`?

1 Like
[Solved] In place (128*N)-elem Vec<f32> into N-elem Vec<Vec<f32> of 128 size>
How often is memory copied/moved around?
#2

The language in the shrink_to_fit docs is just saying that even if you call shrink_to_fit on a vec of 5 u32s, the underlying allocation may not be exactly 20 bytes. For example, with jemalloc, itâ€™ll round up to 32 bytes.

Itâ€™s not really a super meaningful distinction for user code, IMO.

#3

Shrinks the capacity of the vector as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the vector that there is space for a few more elements.

As I read this, â€śitâ€ť refers to â€śthe capacity of the vector,â€ť and thus the rest of the sentence is saying that `vec.capacity() >= vec.len()`. This should be rephrased so that it is clearly talking about the size of the backing allocation.

The language of `reserve_exact` is also misleading:

Reserves the minimum capacity for exactly `additional` more elements to be inserted in the given `Vec<T>`. After calling `reserve_exact` , capacity will be greater than or equal to `self.len() + additional`. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future insertions are expected.

This one says that the `cap` field of the vector may not be equal to `len`, which is indeed a fair statement after reviewing the implementation. But the second paragraph seems to be implying that this is due to the will of the allocator; that is not the case here! (the cases where `cap > requested` on exit are simply the cases where `cap > requested` on entry!)

#4

I believe it is up to the allocator. If you ask the allocator for space for N more elements, it may return more than that (ie the whole notion of â€śusable_sizeâ€ť), eg allocators using size classes.

It doesnâ€™t look like `RawVec` queries the `Alloc::usable_size` anywhere (at least I couldnâ€™t find it while on my phone), however.

#5

So, if I have understood correctly (please correct me if Iâ€™m wrong, I am just basing this post on how I have understood this thread), to summarise in practice:

• `shrink_to_fit`, `reserve_exact`, etc. do manage to drop as much extra capacity as possible. By that I mean that it will be the same capacity as a fresh `Vec::with_capacity`. That is, user-wise, there is no way to allocate less.

• the only subtlety here is thus that a `.shrink_to_fit` cannot be used to guarantee that calling `.push` right after will trigger a reallocation: since the allocator may not be able to give 1-byte-precise â€śchunksâ€ť, there is always the possibility of the actual capacity being rounded up to some size (e.g., `Vec::with_capacity(30)` may actually allocate `32` bytes thus allowing 2 extra `.push`es before triggering a reallocation).

All in all, those seem like overly cautious â€śwarningsâ€ť, since the â€śwastedâ€ť capacity only depends from the allocator implementation, and in general should be negligible. (I have to admit that for a moment I had a doubt (like @ExpHP it seems) as to whether `Vec::from(v.into_boxed_slice())` occupied less memory than `{ v.shrink_to_fit(); v }`)

#6

I believe that the above is a correct analysis. Allocators always have their own strategy for how they partition storage into useful sizes. Very seldom is the allocated area exactly the same size as that requested; usually it is only expected to be within some factor đťś€ (e.g., 1.25 or 1.5) of the requested size. Allocators with power-of-2 granularity are very common, particularly for small requested sizes.

#7

Can we please stop using the phrase â€śactual capacityâ€ť to refer to the size of the allocation? The term is ambiguous and can be interpreted to mean â€śthe actual value of the capacity field.â€ť This in turn creates unnecessary confusion for people who need to write `unsafe` code that messes with the `capacity` field.

• the only subtlety here is thus that a `.shrink_to_fit` cannot be used to guarantee that calling `.push` right after will trigger a reallocation: since the allocator may not be able to give 1-byte-precise â€śchunksâ€ť, there is always the possibility of the actual capacity being rounded up to some size ( e.g. , `Vec::with_capacity(30)` may actually allocate `32` bytes thus allowing 2 extra `.push` es before triggering a reallocation).

I believe you are right that pushing to a vector where `len == cap` does not necessarily reallocate, but youâ€™re off in where, how, and when this occurs. The implementation of `Vec` does not know or care what the actual size of the allocated area is; it only cares about the `capacity` field.

• `Vec::<u8>::with_capacity(30)` creates a vector where `len == 0`, `cap == 30`. Always. No matter what.
• When `push` is called 31 times on such a vector, without conferring with the allocator, the implementation of Vec decides that the new `cap` shall be `60`.
• `Vec` blindly tells the allocator to reallocate the buffer to support a capacity of `60`.
• Supposing that the allocated space is already large enough to support 60 elements (because e.g. the allocator rounds up to powers of 4), `<A as Alloc>::realloc` is free to simply return the same pointer after doing nothing; but this is all opaque to the implementation of `Vec`.
2 Likes
#8

Thank you @ExpHP, now itâ€™s crystal clear (the expression actual capacity did show that things werenâ€™t that clear in that regard. I forgot that vec is an abstraction built on top of the allocator abstraction) â€¦ but I am back to square one: if `.shrink_to_fit()` sets the capacity to the length (asking a truncating realloc to the Allocator, who may return a pointer to a chunk whose usable size is nevertheless bigger than the new requested capacity), then `{ v.shrink_to_fit; v }` and `Vec::from(v.into_boxed_slice())` should indeed be â€śequivalentâ€ť. Or at least the documentation warnings should be removed.