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

81–90 of 129 posts

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

#81

Post by akira2501 »

paulddraper wrote: post #50
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: international standards do. What if...stick with me...the standards sought to codify and respect programmers' expectations? https://en.wikipedia.org/wiki/Principle_of_least_astonishmen...

Then using a language without a published standard is a fools errand.

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

#82

Post by deathanatos »

karmakaze wrote: post #74
hyperpape wrote: post #56

Earlier quoted context omitted.

I agree that this is not a memory leak. However, the semantic distinction between "this uses much more memory than expected" and "this is a memory leak" is a little subtle, and it seems pretty rude to call it clickbait.

Clickbait (in the context of Rust). In languages with managed memory there are no true memory leaks so such wastes are called leaks. In lower-level languages, we should stay more strict with what we call things.

… Box::leak¹ is a function that exists. That seems like a memory leak, no?

Less tongue-in-cheek, if a program allocates far more memory than expected of it, I going to colloquially called that a "memory leak". If I see a Java program whose RSS is doing nothing but "up and to the right" until the VM runs out of memory and dies a sweet sweet page thrashing death, I'm going to describe that as a "memory leak". Having someone tell me, "well, actually, it's not a leak per se it's just that the JVM's GC didn't collect all the available garbage prior to running out of memory because …" … I don't care? You're just forcing me to wordsmith the problem description —-the problem is still there. Program is still dead, and still exceeding the constraints of the environment it should have been operating in.

The author had some assumptions: that Vec doesn't overalloc by more than 2x, and that collect allocates — one of those did turn out to be false, but I think if I polled Rust programmers, a fair number of them would make the wrong assumption. I would, and TIL from this article that it was wrong, and that collect can reuse the original allocation, despite it not being readily apparent how it knows how to do that with a generic Iterator. (And, the article got me to understand that part, too!)

Unlike most clickbaits which lure you in only to let you down, I learned something here. Reading it was worthwhile.

¹https://doc.rust-lang.org/stable/std/boxed/struct.Box.html#m...

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

#83

Post by Groxx »

vlovich123 wrote: post #44
WirelessGigabit wrote: post #26

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

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?

The `map` step converted the data to a smaller type, and the whole chain was smart enough to reuse the original Vec without reallocating. Since the original item size was [much bigger], there was a lot of "free" capacity left over.

It is indeed a bit surprising, but seems entirely reasonable for the platform to do imo. It's efficient, in both memory (allocation) and CPU. If you want a specifically-sized container, you have to make sure that happens, otherwise you're letting things be optimized in language-general ways. That will frequently be wrong in edge cases, and may change at any time.

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

#84

Post by HideousKojima »

karmakaze wrote: post #75
WirelessGigabit wrote: post #26

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

A similar thing happens in Go if you don't use a pre-known 'capacity' when allocating slices. Each internal realloc could use a larger backing array. Adding elements 1 by 1 will keep doing this making lots of garbage. They all get collected of course, but performance is horrible with memory fragmentation and all the copying.

C# doubles the size of a List each time you hit the capacity (if you didn't set it correctly when you created the list or left it at the default). Does Go do something similar or does it only increase it by 1 each time?

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

#85

Post by deathanatos »

Groxx wrote: post #80

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

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.

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

#86

Post by znkr »

HideousKojima wrote: post #84
karmakaze wrote: post #75

Earlier quoted context omitted.

A similar thing happens in Go if you don't use a pre-known 'capacity' when allocating slices. Each internal realloc could use a larger backing array. Adding elements 1 by 1 will keep doing this making lots of garbage. They all get collected of course, but performance is horrible with memory fragmentation and all the copying.

C# doubles the size of a List each time you hit the capacity (if you didn't set it correctly when you created the list or left it at the default). Does Go do something similar or does it only increase it by 1 each time?

It grows by 2x for small sizes, then it transitions to growing it by 1.25x

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

#87

Post by Groxx »

loeg wrote: post #43

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 bu…

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)

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

#88

Post by IshKebab »

tialaramex wrote: post #32
the_mitsuhiko wrote: post #15

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

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.

Yeah I feel like it should reallocate if the size difference is great.

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

#89

Post by IshKebab »

paulddraper wrote: post #55
nickez wrote: post #53

Earlier quoted context omitted.

Please read the article. His produces 200x intermediary values. Clickbait title, since it wasn't a leak.

I did read the article. > the memory waste from excess capacity should always be at most 2x, but I was seeing over 200x. So the 200x analysis is his problem?

200x is correct. What's happening is that he makes a vector with tons of capacity and only a few elements, so lots of wasted space. Then he turns that vector into another vector using an operation that used to allocate a new vector (thus releasing the wasted space) but now reuses the previous vector's allocation (retaining the wasted space).

It's definitely a sneaky bug. Not a "memory leak" in the normal sense since the memory will still be freed eventually. I'd call it an unexpected waste of memory.

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

#90

Post by TwentyPosts »

akira2501 wrote: post #81
paulddraper wrote: post #50

Earlier quoted context omitted.

> Programmers’ expectations are not codified and do not need to be respected: international standards do. What if...stick with me...the standards sought to codify and respect programmers' expectations? https://en.wikipedia.org/wiki/Principle_of_least_astonishmen...

Then using a language without a published standard is a fools errand.

No? How does that even follow? That a standard should codify common expectations insofar possible (without breaking rigor) is irrelevant to whether you "should" only use standardized languages or not.
Post reply on HN