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

71–80 of 129 posts

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

#71

Post by kbknapp »

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?

Rust can re-use an allocation, but if the new item is smaller than the previous it doesn't automatically remove (free) the "wasted" memory left over from the previous allocation. I think this is categorically not a memory leak as the memory was absolutely accounted for and able to be freed (as evidenced by the `shrink_to_fit()`), but I can see how the author was initially confused by this optimization.

The 2x versus 200x confusion IMO is the OP was conflating that Vec will double in size when it needs more space, so they were assuming the memory should have only ever been 2x in the worst case of the new size. Which in the OPs case because the new type size was smaller than the previous, it seemed like a massive over-allocation.

Imagine you had a `Vec>` and to keep it simple it there were only 2 elements in both the inner and outer Vec's, which if we assume Rust doubled each Vec's allocation that'd be 4x4 "slots" of 2 bytes per slot (or 32 bytes total allocated...in reality it'd be a little different but to keep it simple let's just assume).

Now imagine you replace that allocation with a `Vec>` which even with the same doubling of the allocation size would be a maximum of 4x4 slots of 1 byte per slot (16 bytes total allocation required). Well we already have a 32 byte allocation and we only need 16, so Rust just re-uses it, and now it looks like we have 16 bytes of "waste."

Now the author was expecting at most 16 bytes (remember, 2x the new size) but was seeing 32 bytes because Rust just re-used the allocation and didn't free the "extra" 16 bytes. Further, when they ran `Vec::shrink_to_fit()` it shrunk down to only used space, which in our example would be a total of 4 bytes (2x2 of 1 byte slots actually used).

Meaning the author was comparing an observed 32 byte allocation, to an expectation of at most 16 bytes, and a properly sized allocation of 4 bytes. Factored out to their real world data I can see how they'd see numbers greater than "at most 2x."

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

#72

Post by bobbylarrybobby »

ironhaven wrote: post #54
invpt wrote: post #38

I appreciate the mention of Box . 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 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 wa…

Another rust type you should look out for is Box In my rust code I find a lot more uses of Box rather than Box . Strings are often fixed length identifiers or usernames that get passed around frequently and stored in data structures. Box can be a drop-in replacement in a surprising amount of code

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

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

#73

Post by glandium »

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's already what it does (except when shrinking)

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

#74

Post by karmakaze »

hyperpape wrote: post #56
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 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.

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

#75

Post by karmakaze »

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.

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

#76

Post by WirelessGigabit »

paulddraper wrote: post #47
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…

No, if that's all it was, the excess memory usage would be 2x. But it's 200x. Right?

Looking at this example:

    fn dbg_vec(v: &Vec) {
        println!(
            "vec data ptr={:?} len={} cap={}",
            v.as_ptr(),
            v.len(),
            v.capacity()
        );
    }
    
    fn main() {
        {
            let v1 = (0u16..128).map(|i| [i; 1024]).collect::>();
            dbg_vec(&v1);
            let v2 = v1.into_iter().map(|x| x[0] as u8).collect::>();
            dbg_vec(&v2);
        }
        {
            let v1 = (0u16..128).map(|i| [i; 1024]).collect::>();
            dbg_vec(&v1);
            let v2 = v1.into_iter().map(|x| x[0]).collect::>();
            dbg_vec(&v2);
        }
    }


    # cargo +nightly clean
         Removed 11 files, 7.3MiB total
    
    # cargo +nightly run --release
       Compiling vec-debug v0.1.0 (/home/neo/vec-debug)
        Finished release [optimized] target(s) in 0.17s
         Running `target/release/vec-debug`
    vec data ptr=0x7f47ee162010 len=128 cap=128
    vec data ptr=0x7f47ee121010 len=128 cap=262144
    vec data ptr=0x55c6514f3ba0 len=128 cap=128
    vec data ptr=0x55c6514f3ba0 len=128 cap=131072
What happens is that the original's vectors assigned space gets reused. That's it.

It LOOKS like there is more because the capacity inflates. But capacity is written in terms of sizeof(T), not bits

    (0u16..128).map(|i| [i; 1024]).collect::>()
the capacity (and length) is 128 times an array of 1024 of a u16. We then re-use the same underlying array which has a CAPACITY of 128 times (1024 * 16) and put in a u8 (the cast). So each item went from 1024 * 16 to 8.

So previously we had 128 * 1024 * 16 = 2,097,152 bits.

How many times can we put 8 bits in a capacity of 2,097,152 bits?

262,144

How many times can we put 16 bits in a capacity of 2,097,152 bits?

131,072

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

#77

Post by 0x457 »

hyperpape wrote: post #56
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 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.

No, memory leak is a very distinct definition: unused and stored, but inaccessible memory. Memory leak can be as small as a single word. In this case, it's just a memory. There is another term for this scenario, which I don't remember.

This is a case of optimization gone wrong, but nothing is leaked, and every single byte is accounted for.

The title is click bate, but article still interesting to read.

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

#78

Post by steveklabnik »

bobbylarrybobby wrote: post #72
ironhaven wrote: post #54

Earlier quoted context omitted.

Another rust type you should look out for is Box In my rust code I find a lot more uses of Box rather than Box . Strings are often fixed length identifiers or usernames that get passed around frequently and stored in data structures. Box can be a drop-in replacement in a surprising amount of code

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

Yeah, the general concept here is https://en.wikipedia.org/wiki/String_interning, Box is great for it.

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

#79

Post by cmrx64 »

invpt wrote: post #67
cmrx64 wrote: post #62

Earlier quoted context omitted.

For example, by explicitly calling shrink_to_fit. So you either have fragmentation, or an extra copy if you're not careful, but none of the solutions let you forget about the detail entirely.

If you look at the source for into_boxed_slice, it calls shrink_to_fit at the beginning before doing anything else. Hence the documentation is slightly wrong, and no copies occur. Edit: I submitted a PR to clear up the docs: https://github.com/rust-lang/rust/pull/120110

thank you!

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

#80

Post by Groxx »

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

Post reply on HN