Identifying Rust's collect:<Vec<_>>() memory leak footgun

I don&#x27;t think it&#x27;s a memory leak. It&#x27;s re-using the same space of the underling array. It&#x27;s allocated. Dropping the Vec will release the memory.<p>In v1 you put in 128 containers is with each 1024 boxes.<p>Then v2 is taking out the first box out of each container, tossing the container and putting the box at the space where the container was, packing them.<p>The fact that capacity doubles when you remove the as u8 is... normal. You reuse the space, so you can fix 2<i>u8 in the space of 1</i>u16.<p>The problem here is more that this the optimization causes a Vec&lt;T&gt; -&gt; Vec&lt;Y&gt; where sizeof(T) &gt; sizeof(Y) to have much more capacity than expected.<p>Which IS a valid bug report. Bug again, not a memory leak.

I appreciate the mention of Box&lt;[T]&gt;. I&#x27;ve never (or at least very rarely?) seen people using it, even in rustc, although I&#x27;m sure there&#x27;s somewhere in the compiler that uses it. I&#x27;ve kind of gotten the feeling that Box&lt;[T]&gt; is frowned upon as a needless optimization because the one-word storage difference is so minimal, but I appreciate having the immutable size semantics as a way of ensuring no extra allocations occur by way of the methods on Vec.

This is a good time to check how your code performs in beta vs stable. This particular case is new in beta and it would be interesting to catch regressions before they land.<p>Someone already filed this as a bug: <a href="https:&#x2F;&#x2F;github.com&#x2F;rust-lang&#x2F;rust&#x2F;issues&#x2F;120091">https:&#x2F;&#x2F;github.com&#x2F;rust-lang&#x2F;rust&#x2F;issues&#x2F;120091</a>

Over allocating maps and arrays in standard libs is not really a memory &quot;leak&quot; . Other langs do it.

This is a pretty surprising behavior. Reusing the allocation without shrinking when the resulting capacity will be within 1.0-2.0x the length: seems reasonable, not super surprising. Reusing the allocation without shrinking when the resulting capacity will be a large multiple of the (known) length: pretty surprising! My intuition is that this is too surprising (at capacity &gt;2) to be worth the possible optimization but probably still worth doing at capacity small multiples of length.

I’ve read the article and I’m still lost as to how this optimization results in a 200x discrepancy between capacity and length. Was the mapped element size 200x smaller in this case? Or is there some bug where repeated mappings like this cause a 2x growth based on the previous element size instead of the target element size?

This is a good example of the type of challenges you face as an author of widely used library. I can see a lot of scenarios where an optimization like this would bring benefits. But there are also many where it would hurt performance (not to mention memory usage), including most &quot;collect once read many times&quot; use-cases.<p>But I think the real thing for me is that this violates the principle of least surprise. If I wanted the type of memory reuse &#x2F; lazy transformation behavior this optimization introduces, I would be looking at working with an iterator with a bunch of functinoal transforms. And if I&#x27;m calling .collect() it&#x27;s because I want to convert the iterator into a data structure optimized for reads.<p>But I can also see how others would land on the other end, and hence the challenges for the library authors.

While I agree this is a bit surprising... I don&#x27;t see <i>literally anything</i> in the docs for `collect()` that implies anything about memory behaviors. You get <i>a collection</i>, nothing more is guaranteed.<p>If you want specific memory behavior, you really do have to use a method that intends to do that. Like `shrink_to_fit()` (mentioned in the article).

&gt; It’s also an illustration of how an optimization in one place can lead to bugs downstream by violating programmers’ expectations.<p>This touched upon a pet peeve of mine for its resemblance with all the talk about undefined behaviour in C and C++. Programmers’ expectations are not codified and do not need to be respected: international standards do.

Great write-up. Thank you. I wouldn&#x27;t have guessed. The upshot of this whole thing is that Vec is for mutable collections and when you&#x27;re done you make a boxed slice.

Here&#x27;s the code performing the allocation reuse:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;rust-lang&#x2F;rust&#x2F;blob&#x2F;25f8d01fd8bda339612d0c0a8844173a09205f7c&#x2F;library&#x2F;alloc&#x2F;src&#x2F;vec&#x2F;spec_from_iter.rs#L43">https:&#x2F;&#x2F;github.com&#x2F;rust-lang&#x2F;rust&#x2F;blob&#x2F;25f8d01fd8bda339612d0...</a><p>It&#x27;s not supposed to waste more space than a regular `collect()` or `push()` would when growing the capacity exponentially.

