前言

go 的切片可以自动地进行扩容，当调用append方法时，如果len == cap，即容纳不下新的元素的时， 底层会帮我们为切片的底层数组分配更大的内存空间，然后把旧的切片的底层数组指针指向新的内存中

• 注意不是根据底层数据的容量来判断是否扩容，而是根据slice的属性cap，cap可能比数组实际容量小

分配更大的内存时预留的一定的buffer

• 如果不预留，只考虑当前新增的元素，则每次append时都会发生数据拷贝，成本太高

于是slice扩容的重点就在于，预留多少buffer？

1.18以前

直接看源码：

源码位置：/src/runtime/slice.go growslice

func growslice(et *_type, old slice, cap int) slice {// ...newcap := old.capdoublecap := newcap + newcapif 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}if newcap <= 0 {newcap = cap}}}// ...capmem = roundupsize(uintptr(newcap))

新容量的计算规则如下：

• 需要的容量比2倍老容量大：使用需要的容量

  • 一般发生于append一个较大的slice时，例如 append(s, s1...)

• 如果老容量小于1024，按照2倍扩容

• 如果老容量大于等于1024，按照1.25倍扩容，对应源码newcap += newcap / 4

• 如果newcap溢出了int最大值，不扩容

最后再按照内存分配块的大小，向上修正

内存分配各个size如下：{0, 8, 16, 24, 32, 48, 64, 80, 96, 112...}

例如，如果slice为int类型，有5个元素，应该占40个字节，但由于分配到size=48的内存块，会向上修正到48字节，也就是cap变为6

func main() {s := []int{}s = append(s, []int{1, 2, 3, 4, 5}...)fmt.Println(cap(s))  // 结果为6
}

这个扩容规则有什么问题？

1. 不够平滑：容量小于1024时2倍扩容，大于1024突然降到1.25倍扩容

2. 容量增长不单调，正常应该是较大的初始容量扩容后有较大的最终容量

   1. 例如以下代码：

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的容量比x2小，都增加100个元素后x1的容量反而比x2大

1.18以后

go在这次提交中 runtime: make slice growth formula a bit smoother修改了扩容规则：

其用一个更平滑的公式来计算扩容因子，在256个元素之前还是2倍扩容因子，在256个元素后逐步减少，不同容量下的扩容因子如下：

改版后代码如下：

// ...
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {newcap = cap
} else {const threshold = 256if old.cap < threshold {newcap = doublecap} else {for 0 < newcap && newcap < cap {newcap += (newcap + 3*threshold) / 4}if newcap <= 0 {newcap = cap}}
}
// ...

在容量256以后，预留的buffer容量为 1/4原容量，加上了 3/4 * 256

这样当old.cap为256时还是2倍扩容，随着容量增大3/4 * 256占原容量的比例逐渐降低，最终收敛于0，达到平滑扩容的效果

总结

• 1.18以前：

  • 容量小于1024时为2倍扩容，大于等于1024时为1.25倍扩容

• 1.18以后：

  • 小于256时为2倍扩容，大于等于256时的扩容因子逐渐从2减低为1.25

• 不管1.18前后，最终需要按照内存分配块向上修正