In-place iteration results in too big allocations

[TethysSvensson]

(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:

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);
}

On stable this code works as expected, i.e. two different vectors with reasonably lengths and capacities.

On beta however, v2 will have a capacity of 262144, even though it does not share an allocation with v1. If you remove the as u8 part, then the allocations will be shared, but the capacity is still overly large.

My suggested fix is:

• Do not attempt to use in-place collection if the destination alignments do not match, as reallocation will always be necessary. 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 behavior regarding capacities in the remaining cases needs to either change or be documented somewhere.

Meta

I am running NixOS with rustup.

$ rustup --version --verbose
rustup 1.26.0 (1980-01-01)
info: This is the version for the rustup toolchain manager, not the rustc compiler.
info: The currently active `rustc` version is `rustc 1.77.0-nightly (6ae4cfbbb 2024-01-17)`
$ rustc +stable --version --verbose
rustc 1.75.0 (82e1608df 2023-12-21)
binary: rustc
commit-hash: 82e1608dfa6e0b5569232559e3d385fea5a93112
commit-date: 2023-12-21
host: x86_64-unknown-linux-gnu
release: 1.75.0
LLVM version: 17.0.6
$ rustc +beta --version --verbose
rustc 1.76.0-beta.5 (f732c37b4 2024-01-12)
binary: rustc
commit-hash: f732c37b4175158d3af9e2e156142ffb0bff8969
commit-date: 2024-01-12
host: x86_64-unknown-linux-gnu
release: 1.76.0-beta.5
LLVM version: 17.0.6

[the8472]

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 mremap to 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.

[TethysSvensson]

On 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)    = 0

[TethysSvensson]

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

[kevincox]

It 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 Vec such as "The capacity will never automatically grow more than 2x (or some other number) the maximum elements that have been part of the Vec since 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 push allocate 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.)

[the8472]

It 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 pop from them. So there's no guarantee that you always get minimal possible memory footprint.

[kevincox]

I 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 pop not freeing memory. In other words my rule only controls growth, it never implies that the Vec will shrink other than explicit capacity operations such as shrink_to_fit.

[majaha]

It 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 pop from 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)

[the8472]

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

[kevincox]

Small note: I think that collect::<Vec<_>> should probably have some sort of exception for size_hint. For example if size_hint says 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 of size_hint is broken.