vec.reserve() unintuitive behavior

[ghost]

There are three issues I see with vec.reserve()

Issue 1: The results can be vastly different for minimally different input vectors. For example this code:

fn main() {
    let mut x = vec![0i8; 1023];
    x.reserve(1);
    let mut y = vec![0i8; 1024];
    y.reserve(1);
    println!("x capacity = {}, y capacity = {}", x.capacity(), y.capacity());
}

prints "x capacity = 1024, y capacity = 2048". The inputs to such a function are very similar, so we should expect reserve() to behave similarly on them, but we see that reserve() assigns special significance to powers of 2 for no reason.

Suggested fix: if we need to increase capacity past the current capacity, simply double the current capacity. So above, our result would be: "x capacity = 2046, y capacity = 2048".

---

Issue 2: How exactly the vector decides to expand can have huge performance considerations. See for example https://github.com/rust-lang/rust/blob/master/src/libcollections/vec.rs#L536. Also see for example the thread at #23820 (comment). All the API guarantees is that the vector will accommodate at least the size requested. However, in both of these situations, it is critical for performance reasons that the algorithm generally give you more for you ask for, and in the pull request I referenced, if you don't have the doubling behavior, you go from O(n) to O(n^2). It seems like such an important performance consideration should not be hidden in the implementation.

Recommendation: Document in the API that, if reserve() needs to allocate memory less than double its current capacity, it will double its current capacity.

---

Issue 3: The difference between reserve() and reserve_exact() seem confusing, mostly due to the name of the former. I'm sure there will be plenty of examples that crop up as well of people using reserve() where they meant to use reserve_exact(), or using reserve() and reasoning that it behaves like reserve_exact() (the pull request shows an example of this).

Recommendation: Change the name of reserve() to something more specific, so that people don't get confused and use reserve() where they mean to use reserve_exact(). Something like reserve_round_up().

---

I'm currently testing a commit that fixes a few issues in vec.rs (involving expansion behavior near usize::MAX). I can start working on fixing issues 1 and 2 now, though it seems like a large-ish API change like issue 3 (and maybe 2) would require an RFC. Let me know if there's enough interest to be worth submitting.

[emberian]

cc @gankro, @aturon

[ghost]

Also see #23847 which clears up some of the confusion from #23820, but would still benefit from the changes discussed here.

[Gankra]

Suggested fix: if we need to increase capacity past the current capacity, simply double the current capacity. So above, our result would be: "x capacity = 2046, y capacity = 2048".

Seems reasonable; note that this is subtler for HashMap and VecDeque because they require that capacity be a power-of-two implementation-wise.

Recommendation: Document in the API that, if reserve() needs to allocate memory less than double its current capacity, it will double its current capacity.

