深入理解 Go slice 扩容机制

前言

appendlen == cap

cap

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

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

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

1.18以前

直接看源码：

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

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
         }
         if newcap <= 0 {
            newcap = cap
         }
      }
   }
   
   // ...
   
   capmem = roundupsize(uintptr(newcap))

新容量的计算规则如下：

append(s, s1...)1024210241.25newcap += newcap / 4

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

{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
}

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

不够平滑：容量小于1024时2倍扩容，大于1024突然降到1.25倍扩容
容量增长不单调，正常应该是较大的初始容量扩容后有较大的最终容量
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以后

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

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

改版后代码如下：

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

3/4 * 256

逐渐降低最终收敛于0

总结

1.18以前：
- 容量小于1024时为2倍扩容，大于等于1024时为1.25倍扩容
1.18以后：
- 小于256时为2倍扩容，大于等于256时的扩容因子逐渐从2减低为1.25
不管1.18前后，最终需要按照内存分配块向上修正