Repository navigation
In-place iteration results in too big allocations #120091
Description
Activity
- changed the title
[-]In-place iteration does results in too big allocations[/-][+]In-place iteration results in too big allocations[/+]on Jan 18, 2024 On my machine, these reallocations do not appear to return the samme allocation, so we might as well allocate up front to avoid a memcpy.
The pointer not being the same does not necessarily mean the allocation hasn't been reused. The allocator can call
mremapto move it to a new virtual address which has a much lower cost than actually copying the bytes or faulting in new pages. This may also depend on the allocation size. For smaller pool-based allocations it might be an actual memmove and a mremap for larger ones.The behavior regarding capacities in the remaining cases needs to either change or be documented somewhere.
Well, this is a non-guaranteed optimization so we can't document the exact behavior. But it probably makes sense to mention that something like this may happen.
Additionally, in some this will cause the destination vector to have a very large capacity even for non-shared allocations. In my opinion, this should never happen.
That's intended to allow vec-allocation recycling even when the type changes, which can mean the excess factor is infinite.
Reacted by Aphek, Jiahao XU, Leandro Braga and Aurelia MolzerOn my machine this does result in a memmove. This is the strace output of an execution:
29839 mmap(NULL, 266240, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f50437bd000 29839 write(1, "vec data ptr=0x7f50437bd010 len="..., 44) = 44 29839 mmap(NULL, 266240, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f504377c000 29839 munmap(0x7f50437bd000, 266240) = 0 29839 write(1, "vec data ptr=0x7f504377c010 len="..., 47) = 47 29839 munmap(0x7f504377c000, 266240) = 0This extra capacity also has negative performance impacts:
fn test_func() { let v1 = (0u16..0x4000).map(|i| [i; 32]).collect::<Vec<_>>(); let v2 = v1.into_iter().map(|x| x[0] as u8).collect::<Vec<_>>(); // Prevent the optimizer from removing the allocation assert_eq!(v2[0], 0); } fn main() { let mut now = std::time::Instant::now(); for _ in 0..10_000 { test_func(); } println!("{}", now.elapsed().as_millis()); }
This code takes more than 10 times as long on my machine if it was compiled with the beta compiler rather than the stable one.
Reacted by Morten Lohne, Herman Skogseth, Darius Jahandarie, Richard Gura, AdrianEddy, Tony Sunny, Matthew Planchard, Juhan Oskar Hennoste, Ophir LOJKINE, Kevin Cox and 11 moreIt seems that much like capacity growth has a scaling factor there should be some sort of limit on the unused capacity that will be used for optimizations like this. Maybe there should be a general rule for
Vecsuch as "The capacity will never automatically grow more than 2x (or some other number) the maximum elements that have been part of theVecsince the last explicit capacity operation."So the manual capacity operations still work, but automatic capacity growth and allocation will not use more than some constant factor of the in-use memory.
It seems obvious to me that some rule is required here. If the next version of rust made
pushallocate a thousand times extra capacity it would "break" many programs. So there is an implicit contract here. It may make sense to make it explicit. IDK what the number we should promise is, maybe 2x or 4x. But it would be nice to write down some guarantee that can be relied on.If we have that rule spelt out then we can decide if this operation should follow the rule, or have some sort of exception. But I think it should probably follow it. (Or maybe have a slightly relaxed threshold.)
Reacted by Matt Harding, Ophir LOJKINE, Matthew House, matthieu-m, Tim Balsfulland, scottmcm, Jiahao XU, Callum Tolley, mwaitzman, Kyle J Strand and 2 moreIt seems obvious to me that some rule is required here.
Not necessarily. The capacity has already been allocated, so the cost has been paid. And vecs never shrink by themselves, even if you
popfrom them. So there's no guarantee that you always get minimal possible memory footprint.Reacted by Hai HaReacted by Kyle J Strand and Yiyuan LiuI agree that this is a bit of a weird case, but I would argue that from the user's perspective this is a "new Vec". So it is somewhat surprising that it is holding on to arbitrary amounts of memory from another vector. It would be nice to provide some guarantees.
even if you pop from them. So there's no guarantee that you always get minimal possible memory footprint.
Please not that in my rule I said "maximum elements since ...". This would allow the current behaviour of
popnot freeing memory. In other words my rule only controls growth, it never implies that theVecwill shrink other than explicit capacity operations such asshrink_to_fit.Reacted by Matt Harding, Herman Skogseth, Oscar Smith, Jonas Platte, Jiahao XU, Callum Tolley, mwaitzman and Kyle J StrandIt seems obvious to me that some rule is required here.
Not necessarily. The capacity has already been allocated, so the cost has been paid. And vecs never shrink by themselves, even if you
popfrom them. So there's no guarantee that you always get minimal possible memory footprint.The cost of an allocation is over it's entire lifetime: It's memory cannot be used by something else.
I pretty much agree with @kevincox and was about to post something similar: There should be a note in the docs for .collect<Vec<_>() that states that the resulting capacity can never be more than twice the length. (Or wherever in the docs that would cover any other similar cases)
Reacted by Kyle J Strand"surprising" is a matter of expectations. Different people have different expectations. E.g. some people have expressed surprise when collect doesn't reuse allocations.
And as I have mentioned in a previous comment using a factor-based heuristic doesn't help if you're intentionally doing something like
vec_t.filter_map(|_| None).collect::<Vec<U>>to keep the allocation. Allocation recycling has been requested before.There should be a note in the docs for .collect<Vec<_>() that states that the resulting capacity can never be more than twice the length.
Vec does not guarantee that anywhere for any operation. Quite the opposite:
Vec does not guarantee any particular growth strategy when reallocating when full, nor when reserve is called. The current strategy is basic and it may prove desirable to use a non-constant growth factor. Whatever strategy is used will of course guarantee O(1) amortized push.
Reacted by Alec Mocatta, Hai Ha, Louis Dureuil, Aphek, Jemma Nelson and 0xd34d10ccReacted by Matt Harding, Athrunen, matthieu-m, Victor Nordam Suadicani, Moritz Mœller, John Starks, Mohamed Zenadi and Yiyuan LiuReacted by Kyle J Strand and Yiyuan LiuSmall note: I think that
collect::<Vec<_>>should probably have some sort of exception forsize_hint. For example ifsize_hintsays a minimum size of 1k elements but then ends after 2 I think it is acceptable that the capacity can be 500x the actual used space. But I would document this as an exception to the general rule since this it only occurs if the implementation ofsize_hintis broken.Reacted by Matt Harding and scottmcm75 remaining items
- added a commit that references this issue
on Jan 23, 2024 It's unclear whether it would affect the thing that motivated the blog-post since that only contains simplified examples, not the original code that triggered this.
It was
(u64, u128)->(u32, u32), so requiring matching alignments would have prevented the optimization in my case.Reacted by the8472- added a commit that references this issue
on Jan 31, 2024 - added and removed
on Jan 31, 2024 This was discussed in a libs meeting but no conclusion on whether the range of possible behaviors should be narrowed was reached. We did agree that it should at least be documented (#120355) and the recent changes warrant a release note (#120004).
Additionally #120116 removes the cases in which the attempted optimization would never have been useful on stable and that also caused the regression that lead to the blog post.
After the removal there still are some additional cases in that were not optimized on previous stable releases. We're going to let those propagate to stable and wait for feedback. The assumption is that only very few crates will need to apply shrinking.Reacted by Matthew PlanchardDocumentation has been added, the case where the optimization wasn't effective has been removed and there have been no further reports so I'll close this for now.
Reacted by Demian FerreiroLeaving this here as another data point, same issue: https://www.reddit.com/r/rust/comments/1ix1i87/crazy_bug_caused_oom_in_our_streaming_engine_can/
(This bug report was inspired by this blog post https://blog.polybdenum.com/2024/01/17/identifying-the-collect-vec-memory-leak-footgun.html)
After #110353 was landed, in-place iteration can reuse allocations in many more places. While this is a good thing, in some cases this can cause overly large capacity for the destination vector.
Additionally, in some this will cause the destination vector to have a very large capacity even for non-shared allocations. In my opinion, this should never happen.
For an example see this code:
On stable this code works as expected, i.e. two different vectors with reasonably lengths and capacities.
On beta however,
v2will have a capacity of 262144, even though it does not share an allocation withv1. If you remove theas u8part, then the allocations will be shared, but the capacity is still overly large.My suggested fix is:
Meta
I am running NixOS with rustup.