Add a "shrink-if-excessive" API to Vec

[scottmcm]

Proposal

Problem statement

Stealing from steffahn in https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/31?u=scottmcm:

I think Vec is at least missing some sort of generic shrink()/garbage_collect()/... function with good asymptotics, so that if you called it after every potentially-len-shrinking operation it wouldn’t make your program accidentally-quadratic the way that overuse of shrink_to_fit can.

If it isn't the default, it should at least be easy to manually use Vec as a dynamic array with (only) a constant factor memory overhead, if you want to.

Motivating examples or use cases

After a .collect() or .retain(…), where you know you're not going to be pushing for a while so you'd like to not be wasting too much capacity, but aren't worried about it being exactly anything (since reallocating to save one or two items is probably a waste of time, and doesn't actually reduce memory usage).

Having something to write after the warning in https://doc.rust-lang.org/std/vec/struct.Vec.html#impl-FromIterator%3CT%3E-for-Vec%3CT%3E, as something like "You can call the ______ method after doing the operation if you want to avoid excessive remaining capacity".

Solution sketch

// in alloc::vec

impl<T, A: Allocator> Vec<T, A> {
    /// If this vector's `.capacity()` is much larger than its `.len()`,
    /// then `.shrink_to_fit()` it, otherwise do nothing.
    /// 
    /// For example, you might want to call this after doing a `retain`
    /// on a particularly-large vector that has a chance of removing
    /// most of the elements, but where you wouldn't want to 
    /// `.shrink_to_fit()` unconditionally since that's a waste of
    /// CPU if only a few items were removed.
    /// 
    /// Note that "much larger" is intentionally unspecified here,
    /// just like how `reserve` does not specify its growth strategy.
    /// **Do not** use it in any situation where you need a particular
    /// capacity exactly.
    /// 
    /// Beware calling this in a loop, as if that loop sometimes adds
    /// things to the container, this can cause quadratic complexity
    /// for things that would otherwise have been linear.
    /// 
    /// For now, only a few basic things are guaranteed:
    /// - This is *idempotent*: calling it multiple times (without otherwise
    ///   changing the vector between the calls) does the same as
    ///   calling it just once would do.
    /// - If *all* you do on an empty, zero-capacity vector is a sequence
    ///   of `push`es, then there's no need to call this as it'd do nothing.
    /// - In a loop that *monotonically decreases* the length of a vector,
    ///   calling this every iteration will not itself cause quadratic behaviour.
    fn shrink(&mut self) {
        if self.capacity() ⋙ self.len() {
            self.shrink_to_fit();
        }
    }
}

Alternatives

• shrink might be too short a name for something that can still be very costly if misused, so shrink_to_reasonable or shrink_if_profitable or something might be better. But at the same time since it's less risky than a full shrink_to_fit, giving it a more convenient name might be better.
• We could give more or fewer guarantees.

Links and related work

rust-lang/rust#120091

https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/31?u=scottmcm

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[pitaj]

Just concerning implementation: Should it not instead shrink to the smallest possible power of two capacity? I think "shrink to len.next_power_of_two()" is a much easier and less arbitrary algorithm. It also makes sense as an inverse of the growth factor.

[scottmcm]

Should it not instead shrink to the smallest possible power of two capacity?

I don't think so. If I happen to have a capacity-257 vector, I don't want it to shrink to 256. That's a waste of cycles.

That said, I'd certainly like to -- like in reserve -- want to leave things open enough that it can be delegated to the allocator to make smarter decisions about whether shrinking is worth it.

It also makes sense as an inverse of the growth factor.

The initial implementation I'd propose here is something along the lines of

if (v.cap() - v.len()) > cmp::max(v.len(), RawVec<T>::MIN_NON_ZERO_CAP)

which, yes, is an inverse of the growth factor.

(The growth factor is doubling, not rounding up to a power of two.)

[okaneco]

I think users interested in using this function would want to control the strategy or load factor rather than trust the implementation choice.

Something like this with a float, integer ratio, or strategy enum argument type.

