Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.polybdenum.com

Post reply on HN
Print view View original

21–30 of 129 posts

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

#21

Post by vlovich123 »

cmrdporcupine wrote: post #18
burntsushi wrote: post #5

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/474393be8d... The issue appeared when building large Aho-Corasick automatons. Otherwise, it usually do…

What we need is a page-based Vec that mmaps (anon) for the storage but leaves the unused portions zero-bytes and therefore not part of RSS until actually required. (And when clearing/shrinking sections, madvise DONTNEED the pages). That is, the vec could expand to areas much larger than the actual used size, but this would have no effect on process RSS until those pages get dirtied with actual data.

That can be not a great idea for subtle reasons even though it does seem like a better design at first.

When you do the madvise, based on the contact of the API, the kernel has to do a TLB shoot down which is really expensive. And not just “expensive for my process” but expensive in terms of a significant slowdown for entire machine. Honestly you could probably DDOS a machine if you could reliably trigger that shootdown.

As such you want to be very very careful where you place that data structure.

For what it’s worth your memory allocator (or at least a good one like mimalloc or the non-gperftools newer tcmalloc) will do exactly as you mentioned where it will free memory back to the OS using advanced heuristics tested out at scale.

As for why a shoot down is needed, it’s so that a racing allocation call in another process doesn’t get that virtual address but be running on a core where the TLB points elsewhere (the core that did the allocation may not even be the one where it’s used).

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

#22

Post by cmrdporcupine »

cnity wrote: post #20
cmrdporcupine wrote: post #18

Earlier quoted context omitted.

What we need is a page-based Vec that mmaps (anon) for the storage but leaves the unused portions zero-bytes and therefore not part of RSS until actually required. (And when clearing/shrinking sections, madvise DONTNEED the pages). That is, the vec could expand to areas much larger than the actual used size, but this would have no effect on process RSS until those pages get dirtied with actual data.

Couldn't this obfuscate OOM type problems by not triggering actual memory issues until much later than the allocation?

Maybe? Depends on how you monitor and what your expectations are. But for workloads that use a lot of memory, and want to avoid wasteful empty allocations, or have sparse data, etc. it's a reasonable strategy.

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

#23

Post by cmrdporcupine »

vlovich123 wrote: post #21
cmrdporcupine wrote: post #18

Earlier quoted context omitted.

What we need is a page-based Vec that mmaps (anon) for the storage but leaves the unused portions zero-bytes and therefore not part of RSS until actually required. (And when clearing/shrinking sections, madvise DONTNEED the pages). That is, the vec could expand to areas much larger than the actual used size, but this would have no effect on process RSS until those pages get dirtied with actual data.

That can be not a great idea for subtle reasons even though it does seem like a better design at first. When you do the madvise, based on the contact of the API, the kernel has to do a TLB shoot down which is really expensive. And not just “expensive for my process” but expensive in terms of a significant slowdown for entire machine. Honestly you could probably DDOS a machine if you could reliably trigger that shootd…

Yes, well, I think you're right it's a lot about the contract of the API and the expectation of the user.

I'd certainly want intelligence (either by the user or by the framework) in how frequently you release pages back to the OS.

But the DONTNEED is really not the core of the value. It's being able to create vectors that don't fragment as badly.

And yes, you're right a decent allocator could help with this, and what I'm describing is really just a kind of specialized allocator.

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

#24

Post by burntsushi »

beltsazar wrote: post #17
burntsushi wrote: post #5

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/474393be8d... The issue appeared when building large Aho-Corasick automatons. Otherwise, it usually do…

> Just a few months ago, I ran into the same problem, although it wasn't caused by `collect()`. It was caused by "normal" `Vec` usage If it wasn't caused by `collect()`, then I suppose it's a related problem, but not the same problem. Your problem was caused by, as your commit message says, "ignorance [original: ignorant] of the broader effects of this strategy [double-when-full] in aggregate" The OP's problem, otoh,…

I feel like second sentence you quoted clarified that? "same problem" in this context means, "there is excess and unused capacity in the Vec." Your description is more precise, and at that level of precision, sure, they are not the "same problem." But yet, they share the same characteristic that is easy to forget: a `Vec` might have unused capacity leading to higher memory usage than you might expect otherwise if you aren't accounting for that unused capacity.

My phrasing is a reflection of what I think is a more universal lesson to draw from the blog, and one that is not provoked merely by how `collect()` works, but rather, the nature of growth amortization itself.

> This behavior is more surprising than the double-when-full strategy

I agree.

I updated my comment to use "similar" instead of "same."

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

#25

Post by wavemode »

teknopaul wrote: post #2

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

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.

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

#26

Post by WirelessGigabit »

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 -> Vec where sizeof(T) > sizeof(Y) to have much more capacity than expected.

Which IS a valid bug report. Bug again, not a memory leak.

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

#27

Post by Filligree »

burntsushi wrote: post #5

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/474393be8d... The issue appeared when building large Aho-Corasick automatons. Otherwise, it usually do…

What’s the reason for not always using the contiguous variant?

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

#28

Post by phkahler »

pif wrote: post #3

> 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.

>> 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.

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

#30

Post by burntsushi »

Filligree wrote: post #27
burntsushi wrote: post #5

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/474393be8d... The issue appeared when building large Aho-Corasick automatons. Otherwise, it usually do…

What’s the reason for not always using the contiguous variant?

You can't build the contiguous variant directly from a sequence of patterns. You need some kind of intermediate data structure to incrementally build a trie in memory. The contiguous NFA needs to know the complete picture of each state in order to compress it into memory. It makes decisions like, "if the number of transitions of this state is less than N, then use this representation" or "use the most significant N bits of the state pointer to indicate its representation." It is difficult to do this in an online fashion, and likely impossible to do without some sort of compromise. For example, you don't know how many transitions each state has until you've completed construction of the trie. But how do you build the trie if the state representation needs to know the number of transitions? Classic chicken-and-egg.

Note that the conversion from a non-contiguous NFA to a contiguous NFA is, relatively speaking, pretty cheap. The only real reason to not use a contiguous NFA is that it can't represent as many patterns as a non-contiguous NFA. (Because of the compression tricks it uses.)

The interesting bits start here: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

Post reply on HN