mozilla/rust — pull request #14264 by stepancheg (2014-05-17 20:23:27+00:00)
Title: More efficient Vec::reserve strategy

Before this commit new capacity was always chosen as the next power of
two for requested capacity.

It is inefficient in scenarios where several elements are pushed to the
vector at once, and it is final operations. Example:

```
let v = Vec::new();
v.grow(10, false);
// do something with vector
```

With patch applied, new capacity is chosen as max of current capacity
doubled and requested capacity.

Before this patch resulting capacity of the vector from the example
above is 16. With patch applied, capacity is 10.

Similar strategy is used, for instance, to reserve capacity of a vector in
libc++ (1) (`vector::__recommend()`) or to reserve capacity of ArrayList
in OpenJDK (2) (`ArrayList.grow()`).

Patch also includes minor adjustment that does not affect reallocations:
capacity is compared to `self.cap`, not to `self.len` in `reserve()`.

(1) http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/vector?view=markup
(2) http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/ArrayList.java