Cross posting my comment from reddit[1] because I think it&#x27;s interesting.<p>-----<p>Nice post. I love calling attention to this. Just a few months ago, I ran into the ~same~ similar problem, although it wasn&#x27;t caused by `collect()`. It was caused by &quot;normal&quot; `Vec` usage:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;BurntSushi&#x2F;aho-corasick&#x2F;commit&#x2F;474393be8d6be7418699e0a9ef8e00fe2fd9cd75">https:&#x2F;&#x2F;github.com&#x2F;BurntSushi&#x2F;aho-corasick&#x2F;commit&#x2F;474393be8d...</a><p>The issue appeared when building large Aho-Corasick automatons. Otherwise, it usually doesn&#x27;t matter too much because the absolute memory sizes are pretty small. But if your automaton uses 1GB of memory, then because of the excess capacity in a bunch of little `Vec` values, that usage could easily balloon to 2GB. And even at that size, _it was hard to notice that it was more than it should have been_! It is easy to just think that&#x27;s normal memory usage. Especially when it&#x27;s coming from the automaton representation that you know is less memory efficient. (What I&#x27;m talking about here is something I called a &quot;non-contiguous NFA.&quot; The aho-corasick crate also has a &quot;contiguous NFA&quot; and a DFA. The &quot;contiguous NFA&quot; uses one contiguous `Vec` allocation with a bunch of bit-packing tricks.)<p>But then someone actually reported an issue on the `ahocorasick_rs`[2] Python project (bindings to the `aho-corasick` crate) that the `pyahocorasick`[3] Python package (with a bespoke C implementation of Aho-Corasick) was using _substantially_ less memory. The contiguous NFA was still doing better, but the _peak_ memory usage of `ahocorasick_rs` was much much bigger than `pyahocorasick`. That prompted me to investigate and figure out what the heck was going wrong. (And this is one reason why benchmarks comparing tools or libraries are actually useful beyond just advertisements or flexing. They alert you to what is possible, and thus possibly push you to find bugs in your current implementation that might be otherwise easy to miss. In other words, benchmark comparisons can turn unknown unknowns into known unknowns.)<p>So since this prompted me to look very carefully at memory usage, I noticed that the memory usage reported by `AhoCorasick::memory_usage`[4] was substantially smaller than peak RSS memory usage in a simple reproduction program of the original issue reported to `ahocorasick_rs`. I eventually figured out that was because of the excess capacity used by a zillion tiny `Vec`s in the non-contiguous representation. I fixed _most_ of that by calling `shrink_to_fit()`. But as the commit linked above notes, it wasn&#x27;t really feasible to call `shrink_to_fit()` on all `Vec`s because that ended up with a non-trivial impact on construction time. And on top of all of that, memory usage was still worse than `pyahocorasick`.<p>But why was I using a bunch of little `Vec`s in the first place? It&#x27;s because this is the &quot;non-contiguous&quot; NFA. This is the thing that gets built from a list of patterns by first building a trie then filling in the failure transitions. That trie construction really demands random access mutation, which puts a constraint on your data structure choices. Plus, I had designed the contiguous NFA as a release valve of sorts that lifts this constraint. So I reasoned, &quot;sure, the non-contiguous NFA isn&#x27;t designed to be fast. It just needs to get us started.&quot; But still, `pyahocorasick` only has one Aho-Corasick implementation (the `aho-corasick` crate has 3). So it must be doing something differently.<p>It turns out that `pyahocorasick` uses linked lists! THE HORROR! But actually, they are a really good solution to this problem. As a Rust programmer, I reach for `Vec` first. But a C programmer reaches for linked lists first. And it turns out that linked lists are a much better fit here.<p>And so, I switched to linked lists[5]. (But using indices instead of pointers. Because of course. This is Rust. :-)) And now `ahocorasick_rs` uses less memory than `pyahocorasick`!<p>[1]: <a href="https:&#x2F;&#x2F;old.reddit.com&#x2F;r&#x2F;rust&#x2F;comments&#x2F;199jycb&#x2F;identifying_rusts_collect_memory_leak_footgun&#x2F;kifh982&#x2F;" rel="nofollow">https:&#x2F;&#x2F;old.reddit.com&#x2F;r&#x2F;rust&#x2F;comments&#x2F;199jycb&#x2F;identifying_r...</a><p>[2]: <a href="https:&#x2F;&#x2F;pypi.org&#x2F;project&#x2F;ahocorasick-rs&#x2F;" rel="nofollow">https:&#x2F;&#x2F;pypi.org&#x2F;project&#x2F;ahocorasick-rs&#x2F;</a><p>[3]: <a href="https:&#x2F;&#x2F;pypi.org&#x2F;project&#x2F;pyahocorasick&#x2F;" rel="nofollow">https:&#x2F;&#x2F;pypi.org&#x2F;project&#x2F;pyahocorasick&#x2F;</a><p>[4]: <a href="https:&#x2F;&#x2F;docs.rs&#x2F;aho-corasick&#x2F;latest&#x2F;aho_corasick&#x2F;struct.AhoCorasick.html#method.memory_usage" rel="nofollow">https:&#x2F;&#x2F;docs.rs&#x2F;aho-corasick&#x2F;latest&#x2F;aho_corasick&#x2F;struct.AhoC...</a><p>[5]: <a href="https:&#x2F;&#x2F;github.com&#x2F;BurntSushi&#x2F;aho-corasick&#x2F;commit&#x2F;31bb1fc30da69ab8575483c55e15384d09f4c88d">https:&#x2F;&#x2F;github.com&#x2F;BurntSushi&#x2F;aho-corasick&#x2F;commit&#x2F;31bb1fc30d...</a>

It took me a few extra seconds to parse the headline. (&quot;footgun&quot; didn&#x27;t help) Is<p><pre><code> &lt;Vec&lt;_&gt;&gt;() </code></pre> perhaps to become another<p><pre><code> ¯\_(ツ)_&#x2F;¯ ?</code></pre>

8485582898

Kiki