经典面试题：Go 切片扩容策略
引言
最近在刷面试题的过程中，因为本地Go使用的是1.20版本，而网上关于 Go slice扩容策略的描述还大多停留在 2021年前的版本，也就是Go1.17版本和之前的所有版本，遂分享出来。
如果你使用的Go版本大于等于Go1.18，可要千万注意啦。
< Go1.17：
- 新容量计算
- 如果期望大小超过现有容量2倍，则直接使用期望容量
- 如果容量小于1024（
Go1.18后是256），2倍扩容，否则1.25倍扩容（Go1.18后由表达式计算）
- 最终容量计算：为了避免内存碎片，最后会进行
内存对齐计算，所以最后的结果会大于等于上面计算的值。
> Go1.18：
- 2倍扩容的条件由小于1024调整为
小于256 - 1.25倍的固定扩容比，
改成了根据增长因子(growth factor)扩容，而这个增长因子会随着切片容量越大而逐渐变小，直到无限趋近于1.25，相比从2倍直接过渡到1.25倍，增长因子的引入（2.0 -> 1.63 -> 1.44 -> 1.35 -> 1.30 -> ...）让扩容更加平滑。 - 内存对齐计算规则保持不变
so，如果面试被问到，回答了这个细节，应该会加分吧？
下面，让我们通过源码来比较一下。
什么时候会触发扩容
切片扩容发生在调用 append() 时，如果切片的底层数组长度已经不足以容纳新添加的元素时，就会触发扩容，此时go编译器会调用 growslice() 确定新的容量大小，然后拷贝老的元素到新的底层数组。
源码在哪里
- src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
// ...
}
growslice() 是使用append()添加元素时对应的底层函数调用。
源码对比
Go1.17和之前的版本：
// go.17 src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap { // 大于目前容量的2倍，直接使用期望容量
newcap = cap
} else {
// 小于1024，2倍扩容（Go1.18开始改成了256）
if old.cap < 1024 {
newcap = doublecap
} else {
for 0 < newcap && newcap < cap {
// 否则，固定1.24倍（Go1.18开始，这里改成了线性下降，最终接近于1.25倍扩容）
newcap += newcap / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
// … 内存对齐计算、数据拷贝等逻辑
}
Go1.18和后续版本（最新的Go1.20保持一致）：
// go1.18 src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
// ...
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
const threshold = 256 // 注意这里，由1024改成了256
if old.cap < threshold {
newcap = doublecap
} else {
for 0 < newcap && newcap < cap {
// 这里由固定 1.25 倍扩容改成了表达式计算
// 作用是让扩容更加平滑：2倍 -> 1.63倍 -> 1.44倍 -> 1.35倍 -> ... -> 1.25倍
// 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
}
if newcap <= 0 {
newcap = cap
}
}
}
//...后续代码(内存对齐等)没有变动
}
增长因子(growth factor)示例
所谓的增长因子其实就是一个计算公式：
newcap += (newcap + 3*threshold) / 4
如果看不懂，Keith Randall 大神在2021年9月的提交中给出了一个增长因子的示例（runtime: make slice growth formula a bit smoother）：
runtime: make slice growth formula a bit smoother
Instead of growing 2x for < 1024 elements and 1.25x for >= 1024 elements,
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
通过这个示例，我们只要明白大切片（超过256）扩容时，不再是固定 1.25 倍，而是平滑下降即可。
分析公式，当 newcap无限大时，作为分子的 3threshold（3256）因为是固定值，故可以忽略不计，所以增长因子会无限趋近于 1.25倍大小。
为什么要这么优化？
Keith Randall 大神在提交时，给出了一个讨论的链接，其中提到了一些老版本算法的一些问题。
当前算法不是单调递增
Go1.17：
x1 := make([]int, 897)
x2 := make([]int, 1024)
y := make([]int, 100)
println(cap(append(x1, y...))) // 2048
println(cap(append(x2, y...))) // 1280
在上面的代码中：
- 因为x1小于1024，所以触发2倍扩容，内存对齐后最终分配新的 cap 为 2048
- x2由于超过了1024，所以只进行了1.25倍的扩容，最终新容量是 1280
我们可以看到，这个扩容其实并不合理，就是因为跳崖式扩容系数的变更（2倍变成1.25倍），导致了这种问题。
放到Go1.18之后执行，输出：
1360
1536
- 1360：1024在新版中是1.44倍的扩容，原来是2倍，所以结果变小
- 1536：老版本是1.25倍扩容，新版中表达式计算出来此时的增长因子为1.35，所以结果变大
从结果来看，新版Go切片扩容的更合理：切片越大，增长系数随之变小，扩容越缓慢，所以上面的问题得到了有效解决。
看下面的表格，扩容系数的差异一目了然：
| class_size | <= Go1.17 | >= G1.18 |
|---|---|---|
| 256 | 2.0 | 2.0 |
| 512 | 2.0 | 1.63 |
| 1024 | 2.0 | 1.44 |
| 2048 | 1.25 | 1.35 |
不对称
当我们调换2个切片的顺序后，合并切片的容量并不相等，因为Go的切片扩容策略是根据第一个参数的容量进行计算的。
x := make([]int, 98)
y := make([]int, 666)
println(cap(append(x, y...))) // 768
println(cap(append(y, x...))) // 1360
Go1.20执行输出：
768
1024
追加顺序问题
以第一个切片的容量计算扩容，在某些case下并不合理
x := make([]byte, 100, 500)
y := make([]byte, 500)
println(cap(append(x, y...))) // 1024
println(cap(append(x[:len(x):len(x)], y...))) // 640
Go1.20执行输出：
896
640
我们看到，问题2和问题3在最新的Go1.18以及截止到目前Go1.20为止，并没有得到解决。切片扩容策略严格依赖第一个切片的容量，所以更换切片顺序，reslice等会影响新切片的容量。
根据这个特性，在某些极端性能优化的场景下，考虑 x往y追加，还是y往x追加就变得有意义，当然可能更好的做法是尽力避免动态扩容。
总结
- 新容量计算
- 如果期望大小超过现有容量2倍，则直接使用期望容量
- 如果容量小于1024（
Go1.18后是256），2倍扩容，否则1.25倍扩容（Go1.18后由表达式计算，不再是固定值）
- 最终容量计算：为了避免内存碎片，最后会进行
内存对齐计算，所以最后的结果会大于等于上面计算的值。
作者简介：一线Gopher，公众号《Go和分布式IM》运营者，开源项目： CoffeeChat 、interview-golang 发起人 & 核心开发者，终身程序员。