`Vec::reserve()` amortization guarantees in loops

internals
1

Hi, please let me know if this question is better suited for https://users.rust-lang.org/. If so, I'll move it there.

Generally, in many programming languages, calling collection.reserve_exact(additional) from within a loop might lead to a quadratic blowup of execution time:

let mut vec = Vec::new();
let N = 1000000;

for i in 0..N {
    // the following line takes O(i) time per iteration,
    // thus O(N**2) time in total over all iterations
    vec.reserve_exact(2);

    vec.push(2 * i);
    vec.push(2 * i + 1);
}

One way of avoiding this problem is to not call collection.reserve_exact(additional) in the loop's body.

However, the less error-prone solution is to implement collection.reserve(additional) so that it uses allocation sizes in exponential steps: if reserve_exact(additional) would allocate space for exactly M elements in total, then reserve(additional) allocates space for 2**K in total, where 2**K >= M with integer K. This ensures that even if user calls collection.reserve(additional) in a loop, they still get the amortized O(N) over all iterations.

My question is: does Vec::reserve()/HashMap::reserve() (and reserve() in other similar structures) guarantee that calling reserve() in a loop doesn't lead to, and will never lead to, a quadratic blowup of execution time?

The documentation for both those methods (Vec::reserve(), HashMap::reserve()) says:

The collection may reserve more space to speculatively avoid frequent reallocations.

However, in the context of my scenario above, this phrasing is ambiguous enough to put in doubt whether the current implementation uses (and the future implementations will use) the exponential stepping for allocations.

Another hint for the behavior of those methods can be found at 0235-collections-conventions - The Rust RFC Book

(...) The reserve function may grow the capacity by a larger amount than requested, to ensure amortization, while reserve_exact will reserve exactly the requested additional capacity. (...)

Again, the phrasing is not explicit enough to answer my question.

Lastly, AFAICT from looking at the source code, the current implementation does actually use the exponential allocation solution (e.g. here).

So, is there any such guarantee for the current and/or future implementations of reserve()? If so, I suggest adding this to the documentation (or clarifying in the current phrasing). If not, I propose that such guarantee is added to the relevant collections in std.

2

The docs say:

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.

10 Likes