# Vec is asymmetric with memory handling

**URL:** <https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449>\
**Category:** libs\
**Created:** [February 23, 2025, 6:24pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449 "2025-02-23T18:24:49Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![steffahn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steffahn/32/13288_2.png) [@steffahn](https://internals.rust-lang.org/u/steffahn)\
**Post date:** [February 23, 2025, 1:30am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/1 "2025-02-23T01:30:13Z")

</div>

This thread is hosting the discussion split from the following section of a reply from @tczajka in [What is the purpose of std? - #9 by tczajka](https://internals.rust-lang.org/t/what-is-the-purpose-of-std/22436/9)

* * *

> [@What is the purpose of std?](https://internals.rust-lang.org/t/what-is-the-purpose-of-std/22436/9):
>
> For `Vec` it bugs me that it's asymmetric with memory handling: it doesn't release memory automatically when shrinking which makes it a poor default design for lists because you're risking allocating a lot more memory than you're using (e.g. O(n^2) vs O(n)). And now that design choice is stuck in `std` forever.

---

<div class="post-metadata">

**Author:** ![jrose](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jrose/32/9591_2.png) [@jrose](https://internals.rust-lang.org/u/jrose)\
**Post date:** [February 23, 2025, 1:33am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/2 "2025-02-23T01:33:04Z")

</div>

It depends a lot on whether your constrained resource is memory or CPU time. I will say, though, that I don’t know of _any_ stdlib, in any language, where shrinking the default growable contiguous storage type gives up capacity, either on every call or amortized. That doesn’t mean your idea is a bad one, just that no one else has decided to make it the default, either.

It does help that you can build remove-and-shrink on top of remove, but not the other way around.

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [February 22, 2025, 10:34pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/4 "2025-02-22T22:34:08Z")

</div>

That's the behaviour that makes sense in 99% cases.

You certainly don't want your vecs to unpredictably cause two reallocs where zero would suffice because you've popped one element too many before pushing again.

---

<div class="post-metadata">

**Author:** ![Vorpal](https://avatars.discourse-cdn.com/v4/letter/v/aca169/32.png) [@Vorpal](https://internals.rust-lang.org/u/Vorpal)\
**Post date:** [February 22, 2025, 10:43pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/5 "2025-02-22T22:43:05Z")

</div>

The behaviour to not shrink automatically makes sense most of the time, e.g. when using a Vec as a scratch buffer that you keep growing and shrinking a lot. You don't want your stack of pending elements in a depth first search algorithm to shrink mid-algorithm for example.

I think that the "grow list really big once, then shrink it and keep it shrunk for a long time" use case is really rare. For those cases you can manually shrink the Vec. Arguably you should have built in a memory arena (that you reuse) and copied the final shrunk Vec out of that after you know the actual size.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [February 22, 2025, 10:54pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/6 "2025-02-22T22:54:01Z")

</div>

> [@HjVT](#):
>
> You certainly don't want your vecs to unpredictably cause two reallocs where zero would suffice because you've popped one element too many before pushing again.

> [@Vorpal](#):
>
> The behaviour to not shrink automatically makes sense most of the time, e.g. when using a Vec as a scratch buffer that you keep growing and shrinking a lot. You don't want your stack of pending elements in a depth first search algorithm to shrink mid-algorithm for example.

This seems like a micro-optimization. I can see use cases for non-releasing-buffers, but I just don't think it should be the default because it's not the conservative choice. We're talking about constant-time overhead for shrinking (amortized) vs possible quadratic (or worse) memory overhead.

Example: You have n vectors, and you pass n elements through all of them. You might end up with O(n^2) memory allocated even though you only ever have n elements.

---

<div class="post-metadata">

**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\
**Post date:** [February 23, 2025, 12:12am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/7 "2025-02-23T00:12:51Z")

</div>

> [@tczajka](#):
>
> This seems like a micro-optimization.

I'd say that quite the opposite, trying to conserve memory for 1% of use cases is the micro-optimization.

> [@tczajka](#):
>
> Example: You have n vectors, and you pass n elements through all of them. You might end up with O(n^2) memory allocated even though you only ever have n elements.

If you only ever have n elements, you should just intoiter+collect.  
If you have a non-restricted stream of elements, you won't ever grow the first n-1 vectors to n elements.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [February 23, 2025, 12:32am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/8 "2025-02-23T00:32:54Z")

</div>

> [@HjVT](#):
>
> trying to conserve memory for 1% of use cases is the micro-optimization

No no, worst-case guarantees are super-important. You can't call an asymptotic worst-case improvement a "micro-optimization".

> [@HjVT](#):
>
> If you only ever have n elements, you should just intoiter+collect. If you have a non-restricted stream of elements, you won't ever grow the first n-1 vectors to n elements.

I think you may have misunderstood my example. You have n vectors, and n elements. You move those elements in some unpredictable fashion between the vectors. Each vector may grow to n elements at some point in the process. The sum of lengths is always bounded by n.

To me this issue makes `Vec` a much lower-lever tool than what I'd expect from a general-purpose collection type. You basically have to manually worry about memory management to some extent whenever you're removing elements, or accept what amounts to memory leaks.

---

<div class="post-metadata">

**Author:** ![zackw](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/zackw/32/2071_2.png) [@zackw](https://internals.rust-lang.org/u/zackw)\
**Post date:** [February 23, 2025, 1:57am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/9 "2025-02-23T01:57:23Z")

</div>

> [@tczajka](#):
>
> We're talking about constant-time overhead for shrinking (amortized) vs possible quadratic (or worse) memory overhead.

Shrinking and growing may both need to move the allocation, which means the behavior you want can inflict quadratic time overhead on some algorithms (for instance, imagine a bag-of-pages allocator and a stack whose size oscillates across a size bucket boundary).

---

<div class="post-metadata">

**Author:** ![hanna-kruppe](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hanna-kruppe/32/6540_2.png) [@hanna-kruppe](https://internals.rust-lang.org/u/hanna-kruppe)\
**Post date:** [February 23, 2025, 7:37am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/10 "2025-02-23T07:37:56Z")

</div>

Shrinking can be done in amortized constant time per operation (same as for growing), as long as the number of inserts/removals between any two capacity changes is proportional to the length. For example, doubling capacity when full and halving capacity when length \< capacity/3 works fine. You’re right that in the scenario @tczajka is talking about one may spend O(n^2) time on shrinking. But even without shrinking, getting each of n vectors to O(n) capacity requires O(n^2) steps of inserting/removing elements, so the time complexity wouldn’t get worse from shrinking.

However, I agree that the current default behavior is fine: in many common use cases shrinking is unnecessary and costs performance, while the use cases that benefit from shrinking can still easily build it on top of what Vec provides. It’s _possible_ to get bad asymptotic complexity by using the methods that exist, but ultimately that’s the responsibility of the programmer. The documentation clearly states that Vec never shrinks its capacity automatically, just like it says that `remove` takes O(len) time in the worst case.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [February 23, 2025, 8:27am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/11 "2025-02-23T08:27:43Z")

</div>

> [@jrose](#):
>
> I don’t know of _any_ stdlib, in any language, where shrinking the default growable contiguous storage type gives up capacity

Python `list` will [give up capacity](https://github.com/python/cpython/blob/5ec4bf86b7f4455432aebace996ef390ae3e9302/Objects/listobject.c#L111).

> [@zackw](#):
>
> Shrinking and growing may both need to move the allocation, which means the behavior you want can inflict quadratic time overhead on some algorithms (for instance, imagine a bag-of-pages allocator and a stack whose size oscillates across a size bucket boundary).

I'm not suggesting one should release capacity every time the length decreases. That would be a bad idea indeed. Release only when the length decreases sufficiently, e.g. double capacity when len \> capacity, halve capacity when len \< capacity / 4. This would ensure good amortized behavior for any sequence of calls and any allocator.

---

<div class="post-metadata">

**Author:** ![jrose](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jrose/32/9591_2.png) [@jrose](https://internals.rust-lang.org/u/jrose)\
**Post date:** [February 23, 2025, 8:42am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/12 "2025-02-23T08:42:53Z")

</div>

TIL, thank you!

---

<div class="post-metadata">

**Author:** ![Nemo157](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nemo157/32/11585_2.png) [@Nemo157](https://internals.rust-lang.org/u/Nemo157)\
**Post date:** [February 23, 2025, 8:48am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/13 "2025-02-23T08:48:48Z")

</div>

> [@tczajka](#):
>
> Release only when the length decreases sufficiently, e.g. double capacity when len \> capacity, halve capacity when len \< capacity / 4. This would ensure good amortized behavior for any sequence of calls and any allocator.

I find it quite common to use a vec as a scratchpad that gets cleared and then refilled with a similar amount of items in a loop. Far more common than removing just some items.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [February 23, 2025, 9:47am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/14 "2025-02-23T09:47:36Z")

</div>

> [@Nemo157](#):
>
> I find it quite common to use a vec as a scratchpad that gets cleared and then refilled with a similar amount of items in a loop. Far more common than removing just some items.

Sure. Optimally you'd have two types: one type for such optimized scratchpads with manually controlled capacity, and one collection type that automatically manages capacity.

---

<div class="post-metadata">

**Author:** ![burntsushi](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/burntsushi/32/279_2.png) [@burntsushi](https://internals.rust-lang.org/u/burntsushi)\
**Post date:** [February 23, 2025, 12:55pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/15 "2025-02-23T12:55:01Z")

</div>

> [@What is the purpose of std?](https://internals.rust-lang.org/t/what-is-the-purpose-of-std/22436/9):
>
> For `Vec` it bugs me that it's asymmetric with memory handling: it doesn't release memory automatically when shrinking which makes it a poor default design for lists because you're risking allocating a lot more memory than you're using (e.g. O(n^2) vs O(n)). And now that design choice is stuck in `std` forever.

As someone who has been [bitten badly by this](https://github.com/BurntSushi/aho-corasick/commit/474393be8d6be7418699e0a9ef8e00fe2fd9cd75), I don't agree with you that it's a bad default. As others have said, I think it's far more common to want the extra capacity to be there. It's somewhat rarer to need to care about excess capacity from a memory usage perspective. The `aho-corasick` example I linked is I think the only time this has been relevant to me (that I know about) in ten years of using Rust. In contrast, I've relied on excess capacity hanging around for "scratch buffer" use cases _countless_ times.

The suggestion to "just have two different types" likely [underestimates the effects that such designs have on decision paralysis](https://old.reddit.com/r/learnrust/comments/1iishpg/lazycell_vs_lazylock_vs_oncecell_vs_oncelock_vs/), especially when it's as subtle as small tweaks to the capacity amortization trade-off. So I disagree that having two widespread types is "optimal."

---

<div class="post-metadata">

**Author:** ![gbutler](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gbutler/32/3670_2.png) [@gbutler](https://internals.rust-lang.org/u/gbutler)\
**Post date:** [February 23, 2025, 12:58pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/16 "2025-02-23T12:58:49Z")

</div>

Can you provide a concrete example of this problem?

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [February 23, 2025, 1:19pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/17 "2025-02-23T13:19:56Z")

</div>

> [@gbutler](#):
>
> Can you provide a concrete example of this problem?

My example is when I was working on a big integer library that was using `Vec` internally, and had to be careful to shrink the vectors when the numbers get smaller. I ended up implementing a wrapper `Vec`-like type.

> [@burntsushi](#):
>
> In contrast, I've relied on excess capacity hanging around for "scratch buffer" use cases _countless_ times.

I would think in most user cases the memory allocation strategy isn't that important. `malloc` is not _that_ slow. So you have to count many of these as a tie.

It's interesting that for `HashMap` the opposite choice was made. It's using a slower hasher by default, giving up some performance to avoid very troublesome edge cases where the complexity might blow up. Similarly, `rand` uses a good generator by default with slower performance, to avoid troublesome cases.

Perhaps this could be solved similar to `HashMap`, where `Vec` is parametrized with some "growth strategy" parameter that you can tweak according to your use case.

---

<div class="post-metadata">

**Author:** ![burntsushi](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/burntsushi/32/279_2.png) [@burntsushi](https://internals.rust-lang.org/u/burntsushi)\
**Post date:** [February 23, 2025, 1:22pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/18 "2025-02-23T13:22:46Z")

</div>

> [@tczajka](#):
>
> I would think in most user cases the memory allocation strategy isn't that important. `malloc` is not _that_ slow. So you have to count many of these as a tie.

You would think so, but it's not true in practice. I've done this optimization so many times I can't count it. It's so common that it makes its way into API design. (e.g., "Provide a `&mut` borrow to this thing so that it can be reused.") So no, I absolutely do not count these as a tie.

---

<div class="post-metadata">

**Author:** ![Vorpal](https://avatars.discourse-cdn.com/v4/letter/v/aca169/32.png) [@Vorpal](https://internals.rust-lang.org/u/Vorpal)\
**Post date:** [February 24, 2025, 7:17am UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/19 "2025-02-24T07:17:24Z")

</div>

> [@tczajka](#):
>
> It's interesting that for `HashMap` the opposite choice was made. It's using a slower hasher by default, giving up some performance to avoid very troublesome edge cases where the complexity might blow up.

Yes, I personally think this was the wrong choice. For my use cases I don't need DOS resistance at all, and I have seen significant speedups from switching hash function a couple of times. Rustc itself uses a different hash for example.

---

<div class="post-metadata">

**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\
**Post date:** [February 24, 2025, 5:41pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/20 "2025-02-24T17:41:48Z")

</div>

> [@Vorpal](#):
>
> Yes, I personally think this was the wrong choice. For my use cases I don't need DOS resistance at all, and I have seen significant speedups from switching hash function a couple of times. Rustc itself uses a different hash for example.

I have a third opinion, you could call it the middle ground.

I think the default hasher doesn't need to be cryptographically secure, but it should be a randomized [universal](https://en.wikipedia.org/wiki/Universal_hashing) hash function. Those can be very simple and fast, much faster than `SipHash`, and they actually also prevent DOS attacks in many scenarios (depending on the exact attack scenario), and importantly, they have mathematical upper bounds on the expected number of collisions independently of inputs, as opposed to the arbitrary hash functions that C++ has that can easily cause a lot of collisions even without trying.

---

<div class="post-metadata">

**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\
**Post date:** [February 24, 2025, 7:34pm UTC](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/21 "2025-02-24T19:34:42Z")

</div>

Isn't that what siphash is? It's essentially a randomized function, randomized by its key.

[Next page](https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449.md?page=2)