Amortization only requires that it grows by a constant factor; I see little value in specifying doubling (indeed there are many that argue that >= 2 is awful because repeated grows can't re-use any space (2^k >= [sum i=0 to k-1 of 2^i]). If you need tighter control of reservation use reserve_exact. If you just need amortization over many ops, don't even bother reserving, the collection will do appropriate amortization for you.

In general we've been very careful not to overspecify these APIs. Note that the general API is especially fuzzy because of HashMap, which you can't efficiently compute capacity for due to impl details. Also it may be desirable for a HashMap to reallocate if a long collision chain occurs. I'm not fundamentally opposed to tightening up the specific guarantees Vec offers, but I'd like to tread carefully here.

Recommendation: Change the name of reserve() to something more specific, so that people don't get confused and use reserve() where they mean to use reserve_exact(). Something like reserve_round_up().

Eh. We used to have the names reserve (now reserve_exact) and reserve_additional (now reserve). In practice this seemed backwards since empirically reserve_additional was what people wanted (I have some buffer and am anticipating k more items, do at most one reallocation for inserting this). Also it's not like it's a huge semantics foot-gun. At worst using reserve inappropriately wastes some space, right?

[ghost]

Seems reasonable; note that this is subtler for HashMap and VecDeque because they require that capacity be a power-of-two implementation-wise.

Shouldn't be too bad, as long as it starts with a power of two it will remain a power of two. I can take a look at it.

Amortization only requires that it grows by a constant factor I see little value in specifying doubling

I agree. So I think it should note in the API that it will grow by an implementation-defined constant factor.

As of right now even that isn't in the API, and theoretically the algorithm could change to something like allocating twice as much space as you ask for, or allocating exactly as much as you ask for, which would hurt run time complexities of functions which use reserve() (eg read_to_end referenced above).

Also it's not like it's a huge semantics foot-gun. At worst using reserve inappropriately wastes some space, right?

I'm not sure if this is the proper approach to this. It should be up to the user to decide what problems/inefficiencies are tolerable, not the library writers. Considering this is something of a systems language I'd imagine there are plenty of use cases where accidentally allocating twice as much memory as you meant to could be a very bad thing.

Given the ambiguous name of reserve() this is an error that's sure to happen repeatedly. Having eg reserve_round_up and reserve_exact, and no function just called reserve, removes the ambiguity entirely and basically removes that whole class of errors. Additionally, there seems to be a large upside and little to no downside to changing the names. We could just mark reserve() as deprecated and have reserve_round_up perform the same job.

[sfackler]

C++'s vector::reserve appears to be basically identical to Vec::reserve as it currently exists.

[Gankra]

They are different, though. vector::reserve is absolute while Vec::reserve is relative to current len.

[ghost]

I think C++ reserve behaves like reserve_exact in Rust. Note that reserve_exact doesn't guarantee you exactly the sized buffer you asked for either, it guarantees one at least that large. reserve_exact and C++ reserve, however, don't try to actively request a lot more bytes than you need the way Rust reserve does AFAIK.

[bluss]

I don't see why Issue 1 is a problem or needs a change. I'm sure the documentation will tell you the vector grows using that algorithm. Later we have said we would explore growth factors below 2.0.

[ghost]

I don't see why Issue 1 is a problem or needs a change.

Check out https://github.com/rust-lang/rust/blob/master/src/libcollections/vec.rs#L538

Let's say we have a vector with length and capacity 1023, and call insert twice. Right now it will do two full reallocs, the first of which is basically useless and only gives you one additional element in space. If you did the doubling algorithm (or multiplying by any constant factor) instead of rounding up to powers of 2, this would only need one realloc.

I'm sure the documentation will tell you the vector grows using that algorithm.

All the documentation says is:

Reserves capacity for at least additional more elements to be inserted in the given Vec. The collection may reserve more space to avoid frequent reallocations.

This doesn't even guarantee amortization (or anything really) which is why I suggest the API/documention specifies that if the reserve requires less than double (or any constant factor) times its current capacity, it will increase it's capacity by multiplying it by that constant factor.

[bluss]

Let's say we have a vector with length and capacity 1023, and call insert twice.

This will only occur if exactly 1023 was requested with with_capacity() (or from vec![], I admit). During regular growth without user requests for sizing, it would already have capacity 1024 at that point.

[ghost]

It could happen other ways. One or several calls to reserve_exact is another way.

It could happen through push() as well, since push has doubling behavior. Ie, if you start with 19 elements, and push enough elements such that it doubles twice, you end up with (19^2)^2 = 130321 elements. If you call reserve(1) on that when it's full, it will increase to 2^17 = 131072 elements, which is a whole lot of copying for only gaining 751 elements of additional space.

[bluss]

That is clearly broken if push and insert don't agree on growth strategy. I'm sorry.

[steveklabnik]

Removing A-docs for now, as there's clearly some discussion that needs to happen before I document whatever is decided.

[Gankra]

@steveklabnik I'll happily handle the documentation on this once a concensus is reached. Note that there's no real back-compat hazard here vis-a-vis failing to make a decision. This is a pure performance issue and the docs clearly leave it as implementation defined behaviour. (not sure what I-needs-decision is intended to imply)

[steveklabnik]

(not sure what I-needs-decision is intended to imply)

Historically we've used it over the last few weeks as a 'we need to make some sort of call here,' so to not clog up the triage meeting. So feels about right: there's some quibble as to what's expected, and some decision needs to be made.