News for hackers. Stuff that matters.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by WirelessGigabit on Thursday January 18, 2024 @11:50AM (#39044080)
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.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by vlovich123 on Thursday January 18, 2024 @01:10PM (#39045238)
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?
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by 0x457 on Thursday January 18, 2024 @01:24PM (#39045503)
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.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by vlovich123 on Thursday January 18, 2024 @02:23PM (#39046354)
Ah right. Vec of vecs and the interior Vec has wasted capacity due to the reduction of the element size. Thanks!
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by Groxx on Thursday January 18, 2024 @04:38PM (#39048140)
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 by paulddraper on Thursday January 18, 2024 @01:20PM (#39045423)
No, if that's all it was, the excess memory usage would be 2x.

But it's 200x.

Right?

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by WirelessGigabit on Thursday January 18, 2024 @04:04PM (#39047703)
Looking at this example:

    fn dbg_vec<T>(v: &Vec<T>) {
        println!(
            "vec data ptr={:?} len={} cap={}",
            v.as_ptr(),
            v.len(),
            v.capacity()
        );
    }
    
    fn main() {
        {
            let v1 = (0u16..128).map(|i| [i; 1024]).collect::<Vec<_>>();
            dbg_vec(&v1);
            let v2 = v1.into_iter().map(|x| x[0] as u8).collect::<Vec<_>>();
            dbg_vec(&v2);
        }
        {
            let v1 = (0u16..128).map(|i| [i; 1024]).collect::<Vec<_>>();
            dbg_vec(&v1);
            let v2 = v1.into_iter().map(|x| x[0]).collect::<Vec<_>>();
            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::<Vec<_>>()
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 by mplanchard on Thursday January 18, 2024 @10:01PM (#39051099)
Thank you for explaining it this way. I’ve been seeing this bit of news off and on all day and knew there was something I wasn’t understanding. This was the key bit
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by nickez on Thursday January 18, 2024 @01:25PM (#39045517)
Please read the article. His produces 200x intermediary values. Clickbait title, since it wasn't a leak.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by paulddraper on Thursday January 18, 2024 @01:35PM (#39045686)
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?

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by kbknapp on Thursday January 18, 2024 @03:30PM (#39047230)
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<Vec<u16>>` 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<Vec<u8>>` 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 by IshKebab on Thursday January 18, 2024 @05:09PM (#39048551)
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 by hyperpape on Thursday January 18, 2024 @01:40PM (#39045778)
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.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by 0x457 on Thursday January 18, 2024 @04:10PM (#39047796)
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 by karmakaze on Thursday January 18, 2024 @03:43PM (#39047417)
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 by deathanatos on Thursday January 18, 2024 @04:38PM (#39048135)
… 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 by jodrellblank on Thursday January 18, 2024 @06:52PM (#39049689)
> "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"."

By this definition, if a program reads in a file and you point it to a small file then the program does not have a memory leak, but if you point it to a large enough file, then the program does have a memory leak. Whether or not a program has a memory leak doesn't depend on the code of the program, but how you use it. But then on a bigger computer, the program doesn't have a memory leak anymore.

That seems a less useful definition than the parent poster's / the common definition.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by deathanatos on Friday January 19, 2024 @02:28AM (#39052606)
… that's really not the idea I'm trying to convey with the comment.

Clearly, if you feed a program a larger file that it is going to read into memory to process, it is then expected that it will consume more resources on account of it doing more work. But that is memory being expended on visible, useful work. All of the examples in the comment are referring to memory being "allocated" (in the sense of being assigned to the program) but not fulfilling any visibly useful function insofar as the operator/programmer can see: Java's GC being unable to effectively reclaim unused memory prior to killing a machine, the OP's example of a Vec allocating without (seemingly) have a purpose (…as it is excess of what is required to allow for amortized appends).

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by Dylan16807 on Friday January 19, 2024 @03:40PM (#39060835)
There is an implied steady state in what the program is doing. If it goes right from "loading" to "exit" then you need a more complicated analysis.

When you have that steady state, that definition looking at uncontrolled growth is more useful than trying to dissect whether the memory is truly unreachable or only practically unreachable.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by nemothekid on Thursday January 18, 2024 @10:03PM (#39051119)
>I don't care? You're just forcing me to wordsmith the problem description

Yes, because if you don't define the problem clearly, the problem won't be solved. Java being inefficient with memory use doesn't mean any memory was leaked.

Memory leaks can be tricky to track down, and if I spent 6 hours looking for a memory leak only to come back and found out you meant it uses more memory than what's efficient I'd be pissed I wasted 6 hours because you wanted to save 5 minutes.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by Dylan16807 on Friday January 19, 2024 @03:44PM (#39060874)
"uses more memory than what's efficient"

There is a hidden memory store using orders of magnitude more RAM than the live data. Why do we need to nitpick exactly how hidden it is? Are you going to be mad if I don't know whether it's literally inaccessible or not?

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by nemothekid on Friday January 19, 2024 @08:58PM (#39063905)
Because there are legitimate reasons why memory can be allocated. This is like calling your OS cache a memory leak when you open up Task Manager and see you only have 400MB free. A memory leak implies memory that is lost for good and it no longer being kept track of.

Consider it this way - if I had a program that connected to a database and used a connection pool to improve performance, would it be a "connection leak" that 5 connections were opened even though the database was idle?

The framing here is similar - Rust, in an attempt to improve performance reused large memory allocations. Some applications do this on purpose and call it buffer pools.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by Dylan16807 on Friday January 19, 2024 @09:17PM (#39064011)
Except this memory is not being intentionally used as a cache/buffer.

Rust attempts to keep the vector capacity in a range for that purpose, and failed to do so here.

No matter what, it's a bug. So none of those possible justifications fit, because it's a bug.

For the database analogy, I would call it a connection leak if the number of idle connections greatly exceeded the amount that had ever been simultaneously busy and they weren't actually getting reused.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by devmor on Thursday January 18, 2024 @02:09PM (#39046168)
I disagree that it’s a small semantic difference.

I don’t think it’s clickbait though, I think the author was just misusing terminology.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by hyperpape on Thursday January 18, 2024 @02:16PM (#39046267)
I said it was subtle, not small. I agree it's a valuable distinction.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by mratsim on Thursday January 18, 2024 @02:50PM (#39046699)
A memory leak means it leaks, it's not anymore under control. Here the memory is under control, it can be reclaimed by the program.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by thecodedmessage on Saturday January 20, 2024 @12:33AM (#39064992)
Clickbait implies a specific intent to mislead for clicks, whereas I think there’s a completely good-faith disagreement here about the meaning of the word “memory leak.”
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by karmakaze on Thursday January 18, 2024 @03:50PM (#39047497)
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 by HideousKojima on Thursday January 18, 2024 @04:40PM (#39048173)
C# doubles the size of a List<T> 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 by znkr on Thursday January 18, 2024 @04:48PM (#39048281)
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 by tialaramex on Thursday January 18, 2024 @07:22PM (#39049961)
In many of these languages (and C++) you can inadvertently pessimise by trying to provide useful size hints, Rust has a smarter API here.

Here's how that goes, suppose I receives batches of 10 Doodads. My growable array type has an API to reserve more space for Doodads, so before pushing each onto my growable array I reserve enough space for 10 extra. At small sizes this helps. Instead of 1, 2, 4, 8, 16, 32 Doodads, for two batches we grow to 10 and then 20 Doodads, we're only allocating twice and copying 10 items, instead of allocating 6 times and copying 31 items. But at bigger sizes it hurts instead, we're doing far more allocations and exponentially more copying.

Rust provides two distinct functions, Vec::reserve and Vec::reserve_exact. With reserve we get to avoid the pessimisation, it will grow faster than the exponential amortization if asked but never slower - while reserve_exact still allows us to give a specific final size in cases where we actually know that before growing too far.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by znkr on Friday January 19, 2024 @06:42AM (#39054326)
You can use slices.Grow for that purpose in Go. Exact sizing is only possible during slice creation.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by tialaramex on Friday January 19, 2024 @07:53AM (#39054867)
It's unclear which policy slices.Grow exhibits, and so maybe it's not guaranteed whether you get the equivalent of Vec::reserve or Vec::reserve_exact ? My guess since it's not mentioned and no alternative is supplied is that you get Vec::reserve_exact - the same pessimisation footgun.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by znkr on Friday January 19, 2024 @11:27AM (#39057265)
You get reserve, not reserve_exact. You are right that it would be allowed to implement reserve_exact semantics instead, given the method comment. But that’s not how it works, if you want reserve_exact semantics, you need to take extra steps. That said, the semantics are not exactly the same as reserve. The go compiler may optimize since allocations (I don’t know if it does though).
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by Thaxll on Thursday January 18, 2024 @11:31PM (#39051591)
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by karmakaze on Friday January 19, 2024 @06:04PM (#39062581)
Interesting that it considers >= 256 entries to be 'not small'. That would be accurate for larger structs, not so much if the element is a bool, int, pointer, etc.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by karmakaze on Friday January 19, 2024 @01:53PM (#39059452)
Using 1.25 creates more copies along the way than 2x.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by Dylan16807 on Friday January 19, 2024 @03:32PM (#39060731)
Sure. It's a tradeoff to avoid wasting huge amounts of memory once the list gets huge.

No matter what the growth factor, you want to set the capacity up front if you know it. But 2x and 1.25x are both reasonable.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by ongy on Thursday January 18, 2024 @11:40PM (#39051630)
In the Haskell world there's a bit of a cheap differentiation for this kind of leak.

Memory leak: classical C style, fully lost in memgrind (runtime bug) Space leak: Some memory structure requires significantly more memory than it should. E.g. keeping a (lazy) ref to a large blob, around that keeps it in memory.

The effect is largely the same, but the latter is almost harder to spot, since the tooling cannot be as general as memgrind.

Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by crotchfire on Friday January 19, 2024 @03:57AM (#39053221)
Also the latter is the bane of lazy languages, which make space leaks both commonplace and extremely difficult to notice.
Re:Identifying Rust's collect:<Vec<_>>() memory leak footgun by saagarjha on Saturday January 20, 2024 @10:05PM (#39075138)
Generally having a reference for something for longer than you should is a different kind of problem from “the vector never resizes down”.