fn shrink_with_factor(&mut self, load_factor: f32) -> bool;

Users may want to know if the resize operation was executed so the function could return bool or Option<NonZeroUsize> of the number of elements v_old.cap() - v_new.cap() the vec was shrunk by.

[hanna-kruppe]

I agree with the problem statement and motivation. But it would be unfortunate to introduce a new easy way to be accidentally quadratic. The “beware of calling this in a loop that adds items” advice rules out some valid use cases, and is not essential for bounding excess capacity.

I think it’s desirable and easily possible to keep the same amortized time complexity for basically any usage pattern — even if you call shrink() after every other Vec operation it may be significantly slower but “only” by a reasonable constant factor. Even v.reserve_exact(2*v.capacity()); v.shrink(); can be “merely” a waste of Θ(cap) time, asymptotically the same as the cost of reserving the excess capacity in the first place.

Basically, just choose the threshold (function) for when to shrink the capacity so that there’s always Θ(cap) distance between the length right after “normal” (not requested via reserve) growth and the length where it’ll shrink again. For a fixed growth factor X, that means don’t shrink until length < epsilon * (1/X) * capacity for some positive constant epsilon < 1. (The initial implementation suggested by @scottmcm would be epsilon = 1, which has worse asymptotics.) This is the textbook solution, usually analyzed for push/pop operations only, but I think it works more generally.

[scottmcm]

I think users interested in using this function would want to control the strategy or load factor rather than trust the implementation choice.

I don't think so, because if you want to control it exactly then you already have all the functionality you need, between reserve_exact and shrink_to.

To me, the point of this is that it's the obvious "just do this after a collect or retain that you're not going to push onto" thing, without needing to make choices for things like "well should I pass 1½ or φ or 2 or ...?"

[the8472]

I think we have to be careful here and implement some hysteresis - making the shrinking a bit less aggressive than the growth logic - so that the capacity wouldn't oscillate between 2 states around each breaking point.
That kind of subtlety would also be a reason to put this in std so people don't roll their own.

TC noted in today's libs meeting that he'd call this after each work item to make the memory footprint more tightly follow what's needed, to avoid lingering bloat. So that would essentially be calling it in a loop, albeit an outer loop.

/// Beware calling this in a loop, as if that loop sometimes adds
/// things to the container, this can cause quadratic complexity
/// for things that would otherwise have been linear.

The wording doesn't seem quite right. If you only add items to a vec and don't remove anything then shrinking should be a noop and provide the same amortized O(1) behavior. So the effective behavior depends on the insert/remove/shrink patterns and I don't think any of those would be O(n²), just decaying from O(1) to O(n)?

[pitaj]

Agreed, can someone produce an example case where this would become accidentally quadratic?

[scottmcm]

By "quadratic" in the description I meant that the overall algorithm would be quadratic, not shrink itself, like how using reserve_exact(1) makes a push loop become quadratic even though each reserve_exact is still only linear.

So something like a loop that does push + pop + pop + shrink every iteration, maybe? Where that push forces a reallocation after the shink just left no capacity -- which I think is the right thing for shrink to do, since in the "it's after a collect that might have reused an allocation" case I wouldn't expect it to leave extra capacity if it did choose to reallocate.

[pitaj]

But in that case, it's not quadratic overall - the shrinking would happen once at most, the rest of the time the "capacity double length" condition is not met for the actual shrink.

You would have to be pretty creative, maybe something like "pop length/2+1 times, shrink, push" repeatedly.

If we want to defend against something like that, we'd want to leave some extra space behind sometimes. One option is to shrink to the smallest possible power of two. In many cases the growth of capacity follows powers of two thanks to the 2x growth factor, so the shrinking would reflect the growth.

[programmerjake]

what happens when you have v.len() == 16, v.capacity() == 32 and you do:

for _ in 0..1000 {
    v.shrink(); // now capacity == 16
    v.push(1); // has to realloc so capacity == 32
    v.pop(); // back where we started
}

I think it might be better to shrink only if the capacity is more than twice the length, and not shrink if it's less or equal to twice the length, that way you avoid bad cases like the above.

