10 ms·

() memory leak footgun

180 points by muglug 3y ago

teknopaul 3y ago
Over allocating maps and arrays in standard libs is not really a memory "leak" . Other langs do it.
- gipp 3y ago
  Yeah, came here to say this. Still an interesting post, but the title implies a much more serious problem
- dylan604 3y ago
  [flagged]
  - GrumpySloth 3y ago
    There is nothing unsafe about allocating more memory than necessary.
  - hyperpape 3y ago
    Please go read Wikipedia: https://en.wikipedia.org/wiki/Memory_safety https://en.wikipedia.org/wiki/Memory_safety.
  - phanimahesh 3y ago
    Memory safety has not been violated here.
  - unshavedyak 3y ago
    Being so quick to jump this sarcastic gun on something so clearly unrelated to memory safety (even if it was a leak, which it isn't!) is not a great look.
- hyperpape 3y ago
  Agreed. In the Haskell world, "space leak" is used to refer to a lazy computation that overallocates because of laziness (classic example being the difference between foldl and foldr or maybe that's foldl' and foldr'--I forget some details/cannot be bothered to think about folds right now). I've personally stolen the terminology for a computation that temporarily holds on to a bunch of unneeded memory.
- beltsazar 3y ago
  After skimming the first few paragraphs, I almost commented something similar to yours. But after reading it until the end, the problem is more nuanced than that. The issue is more about reusing memory that has been allocated when you "convert" (in Rust term: into_iter()) a Vec to another Vec. More surprisingly, the reuse still happens even when the new Vec has a different type than the original Vec's type. You should read the whole post—it's more interesting than I (and you) thought.
- wredue 3y ago
  You’re right, but it’s (I agree; incorrectly) been called a memory leak for a long time, to inappropriately over allocate/not free resources. Coming from my java days, they called this a memory leak there too. It’s definitely a more inappropriate term in rust, where memory leak has a definite meaning already.
- hulium 3y ago
  Conceptually, collect seems to create a new vector. In that case you would expect that the memory of the old vector is freed. The library tries to be smart and reuses the old vector as an (undocumented?) optimization. So the old memory that is no longer needed is not released. Whether you call that a leak or not, Rust is known for its predictability. Allocating 200x the memory which a programmer would expect if he doesn't know the implementation details is bad.
- wavemode 3y ago
  The semantics are kind of besides the point, I think. This allocation reuse behavior was meant as an optimization, but the real-world programs this is meant to be "optimizing" run significantly slower in beta than they did in stable. So there is a bug here no matter how you look at it.
- deleted 3y ago
  [deleted]
pif 3y ago
> It’s also an illustration of how an optimization in one place can lead to bugs downstream by violating programmers’ expectations. 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.
- thfuran 3y ago
  Respecting both is much better than respecting only the latter.
- phkahler 3y ago
  >> Programmers’ expectations are not codified and do not need to be respected That's pretty negative attitude - my immediate gut response was "and neither do yours". But Rust isn't an ISO standard and is still in development. Even if we do think in those terms, people developing a standard have IMHO an obligation to the people who will be using the standard.
  - binary132 3y ago
    To be a bit pedantic, the people using the C++ standard are mostly compiler engineers.
    - tialaramex 3y ago
      I mean sure, so for those people WG21 does them a great service, in most cases they can say "Oh that's IFNDR" [Ill-formed; No Diagnostic Required] or "That's UB" and so it's not the compiler's fault your program doesn't work and they can close your ticket as NOTABUG if they want. My guess is that all or almost-all non-trivial C++ projects trigger IFNDR and thus have no actual meaning per the ISO standard language. They do work, more or less, but that's just convention and can be taken away at any time or for any reason. Header files, use of concepts, unfortunate algorithmic goofs, careless naming, there are a billion† ways to trigger IFNDR in C++ and by definition that's fatal to your correctness. † A billion is likely an overestimate, but WG21 has no formal inventory of IFNDR in the sprawling ISO document so, who knows.
burntsushi 3y ago
Cross posting my comment from reddit[1] because I think it's interesting. ----- Nice post. I love calling attention to this. Just a few months ago, I ran into the ~same~ similar problem, although it wasn't caused by `collect()`. It was caused by "normal" `Vec` usage: https://github.com/BurntSushi/aho-corasick/commit/474393be8d6be7418699e0a9ef8e00fe2fd9cd75 https://github.com/BurntSushi/aho-corasick/commit/474393be8d... The issue appeared when building large Aho-Corasick automatons. Otherwise, it usually doesn'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's normal memory usage. Especially when it's coming from the automaton representation that you know is less memory efficient. (What I'm talking about here is something I called a "non-contiguous NFA." The aho-corasick crate also has a "contiguous NFA" and a DFA. The "contiguous NFA" uses one contiguous `Vec` allocation with a bunch of bit-packing tricks.) 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.) 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'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`. But why was I using a bunch of little `Vec`s in the first place? It's because this is the "non-contiguous" 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, "sure, the non-contiguous NFA isn't designed to be fast. It just needs to get us started." But still, `pyahocorasick` only has one Aho-Corasick implementation (the `aho-corasick` crate has 3). So it must be doing something differently. 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. 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`! [1]: https://old.reddit.com/r/rust/comments/199jycb/identifying_rusts_collect_memory_leak_footgun/kifh982/ https://old.reddit.com/r/rust/comments/199jycb/identifying_r... [2]: https://pypi.org/project/ahocorasick-rs/ https://pypi.org/project/ahocorasick-rs/ [3]: https://pypi.org/project/pyahocorasick/ https://pypi.org/project/pyahocorasick/ [4]: https://docs.rs/aho-corasick/latest/aho_corasick/struct.AhoCorasick.html#method.memory_usage https://docs.rs/aho-corasick/latest/aho_corasick/struct.AhoC... [5]: https://github.com/BurntSushi/aho-corasick/commit/31bb1fc30da69ab8575483c55e15384d09f4c88d https://github.com/BurntSushi/aho-corasick/commit/31bb1fc30d...
the_mitsuhiko 3y ago
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. Someone already filed this as a bug: https://github.com/rust-lang/rust/issues/120091 https://github.com/rust-lang/rust/issues/120091
- tialaramex 3y ago
  This re-use trick seems clever, but definitely needed more consideration before merging IMO. Re-use where we can determine the size & alignment are a perfect match ought to be a win, but the other cases seem very situational. And The8472's attitude here seems unlikely to lead to a better Rust.
  - IshKebab 3y ago
    Yeah I feel like it should reallocate if the size difference is great.
WirelessGigabit 3y ago
I don't think it's a memory leak. It's re-using the same space of the underling array. It's allocated. Dropping the Vec will release the memory. In v1 you put in 128 containers is with each 1024 boxes. 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. The fact that capacity doubles when you remove the as u8 is... normal. You reuse the space, so you can fix 2u8 in the space of 1u16. The problem here is more that this the optimization causes a Vec<T> -> Vec<Y> where sizeof(T) > sizeof(Y) to have much more capacity than expected. Which IS a valid bug report. Bug again, not a memory leak.
- vlovich123 3y ago
  It seems like you have a better grasp on the problem than I. I understand why capacity in terms of number of elements doubles. But why did he end up using 200x more memory? Is it that the transient memory used the 18GiB and then he reduced it to vector of elements that were 200x smaller? Or is it that there’s some other problem that when you collect, it’s reallocating 2x using the wrong type to do the computation?
  - 0x457 3y ago
    Because it doubles in every node and OP has 300k of them[1]. It's not a leak, since memory is...well...accounted for and easily freed by either dropping Vec or calling shirk_to_fit. IMO it's expected behavior. Honestly, if I had 300k Vecs, I would call `shrink_to_fit` even without that optimization. 1: Since the edge list calculation logic is run for one node at a time in sequence, the fact that it temporarily uses 132kb of memory would normally not be a problem at all. However, the new collect() optimization meant that that internal storage was being preserved in the final vec which got inserted into the list of edge lists, thus keeping around that 132kb of obsolete memory forever. Multiply that by 300k nodes and suddenly you’ve leaked the computer’s entire RAM.
    - vlovich123 3y ago
      Ah right. Vec of vecs and the interior Vec has wasted capacity due to the reduction of the element size. Thanks!
stcredzero 3y ago
It took me a few extra seconds to parse the headline. ("footgun" didn't help) Is <Vec<_>>() perhaps to become another ¯\_(ツ)_/¯ ?
- avgcorrection 3y ago
  Yes? What about unamused Vec?
- tialaramex 3y ago
  It's interesting that HN zapped the second colon. The headline here (at time of my posting) is: "Identifying Rust's collect:<Vec<_>>() memory leak footgun" but the actual title of the blog post is: "Identifying Rust's collect::<Vec<_>>() memory leak footgun" That extra colon matters to Rust's syntax.
- unshavedyak 3y ago
  Not sure what you're asking. At risk of loosely explaining what you may already know, `<Vec<_>>` is a generic parameter `<T>` with the type `T` specified as `Vec`. Vec also has a param, `<_>`, where the type is ignored - as the compiler can figure that out. Sidenote, `<Vec<_>>` is missing the best part - the fish head, to become `::<Vec<_>>`, aka `::<>` - the Turbo Fish :D I admit to using this syntax more than necessary just so i can write a turbofish :D edit: Wait no, `<>` is the head - isn't it. hah. So i guess it's missing the fins? /shrug
renewiltord 3y ago
Great write-up. Thank you. I wouldn't have guessed. The upshot of this whole thing is that Vec is for mutable collections and when you're done you make a boxed slice.
invpt 3y ago
I appreciate the mention of Box<[T]>. I've never (or at least very rarely?) seen people using it, even in rustc, although I'm sure there's somewhere in the compiler that uses it. I've kind of gotten the feeling that Box<[T]> 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.
- ironhaven 3y ago
  Another rust type you should look out for is Box<str>In my rust code I find a lot more uses of Box<str> rather than Box<[T]>. Strings are often fixed length identifiers or usernames that get passed around frequently and stored in data structures. Box<str> can be a drop-in replacement in a surprising amount of code
  - zozbot234 3y ago
    Arc<str> is an atomically ref-counted string, also quite useful in async or multi-threaded code where (unlike w/ Box) you sometimes can't know in advance which task will drop the last reference to some data.
  - bobbylarrybobby 3y ago
    Box<str> is used pervasively in the rust compiler instead of String for exactly this reason. Basically every string of code the compiler looks at is, unsurprisingly, constant.
    - steveklabnik 3y ago
      Yeah, the general concept here is https://en.wikipedia.org/wiki/String_interning https://en.wikipedia.org/wiki/String_interning, Box<str> is great for it.
- tsnl 3y ago
  Another downside of Box<T> is that Vec::into_boxed_slice copies all elements from the source vector. Vec::shrink_to_fit does not appear to copy. This is based on the stable docs.
loeg 3y ago
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 >2) to be worth the possible optimization but probably still worth doing at capacity small multiples of length.
- Groxx 3y ago
  Is reusing an allocation while changing its size a thing you expect to be able to do? I would believe that some languages/systems/etc can do that, but it certainly feels like an exception rather than a rule. Reuse generally means the whole block of memory is retained, from what I've seen, because you'd have to track that half-freed memory for reuse somehow and that has some associated cost. (A compacting-GC language would be a reasonable exception here, for example)
  - loeg 3y ago
    > Is reusing an allocation while changing its size a thing you expect to be able to do? It's something you should expect to be able to try to do. The underlying allocator may reject the request depending on context (maybe it is works for large sizes only, for example). This is provided by Rust's Allocator trait realloc_in_place() API, which returns CannotReallocInPlace if it isn't possible. For Vec::collect, in the event that the storage cannot be reused smaller in place, I think it would be reasonable to free it and allocate an appropriately sized buffer instead.
- rstuart4133 3y ago
  > This is a pretty surprising behavior. This optimisation crosses the line into "too clever by half". Once a Rust programmers groks how Vec's work their mental model of how capacity is allocated simple, so simple they hardly need thing about it's implications as they write code. This optimisation breaks that simple model badly, and you would have to be really focused to realise it's about to bite you as the code streams off your finger tips. Consequently this "optimisation" is almost certainly going to cause a lot of code to using far more memory than expected. You get the same results with filter(): let mut v = vec![1,2,3]; v.push(4); println!("len {} cap {}", v.len(), v.capacity()); let v = v.into_iter().map(|x| x+1).filter(|_x| false).collect::<Vec<_>>(); println!("len {} cap {}", v.len(), v.capacity()); len 4 cap 6 len 0 cap 6 Despite being in some sense "correct", I'd consider that result a bug. One fix would be to examine the result, and if it breaks the programmers expectations badly (by say using more than twice the memory needed) it does a shink_to_fit() for you. Since the programmer is probably expecting a new vector to be generated it isn't a surprising outcome.
vlovich123 3y ago
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?
- hedgehog 3y ago
  I think the behavior is that if you have a Vec of u128 (say 1000), filter that to fewer elements (say 10), and then collect it into a Vec of u32 you might expect the resulting value to be around 40 bytes but in beta Rust it is 16000 bytes. In current Rust the collect would cause a new 10 element Vec of u32 to be allocated, in beta it reuses the original larger allocation. The author's code is doing a bit more but essentially when moving to beta Rust the new optimization caused memory usage to increase by a big multiple.
  - vlovich123 3y ago
    Ok. I missed that there’s a filter step that compounds the problem. The more I read the less this sounds like a bug and more like application code is missing a shrink_to_fit and was relying on a pessimization. That being said, it’s also not an unreasonable expectation on the user’s behalf that the size and capacity don’t get crazy different in code as innocuous and idiomatic as this. I wonder how the open bug will end up training itself.
    - hedgehog 3y ago
      Someone here linked an open ticket for this issue. In the comments at least one person made basically the same argument that holding on to a potentially large % of memory is a surprising sharp edge, meanwhile shrinking the Vec and perhaps allocating is unsurprising behavior. Requiring many additional defensive shrink_to_fit calls to avoid this problem seems like the wrong tradeoff but I don't write enough Rust to have a strong opinion.
      - 3y ago
notso411 3y ago
[dead]
Groxx 3y ago
While I agree this is a bit surprising... I don't see literally anything in the docs for `collect()` that implies anything about memory behaviors. You get a collection, nothing more is guaranteed. 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).
- deathanatos 3y ago
  I would say I don't (or now, didn't) expect collect to be able to know that there is an allocation under there, since that's not part of Iterator's interface. I.e., the docs could call out that there aren't such implied behaviors, and that in some circumstances, it might reuse the allocation, but that that's not guaranteed. (And ideally, offer me info on what to do if I do want certain guarantees about the allocation of the Vec.) Warding off what I think is a reasonable, but wrong, assumption, is well within the scope of the docs.
pornel 3y ago
Here's the code performing the allocation reuse: https://github.com/rust-lang/rust/blob/25f8d01fd8bda339612d0c0a8844173a09205f7c/library/alloc/src/vec/spec_from_iter.rs#L43 https://github.com/rust-lang/rust/blob/25f8d01fd8bda339612d0... It's not supposed to waste more space than a regular `collect()` or `push()` would when growing the capacity exponentially.
ardel95 3y ago
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 "collect once read many times" use-cases. 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 / lazy transformation behavior this optimization introduces, I would be looking at working with an iterator with a bunch of functinoal transforms. And if I'm calling .collect() it's because I want to convert the iterator into a data structure optimized for reads. But I can also see how others would land on the other end, and hence the challenges for the library authors.
0881023458168 3y ago
Kiki
0881023458168 3y ago
8485582898
deleted 3y ago
[deleted]

180 points by muglug 3y ago

teknopaul 3y ago

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

gipp 3y ago
Yeah, came here to say this. Still an interesting post, but the title implies a much more serious problem
dylan604 3y ago
[flagged]
- GrumpySloth 3y ago
  There is nothing unsafe about allocating more memory than necessary.
- hyperpape 3y ago
  Please go read Wikipedia: https://en.wikipedia.org/wiki/Memory_safety https://en.wikipedia.org/wiki/Memory_safety.
- phanimahesh 3y ago
  Memory safety has not been violated here.
- unshavedyak 3y ago
  Being so quick to jump this sarcastic gun on something so clearly unrelated to memory safety (even if it was a leak, which it isn't!) is not a great look.
hyperpape 3y ago
Agreed. In the Haskell world, "space leak" is used to refer to a lazy computation that overallocates because of laziness (classic example being the difference between foldl and foldr or maybe that's foldl' and foldr'--I forget some details/cannot be bothered to think about folds right now). I've personally stolen the terminology for a computation that temporarily holds on to a bunch of unneeded memory.
beltsazar 3y ago
After skimming the first few paragraphs, I almost commented something similar to yours. But after reading it until the end, the problem is more nuanced than that. The issue is more about reusing memory that has been allocated when you "convert" (in Rust term: into_iter()) a Vec to another Vec. More surprisingly, the reuse still happens even when the new Vec has a different type than the original Vec's type. You should read the whole post—it's more interesting than I (and you) thought.
wredue 3y ago
You’re right, but it’s (I agree; incorrectly) been called a memory leak for a long time, to inappropriately over allocate/not free resources. Coming from my java days, they called this a memory leak there too. It’s definitely a more inappropriate term in rust, where memory leak has a definite meaning already.
hulium 3y ago
Conceptually, collect seems to create a new vector. In that case you would expect that the memory of the old vector is freed. The library tries to be smart and reuses the old vector as an (undocumented?) optimization. So the old memory that is no longer needed is not released. Whether you call that a leak or not, Rust is known for its predictability. Allocating 200x the memory which a programmer would expect if he doesn't know the implementation details is bad.
wavemode 3y ago
The semantics are kind of besides the point, I think. This allocation reuse behavior was meant as an optimization, but the real-world programs this is meant to be "optimizing" run significantly slower in beta than they did in stable. So there is a bug here no matter how you look at it.
deleted 3y ago
[deleted]

pif 3y ago

> It’s also an illustration of how an optimization in one place can lead to bugs downstream by violating programmers’ expectations. 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.

thfuran 3y ago
Respecting both is much better than respecting only the latter.
phkahler 3y ago
>> Programmers’ expectations are not codified and do not need to be respected That's pretty negative attitude - my immediate gut response was "and neither do yours". But Rust isn't an ISO standard and is still in development. Even if we do think in those terms, people developing a standard have IMHO an obligation to the people who will be using the standard.
- binary132 3y ago
  To be a bit pedantic, the people using the C++ standard are mostly compiler engineers.
  - tialaramex 3y ago
    I mean sure, so for those people WG21 does them a great service, in most cases they can say "Oh that's IFNDR" [Ill-formed; No Diagnostic Required] or "That's UB" and so it's not the compiler's fault your program doesn't work and they can close your ticket as NOTABUG if they want. My guess is that all or almost-all non-trivial C++ projects trigger IFNDR and thus have no actual meaning per the ISO standard language. They do work, more or less, but that's just convention and can be taken away at any time or for any reason. Header files, use of concepts, unfortunate algorithmic goofs, careless naming, there are a billion† ways to trigger IFNDR in C++ and by definition that's fatal to your correctness. † A billion is likely an overestimate, but WG21 has no formal inventory of IFNDR in the sprawling ISO document so, who knows.

burntsushi 3y ago

Cross posting my comment from reddit[1] because I think it's interesting. ----- Nice post. I love calling attention to this. Just a few months ago, I ran into the ~same~ similar problem, although it wasn't caused by `collect()`. It was caused by "normal" `Vec` usage: https://github.com/BurntSushi/aho-corasick/commit/474393be8d6be7418699e0a9ef8e00fe2fd9cd75 https://github.com/BurntSushi/aho-corasick/commit/474393be8d... The issue appeared when building large Aho-Corasick automatons. Otherwise, it usually doesn'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's normal memory usage. Especially when it's coming from the automaton representation that you know is less memory efficient. (What I'm talking about here is something I called a "non-contiguous NFA." The aho-corasick crate also has a "contiguous NFA" and a DFA. The "contiguous NFA" uses one contiguous `Vec` allocation with a bunch of bit-packing tricks.) 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.) 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'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`. But why was I using a bunch of little `Vec`s in the first place? It's because this is the "non-contiguous" 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, "sure, the non-contiguous NFA isn't designed to be fast. It just needs to get us started." But still, `pyahocorasick` only has one Aho-Corasick implementation (the `aho-corasick` crate has 3). So it must be doing something differently. 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. 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`! [1]: https://old.reddit.com/r/rust/comments/199jycb/identifying_rusts_collect_memory_leak_footgun/kifh982/ https://old.reddit.com/r/rust/comments/199jycb/identifying_r... [2]: https://pypi.org/project/ahocorasick-rs/ https://pypi.org/project/ahocorasick-rs/ [3]: https://pypi.org/project/pyahocorasick/ https://pypi.org/project/pyahocorasick/ [4]: https://docs.rs/aho-corasick/latest/aho_corasick/struct.AhoCorasick.html#method.memory_usage https://docs.rs/aho-corasick/latest/aho_corasick/struct.AhoC... [5]: https://github.com/BurntSushi/aho-corasick/commit/31bb1fc30da69ab8575483c55e15384d09f4c88d https://github.com/BurntSushi/aho-corasick/commit/31bb1fc30d...

the_mitsuhiko 3y ago

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. Someone already filed this as a bug: https://github.com/rust-lang/rust/issues/120091 https://github.com/rust-lang/rust/issues/120091

tialaramex 3y ago
This re-use trick seems clever, but definitely needed more consideration before merging IMO. Re-use where we can determine the size & alignment are a perfect match ought to be a win, but the other cases seem very situational. And The8472's attitude here seems unlikely to lead to a better Rust.
- IshKebab 3y ago
  Yeah I feel like it should reallocate if the size difference is great.

WirelessGigabit 3y ago

I don't think it's a memory leak. It's re-using the same space of the underling array. It's allocated. Dropping the Vec will release the memory. In v1 you put in 128 containers is with each 1024 boxes. 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. The fact that capacity doubles when you remove the as u8 is... normal. You reuse the space, so you can fix 2u8 in the space of 1u16. The problem here is more that this the optimization causes a Vec<T> -> Vec<Y> where sizeof(T) > sizeof(Y) to have much more capacity than expected. Which IS a valid bug report. Bug again, not a memory leak.

vlovich123 3y ago
It seems like you have a better grasp on the problem than I. I understand why capacity in terms of number of elements doubles. But why did he end up using 200x more memory? Is it that the transient memory used the 18GiB and then he reduced it to vector of elements that were 200x smaller? Or is it that there’s some other problem that when you collect, it’s reallocating 2x using the wrong type to do the computation?
- 0x457 3y ago
  Because it doubles in every node and OP has 300k of them[1]. It's not a leak, since memory is...well...accounted for and easily freed by either dropping Vec or calling shirk_to_fit. IMO it's expected behavior. Honestly, if I had 300k Vecs, I would call `shrink_to_fit` even without that optimization. 1: Since the edge list calculation logic is run for one node at a time in sequence, the fact that it temporarily uses 132kb of memory would normally not be a problem at all. However, the new collect() optimization meant that that internal storage was being preserved in the final vec which got inserted into the list of edge lists, thus keeping around that 132kb of obsolete memory forever. Multiply that by 300k nodes and suddenly you’ve leaked the computer’s entire RAM.
  - vlovich123 3y ago
    Ah right. Vec of vecs and the interior Vec has wasted capacity due to the reduction of the element size. Thanks!

stcredzero 3y ago

It took me a few extra seconds to parse the headline. ("footgun" didn't help) Is <Vec<_>>() perhaps to become another ¯\_(ツ)_/¯ ?

avgcorrection 3y ago
Yes? What about unamused Vec?
tialaramex 3y ago
It's interesting that HN zapped the second colon. The headline here (at time of my posting) is: "Identifying Rust's collect:<Vec<_>>() memory leak footgun" but the actual title of the blog post is: "Identifying Rust's collect::<Vec<_>>() memory leak footgun" That extra colon matters to Rust's syntax.
unshavedyak 3y ago
Not sure what you're asking. At risk of loosely explaining what you may already know, `<Vec<_>>` is a generic parameter `<T>` with the type `T` specified as `Vec`. Vec also has a param, `<_>`, where the type is ignored - as the compiler can figure that out. Sidenote, `<Vec<_>>` is missing the best part - the fish head, to become `::<Vec<_>>`, aka `::<>` - the Turbo Fish :D I admit to using this syntax more than necessary just so i can write a turbofish :D edit: Wait no, `<>` is the head - isn't it. hah. So i guess it's missing the fins? /shrug

renewiltord 3y ago

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

invpt 3y ago

I appreciate the mention of Box<[T]>. I've never (or at least very rarely?) seen people using it, even in rustc, although I'm sure there's somewhere in the compiler that uses it. I've kind of gotten the feeling that Box<[T]> 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.

ironhaven 3y ago
Another rust type you should look out for is Box<str>In my rust code I find a lot more uses of Box<str> rather than Box<[T]>. Strings are often fixed length identifiers or usernames that get passed around frequently and stored in data structures. Box<str> can be a drop-in replacement in a surprising amount of code
- zozbot234 3y ago
  Arc<str> is an atomically ref-counted string, also quite useful in async or multi-threaded code where (unlike w/ Box) you sometimes can't know in advance which task will drop the last reference to some data.
- bobbylarrybobby 3y ago
  Box<str> is used pervasively in the rust compiler instead of String for exactly this reason. Basically every string of code the compiler looks at is, unsurprisingly, constant.
  - steveklabnik 3y ago
    Yeah, the general concept here is https://en.wikipedia.org/wiki/String_interning https://en.wikipedia.org/wiki/String_interning, Box<str> is great for it.
tsnl 3y ago
Another downside of Box<T> is that Vec::into_boxed_slice copies all elements from the source vector. Vec::shrink_to_fit does not appear to copy. This is based on the stable docs.

loeg 3y ago

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 >2) to be worth the possible optimization but probably still worth doing at capacity small multiples of length.

Groxx 3y ago
Is reusing an allocation while changing its size a thing you expect to be able to do? I would believe that some languages/systems/etc can do that, but it certainly feels like an exception rather than a rule. Reuse generally means the whole block of memory is retained, from what I've seen, because you'd have to track that half-freed memory for reuse somehow and that has some associated cost. (A compacting-GC language would be a reasonable exception here, for example)
- loeg 3y ago
  > Is reusing an allocation while changing its size a thing you expect to be able to do? It's something you should expect to be able to try to do. The underlying allocator may reject the request depending on context (maybe it is works for large sizes only, for example). This is provided by Rust's Allocator trait realloc_in_place() API, which returns CannotReallocInPlace if it isn't possible. For Vec::collect, in the event that the storage cannot be reused smaller in place, I think it would be reasonable to free it and allocate an appropriately sized buffer instead.
rstuart4133 3y ago
> This is a pretty surprising behavior. This optimisation crosses the line into "too clever by half". Once a Rust programmers groks how Vec's work their mental model of how capacity is allocated simple, so simple they hardly need thing about it's implications as they write code. This optimisation breaks that simple model badly, and you would have to be really focused to realise it's about to bite you as the code streams off your finger tips. Consequently this "optimisation" is almost certainly going to cause a lot of code to using far more memory than expected. You get the same results with filter(): let mut v = vec![1,2,3]; v.push(4); println!("len {} cap {}", v.len(), v.capacity()); let v = v.into_iter().map(|x| x+1).filter(|_x| false).collect::<Vec<_>>(); println!("len {} cap {}", v.len(), v.capacity()); len 4 cap 6 len 0 cap 6 Despite being in some sense "correct", I'd consider that result a bug. One fix would be to examine the result, and if it breaks the programmers expectations badly (by say using more than twice the memory needed) it does a shink_to_fit() for you. Since the programmer is probably expecting a new vector to be generated it isn't a surprising outcome.

vlovich123 3y ago

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?

hedgehog 3y ago
I think the behavior is that if you have a Vec of u128 (say 1000), filter that to fewer elements (say 10), and then collect it into a Vec of u32 you might expect the resulting value to be around 40 bytes but in beta Rust it is 16000 bytes. In current Rust the collect would cause a new 10 element Vec of u32 to be allocated, in beta it reuses the original larger allocation. The author's code is doing a bit more but essentially when moving to beta Rust the new optimization caused memory usage to increase by a big multiple.
- vlovich123 3y ago
  Ok. I missed that there’s a filter step that compounds the problem. The more I read the less this sounds like a bug and more like application code is missing a shrink_to_fit and was relying on a pessimization. That being said, it’s also not an unreasonable expectation on the user’s behalf that the size and capacity don’t get crazy different in code as innocuous and idiomatic as this. I wonder how the open bug will end up training itself.
  - hedgehog 3y ago
    Someone here linked an open ticket for this issue. In the comments at least one person made basically the same argument that holding on to a potentially large % of memory is a surprising sharp edge, meanwhile shrinking the Vec and perhaps allocating is unsurprising behavior. Requiring many additional defensive shrink_to_fit calls to avoid this problem seems like the wrong tradeoff but I don't write enough Rust to have a strong opinion.
    - 3y ago

notso411 3y ago

[dead]

Groxx 3y ago

While I agree this is a bit surprising... I don't see literally anything in the docs for `collect()` that implies anything about memory behaviors. You get a collection, nothing more is guaranteed. 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).

deathanatos 3y ago
I would say I don't (or now, didn't) expect collect to be able to know that there is an allocation under there, since that's not part of Iterator's interface. I.e., the docs could call out that there aren't such implied behaviors, and that in some circumstances, it might reuse the allocation, but that that's not guaranteed. (And ideally, offer me info on what to do if I do want certain guarantees about the allocation of the Vec.) Warding off what I think is a reasonable, but wrong, assumption, is well within the scope of the docs.

pornel 3y ago

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

ardel95 3y ago

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 "collect once read many times" use-cases. 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 / lazy transformation behavior this optimization introduces, I would be looking at working with an iterator with a bunch of functinoal transforms. And if I'm calling .collect() it's because I want to convert the iterator into a data structure optimized for reads. But I can also see how others would land on the other end, and hence the challenges for the library authors.

0881023458168 3y ago

Kiki

0881023458168 3y ago

8485582898

deleted 3y ago

[deleted]