《关于golang切片扩容基准选择1024而v1.18之后公式发生改变了这件事》

原标题：为什么Golang切片扩容基准是1024 以及 为什么v1.18之后改变了扩容公式，发现标题太长可以改成轻小说

在阅读了Go 语言设计与实现的3.2 切片实现原理之后，了解到切片的扩容机制和扩容公式，但是不明白为什么要选择这个公式，所以查找了资料并做下总结。

1. 切片扩容公式

在gov1.18之前切片扩容代码如下（以1.17为例，runtime.growslice）：

// gov1.17 runtime/slice.go

func growslice(et *_type, old slice, cap int) slice {
	...
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		if old.cap < 1024 {
			newcap = doublecap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
	...
}

可将上述代码段总结为以下公式，假设新容量为N，原容量为OC, 期望容量为C：

$N=\begin{cases}C & C \ge 2\times OC \\ 2\times OC & OC \lt 1024 \\ OC\times 1.25^n & OC \ge 1024, OC \times1.25^{n-1} \lt C \le OC \times 1.25^n \end{cases}$

这里以 1024 作为扩容公式的基准（pivot），扩容公式发生改变。

2. 为什么是 1024

没有为什么，总得选个数字吧。

因为 1024 是个不错的数字，比大部分切片的长度都要大。

我在 golang-nuts 找到了讨论 slices grow at 25% after 1024 but why 1024?，以下是Rob Pike（Google的工程师，参与编程语言Go与Sawzall的研发工作）的回答：

What would you pick? You need to pick something.

It was just arbitrary, I'm sure. 1024 is a nice number, and it's larger than the length of many slices.

Sometimes a number is just a number.

3. v1.18 之后的扩容公式

在gov1.18之后，公式发生了改变runtime.growSlice：

func growslice(et *_type, old slice, cap int) slice {
	...
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		const threshold = 256
		if old.cap < threshold {
			newcap = doublecap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
				// Transition from growing 2x for small slices
				// to growing 1.25x for large slices. This formula
				// gives a smooth-ish transition between the two.
				newcap += (newcap + 3*threshold) / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
	...
}

此处变为了 256，并且大于等于 256 时，公式发生了改变。

每次增加量为 $(\text{新容量}+3\times \text{阈值})\times \frac{1}{4}$，直到大于或等于期望容量。

4. 为什么是这个公式

根据347917: runtime: make slice growth formula a bit smoother | https://go-review.googlesource.com/c/go/+/347917 的描述：

use a somewhat smoother formula for the growth factor. Start reducing
the growth factor after 256 elements, but slowly.

starting cap    growth factor
	256             2.0
	512             1.63
	1024            1.44
	2048            1.35
	4096            1.30

此公式会让切片容量的增长更加的平滑(Smoother)。

如下是提供的图表：

增长因子变化曲线

image-20230925044008056

进行内存对齐(roundupsize)之后的曲线

image-20230925044135744

Reference

1. https://groups.google.com/g/golang-nuts/c/UaVlMQ8Nz3o
2. https://go-review.googlesource.com/c/go/+/347917?tab=comments
3. https://docs.google.com/document/d/1JQvV6vyAYdHhIboY-zAwK06OXZjxHrUhOFeG38MuJ94/edit?resourcekey=0-L5OsHqwZZBxvjfK0dwsyVQ#heading=h.k26k09874o5u
4. https://archive.li/Z2R8w
5. https://go.googlesource.com/go/+/2dda92ff6f9f07eeb110ecbf0fc2d7a0ddd27f9d
6. https://wtf.hiigara.net/t/aaRKuc/golang