RawVec growth strategy can be more efficient

[handsomefox]

Currently, the RawVec implementation tries to double its internal capacity every time it has to grow, as can be seen in:

rust/library/alloc/src/raw_vec.rs

Line 398 in 31a4f2d

let cap = cmp::max(self.cap * 2, required_cap);

But, according to Facebook's FBVector memory handling: it is suboptimal, as "it can be mathematically proven that a growth factor of 2 is rigorously the worst possible because it never allows the vector to reuse any of its previously-allocated memory" because "any new chunk requested will be larger than all previously used chunks combined, so the vector must crawl forward in memory; it can't move back to its deallocated chunks. But any number smaller than 2 guarantees that you'll at some point be able to reuse the previous chunks."

They use a growth factor of 1.5.

Maybe it is worth considering changing the growth factor for the standard library to a theoretically more optimal value.

[workingjubilee]

In practice, changes like this have been attempted, and yielded nontrivial perf regressions in the compiler:

• Try 1.5x as a vec growth factor #108718
• Grow RawVec to fill the allocator bins tighter [please bench it] #101341

As there is certainly not a shortage of Vecs in the compiler, it's reasonable to believe that this may not be a worthwhile improvement, as it trades off a potentially significant amount of runtime. However if someone can provide evidence otherwise, e.g. that the compiler is somehow distinct from every other common user of Vec, or if there is some conjoined changeset that makes this into an actual improvement, this remains open to change.

Obviously there is some reason to believe that the space efficiency is improved. However, it is enormously common for Vec to be used for small amounts, such that SmallVec is a significant optimization. We avoid the claim FB makes (that size is never reused) partly by simply allocating a nonzero capacity if the programmer hasn't requested a more specific size and is doing a first-time push:

rust/library/alloc/src/raw_vec.rs

Lines 104 to 116 in a77c552

	impl<T, A: Allocator> RawVec<T, A> {
	// 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.
	pub(crate) const MIN_NON_ZERO_CAP: usize = if mem::size_of::<T>() == 1 {
	8
	} else if mem::size_of::<T>() <= 1024 {
	4
	} else {
	1
	};

Notably, there are two possible biases here: the compiler is a batch-processing program, so its performance relies heavily on quickly allocating a lot of memory, so time efficiency matters. Facebook has a number of different programs they are interested in, but a fairly notable one for their C++ code (especially the many years ago that was written...) is a nontrivial server architecture, where data structures can be incredibly long-lived, thus space efficiency matters. Many programs instead live between these two.

I am closing this, but only because it is a duplicate of #29931