From f4b9dc31f68ff5b3dd19a22c4a3e3eefeaa0611a Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Mon, 18 May 2020 05:28:14 +1000 Subject: [PATCH] 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.rs | 29 +++++++-- src/liballoc/raw_vec/tests.rs | 2 +- src/liballoc/tests/vec.rs | 115 ++++++++++++++++++++++++++++++++++ 3 files changed, 141 insertions(+), 5 deletions(-) diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs index d46bf81f996..f348b5b6978 100644 --- a/src/liballoc/raw_vec.rs +++ b/src/liballoc/raw_vec.rs @@ -407,13 +407,34 @@ fn grow_amortized( return Err(CapacityOverflow); } + if needed_extra_capacity == 0 { + return Ok(()); + } + // Nothing we can really do about these checks, sadly. let required_cap = used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; - // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`. - let double_cap = self.cap * 2; - // `double_cap` guarantees exponential growth. - let cap = cmp::max(double_cap, required_cap); + + // This guarantees exponential growth. The doubling cannot overflow + // because `cap <= isize::MAX` and the type of `cap` is `usize`. + let cap = cmp::max(self.cap * 2, required_cap); + + // Tiny Vecs are dumb. Skip to: + // - 8 if the element size is 1, because any heap allocators is likely + // to round up a request of less than 8 bytes to at least 8 bytes. + // - 4 if elements are moderate-sized (<= 1 KiB). + // - 1 otherwise, to avoid wasting too much space for very short Vecs. + // Note that `min_non_zero_cap` is computed statically. + let elem_size = mem::size_of::(); + let min_non_zero_cap = if elem_size == 1 { + 8 + } else if elem_size <= 1024 { + 4 + } else { + 1 + }; + let cap = cmp::max(min_non_zero_cap, cap); + let new_layout = Layout::array::(cap); // `finish_grow` is non-generic over `T`. 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()); diff --git a/src/liballoc/tests/vec.rs b/src/liballoc/tests/vec.rs index 3d76324f7e8..b16044d9640 100644 --- a/src/liballoc/tests/vec.rs +++ b/src/liballoc/tests/vec.rs @@ -1473,3 +1473,118 @@ struct DynRepr { vtable: *mut (), } } + +// This test will likely fail if you change the capacities used in +// `RawVec::grow_amortized`. +#[test] +fn test_push_growth_strategy() { + // If the element size is 1, we jump from 0 to 8, then double. + { + let mut v1: Vec = vec![]; + assert_eq!(v1.capacity(), 0); + + for _ in 0..8 { + v1.push(0); + assert_eq!(v1.capacity(), 8); + } + + for _ in 8..16 { + v1.push(0); + assert_eq!(v1.capacity(), 16); + } + + for _ in 16..32 { + v1.push(0); + assert_eq!(v1.capacity(), 32); + } + + for _ in 32..64 { + v1.push(0); + assert_eq!(v1.capacity(), 64); + } + } + + // If the element size is 2..=1024, we jump from 0 to 4, then double. + { + let mut v2: Vec = vec![]; + let mut v1024: Vec<[u8; 1024]> = vec![]; + assert_eq!(v2.capacity(), 0); + assert_eq!(v1024.capacity(), 0); + + for _ in 0..4 { + v2.push(0); + v1024.push([0; 1024]); + assert_eq!(v2.capacity(), 4); + assert_eq!(v1024.capacity(), 4); + } + + for _ in 4..8 { + v2.push(0); + v1024.push([0; 1024]); + assert_eq!(v2.capacity(), 8); + assert_eq!(v1024.capacity(), 8); + } + + for _ in 8..16 { + v2.push(0); + v1024.push([0; 1024]); + assert_eq!(v2.capacity(), 16); + assert_eq!(v1024.capacity(), 16); + } + + for _ in 16..32 { + v2.push(0); + v1024.push([0; 1024]); + assert_eq!(v2.capacity(), 32); + assert_eq!(v1024.capacity(), 32); + } + + for _ in 32..64 { + v2.push(0); + v1024.push([0; 1024]); + assert_eq!(v2.capacity(), 64); + assert_eq!(v1024.capacity(), 64); + } + } + + // If the element size is > 1024, we jump from 0 to 1, then double. + { + let mut v1025: Vec<[u8; 1025]> = vec![]; + assert_eq!(v1025.capacity(), 0); + + for _ in 0..1 { + v1025.push([0; 1025]); + assert_eq!(v1025.capacity(), 1); + } + + for _ in 1..2 { + v1025.push([0; 1025]); + assert_eq!(v1025.capacity(), 2); + } + + for _ in 2..4 { + v1025.push([0; 1025]); + assert_eq!(v1025.capacity(), 4); + } + + for _ in 4..8 { + v1025.push([0; 1025]); + assert_eq!(v1025.capacity(), 8); + } + + for _ in 8..16 { + v1025.push([0; 1025]); + assert_eq!(v1025.capacity(), 16); + } + + for _ in 16..32 { + v1025.push([0; 1025]); + assert_eq!(v1025.capacity(), 32); + } + + for _ in 32..64 { + v1025.push([0; 1025]); + assert_eq!(v1025.capacity(), 64); + } + } +} -- 2.44.0