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.
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.
But it's 200x.
Right?
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
> 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?
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."
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.
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.
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.
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...
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.
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).
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.
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.
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?
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.
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.
I don’t think it’s clickbait though, I think the author was just misusing terminology.
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.
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.
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.
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.