6 ms·

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

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.

vlovich123 3y ago
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?
- 0x457 3y ago
  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.
  - vlovich123 3y ago
    Ah right. Vec of vecs and the interior Vec has wasted capacity due to the reduction of the element size. Thanks!
- Groxx 3y ago
  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.
deleted 3y ago
[deleted]
paulddraper 3y ago
No, if that's all it was, the excess memory usage would be 2x. But it's 200x. Right?
- nickez 3y ago
  Please read the article. His produces 200x intermediary values. Clickbait title, since it wasn't a leak.
  - paulddraper 3y ago
    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?
    - kbknapp 3y ago
      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."
karmakaze 3y ago
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.
- HideousKojima 3y ago
  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?
  - znkr 3y ago
    It grows by 2x for small sizes, then it transitions to growing it by 1.25x
    - karmakaze 3y ago
      Using 1.25 creates more copies along the way than 2x.
      - Dylan16807 3y ago
        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.
    - tialaramex 3y ago
      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.
ongy 3y ago
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.
- crotchfire 3y ago
  Also the latter is the bane of lazy languages, which make space leaks both commonplace and extremely difficult to notice.
- saagarjha 3y ago
  Generally having a reference for something for longer than you should is a different kind of problem from “the vector never resizes down”.

vlovich123 3y ago

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?

0x457 3y ago
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.
- vlovich123 3y ago
  Ah right. Vec of vecs and the interior Vec has wasted capacity due to the reduction of the element size. Thanks!
Groxx 3y ago
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.

deleted 3y ago

[deleted]

paulddraper 3y ago

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

nickez 3y ago
Please read the article. His produces 200x intermediary values. Clickbait title, since it wasn't a leak.
- paulddraper 3y ago
  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?
  - kbknapp 3y ago
    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."

karmakaze 3y ago

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.

HideousKojima 3y ago
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?
- znkr 3y ago
  It grows by 2x for small sizes, then it transitions to growing it by 1.25x
  - karmakaze 3y ago
    Using 1.25 creates more copies along the way than 2x.
    - Dylan16807 3y ago
      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.
  - tialaramex 3y ago
    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.

ongy 3y ago

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.

crotchfire 3y ago
Also the latter is the bane of lazy languages, which make space leaks both commonplace and extremely difficult to notice.
saagarjha 3y ago
Generally having a reference for something for longer than you should is a different kind of problem from “the vector never resizes down”.