[programmerjake]

for comparison: num_bigint::BigUInt shrinks when len() < capacity() / 4:
https://docs.rs/num-bigint/0.4.6/src/num_bigint/biguint.rs.html#866-868

[pitaj]

I don't disagree. To be clear, I would propose something like this

if (cap - len) > cmp::max(len, MIN_NON_ZERO_CAP) {
    self.shrink_to(len.next_power_of_two());
}

[scottmcm]

One option is to shrink to the smallest possible power of two.

I really don't see why a power of two is special here. And that proposed implementation has the problem that len=129, cap=259 shrinks to 256, which is a waste -- it's silly to reallocate just to drop the capacity by about 1%, especially in an API that exists to avoid such unhelpful reallocations.

We can add slack (to use the word finger trees use for why they have 1..=4 element digits instead of just 2..=3) without needing to privilege any particular thresholds. (Like the BigUint example that was given.)

---

I think it might be better to shrink only if the capacity is more than twice the length

Yes, that's why I used > and not >= in #553 (comment)

[hanna-kruppe]

@scottmcm

So something like a loop that does push + pop + pop + shrink every iteration, maybe? Where that push forces a reallocation after the shink just left no capacity -- which I think is the right thing for shrink to do, since in the "it's after a collect that might have reused an allocation" case I wouldn't expect it to leave extra capacity if it did choose to reallocate.

In the “it’s a collect that might have reduced an allocation” case, why not just use shrink_to_fit or shrink_to? Rust already has the tools to shrink capacity aggressively. What’s missing is a way that can’t be accidentally quadratic even in the face of growing and shrinking length. This requires coordinating with the (unspecified) default growth policy. If you only care about absolute or relative excess capacity in a collection you’re not going to grow any more, you can already implement whatever exact policy you want outside the standard library out of len(), capacity(), and shrink_to().

Edit: to be clear, the approach I’m emphasizing will also result in shrinking to 0 excess capacity whenever it does shrink. It just schedules the shrinks to avoid quadratic complexity in cases like the push; pop; pop; shrink loop.

[the8472]

We discussed this during today's libs-API meeting. There was some skepticism whether we can provide a method with the right heuristics that would satisfy everyone's needs since those needs may be workload-dependent. There was also the question how common the problem is.

So we'd like to know how often this comes up, what it is used for and which heuristics were used when this was implemented manually.

[programmerjake]

So we'd like to know how often this comes up, what it is used for and which heuristics were used when this was implemented manually.

one use case that may eventually switch to using this method:

for comparison: num_bigint::BigUInt shrinks when len() < capacity() / 4: https://docs.rs/num-bigint/0.4.6/src/num_bigint/biguint.rs.html#866-868

[the8472]

After some more discussion we'd like to know whether the goal of adding the shrink method is a) to have some "just do the right thing" sort of convenience or whether it's about b) the issue that user code shouldn't rely on/try to match implementation details - the growth strategy - which we could also expose as something like Vec::calc_capacity_growth(&self, reserve: usize) -> usize which user code could then use to calculate their own shrink_to goal.

[hanna-kruppe]

It’s not clear the me that “limit excess capacity without becoming accidentally quadratic” can be implemented with just calc_capacity_growth and no further assumptions about the growth strategy. The relevant question for this kind of shrinking isn’t “how much further would the capacity grow if I reserved even more now” but rather how the vector might have grown to its current capacity and how it would grow again if it was shrunk now. If the growth strategy is more complex than “always multiply capacity by a constant factor” then you can’t conclude one from the other.

Also, keep in mind that some use cases want to do the “shrink if excessive” check very frequently, e.g., after every operation that may remove elements from the vector. A built-in implementation can make this quite efficient because it can combine knowledge of the growth strategy with the leeway it has in picking the exact threshold for shrinking. For example, if the growth strategy is “double capacity but grow by at least 4 elements” the shrink check could be something like (cap + 12) / 3 < len instead of a more complicated expression that mirrors the growth function exactly on the whole domain.