From f4b9dc31f68ff5b3dd19a22c4a3e3eefeaa0611a Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Mon, 18 May 2020 05:28:14 +1000 Subject: Tiny Vecs are dumb. Currently, if you repeatedly push to an empty vector, the capacity growth sequence is 0, 1, 2, 4, 8, 16, etc. This commit changes the relevant code (the "amortized" growth strategy) to skip 1 and 2 in most cases, instead using 0, 4, 8, 16, etc. (You can still get a capacity of 1 or 2 using the "exact" growth strategy, e.g. via `reserve_exact()`.) This idea (along with the phrase "tiny Vecs are dumb") comes from the "doubling" growth strategy that was removed from `RawVec` in #72013. That strategy was barely ever used -- only when a `VecDeque` was grown, oddly enough -- which is why it was removed in #72013. (Fun fact: until just a few days ago, I thought the "doubling" strategy was used for repeated push case. In other words, this commit makes `Vec`s behave the way I always thought they behaved.) This change reduces the number of allocations done by rustc itself by 10% or more. It speeds up rustc, and will also speed up any other Rust program that uses `Vec`s a lot. --- src/liballoc/raw_vec/tests.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/liballoc/raw_vec') diff --git a/src/liballoc/raw_vec/tests.rs b/src/liballoc/raw_vec/tests.rs index e7ab8a305d2..17622d72a05 100644 --- a/src/liballoc/raw_vec/tests.rs +++ b/src/liballoc/raw_vec/tests.rs @@ -59,7 +59,7 @@ fn reserve_does_not_overallocate() { let mut v: RawVec = RawVec::new(); v.reserve(0, 7); assert_eq!(7, v.capacity()); - // 97 if more than double of 7, so `reserve` should work + // 97 is more than double of 7, so `reserve` should work // like `reserve_exact`. v.reserve(7, 90); assert_eq!(97, v.capacity()); -- cgit 1.4.1-3-g733a5