引言

Go1.18之前切片的扩容是以容量1024为临界点，当旧容量 < 1024个元素,扩容变成2倍；当旧容量 > 1024个元素，那么会进入一个循环，每次增加25%直到大于期望容量。

然而这个扩容机制已经被Go 1.18弃用了，官方说新的扩容机制能更平滑地过渡。

测试代码

  1. go
  2. 复制代码
  3. //go 1.18
  4. func TestSliceGrowing(t *testing.T) {
  5.    s := []int{}
  6.    for i := 0; i < 4098; i++ {
  7.       s = append(s, i)
  8.       t.Log(len(s), cap(s))
  9.    }
  10. }

运行结果：

  1. yaml
  2. 复制代码
  3. === RUN   TestSliceGrowing
  4.     slice_test.go:32: 1 1
  5.     slice_test.go:32: 2 2
  6.     slice_test.go:32: 3 4
  7.     slice_test.go:32: 4 4
  8.     slice_test.go:32: 5 8
  9.     slice_test.go:32: 6 8
  10.     slice_test.go:32: 7 8
  11.     slice_test.go:32: 8 8
  12.     slice_test.go:32: 9 16
  13.     ......
  14.     slice_test.go:32: 128 128
  15.     slice_test.go:32: 129 256
  16.     ......
  17.     slice_test.go:32: 256 256
  18.     slice_test.go:32: 257 512
  19.     ......
  20.     slice_test.go:32: 512 512
  21.     slice_test.go:32: 513 848
  22.     ......
  23.     slice_test.go:32: 848 848
  24.     slice_test.go:32: 849 1280
  25.     ......
  26.     slice_test.go:32: 1280 1280
  27.     slice_test.go:32: 1281 1792
  28.     ......
  29.     slice_test.go:32: 1792 1792
  30.     slice_test.go:32: 1793 2560
  31.     ......
  32.     slice_test.go:32: 2560 2560
  33.     slice_test.go:32: 2561 3408
  34.     ......
  35.     slice_test.go:32: 3408 3408
  36.     slice_test.go:32: 3409 5120

Go 1.17版本切片扩容

Go 1.17切片扩容时会进行内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于老 slice 容量的 2倍或者1.25倍。

  • 当新切片需要的容量cap大于两倍扩容的容量，则直接按照新切片需要的容量扩容；
  • 当原 slice 容量 < 1024 的时候，新 slice 容量变成原来的 2 倍；
  • 当原 slice 容量 > 1024，进入一个循环，每次容量变成原来的1.25倍,直到大于期望容量。

公式如下：

568.新版的golang slice切片扩容机制 - 图1

  1. go
  2. 复制代码
  3. // runtime/slice.go
  4. // et：表示slice的一个元素；old：表示旧的slice； cap：表示新切片需要的容量；
  5. func growslice(et *_type, old slice, cap int) slice {
  6.     if cap < old.cap {
  7.         panic(errorString("growslice: cap out of range"))
  8.     }
  10.     if et.size == 0 {
  11.         // append should not create a slice with nil pointer but non-zero len.
  12.         // We assume that append doesn't need to preserve old.array in this case.
  13.         return slice{unsafe.Pointer(&zerobase), old.len, cap}
  14.     }
  16.     newcap := old.cap
  17.         // 两倍扩容
  18.     doublecap := newcap + newcap
  19.         // 新切片需要的容量大于两倍扩容的容量，则直接按照新切片需要的容量扩容
  20.     if cap > doublecap {
  21.         newcap = cap
  22.     } else {
  23.         // 原 slice 容量小于 1024 的时候，新 slice 容量按2倍扩容
  24.         if old.cap < 1024 {
  25.             newcap = doublecap
  26.         } else { // 原 slice 容量超过 1024，新 slice 容量变成原来的1.25倍。
  27.             // Check 0 < newcap to detect overflow
  28.             // and prevent an infinite loop.
  29.             for 0 < newcap && newcap < cap {
  30.                 newcap += newcap / 4
  31.             }
  32.             // Set newcap to the requested cap when
  33.             // the newcap calculation overflowed.
  34.             if newcap <= 0 {
  35.                 newcap = cap
  36.             }
  37.         }
  38.     }
  40.         // 后半部分还对 newcap 作了一个内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于 老 slice 容量的 2倍或者1.25倍。
  41.     var overflow bool
  42.     var lenmem, newlenmem, capmem uintptr
  43.     // Specialize for common values of et.size.
  44.     // For 1 we don't need any division/multiplication.
  45.     // For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
  46.     // For powers of 2, use a variable shift.
  47.     switch {
  48.     case et.size == 1:
  49.         lenmem = uintptr(old.len)
  50.         newlenmem = uintptr(cap)
  51.         capmem = roundupsize(uintptr(newcap))
  52.         overflow = uintptr(newcap) > maxAlloc
  53.         newcap = int(capmem)
  54.     case et.size == sys.PtrSize:
  55.         lenmem = uintptr(old.len) * sys.PtrSize
  56.         newlenmem = uintptr(cap) * sys.PtrSize
  57.         capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
  58.         overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
  59.         newcap = int(capmem / sys.PtrSize)
  60.     case isPowerOfTwo(et.size):
  61.         var shift uintptr
  62.         if sys.PtrSize == 8 {
  63.             // Mask shift for better code generation.
  64.             shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
  65.         } else {
  66.             shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
  67.         }
  68.         lenmem = uintptr(old.len) << shift
  69.         newlenmem = uintptr(cap) << shift
  70.         capmem = roundupsize(uintptr(newcap) << shift)
  71.         overflow = uintptr(newcap) > (maxAlloc >> shift)
  72.         newcap = int(capmem >> shift)
  73.     default:
  74.         lenmem = uintptr(old.len) * et.size
  75.         newlenmem = uintptr(cap) * et.size
  76.         capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
  77.         capmem = roundupsize(capmem)
  78.         newcap = int(capmem / et.size)
  79.     }
  80. }

Go 1.18版本切片扩容

Go1.18不再以1024为临界点，而是设定了一个值为256的threshold，以256为临界点；超过256，不再是每次扩容1/4，而是每次增加（旧容量+3*256）/4；

  • 当新切片需要的容量cap大于两倍扩容的容量，则直接按照新切片需要的容量扩容；
  • 当原 slice 容量 < threshold 的时候，新 slice 容量变成原来的 2 倍；
  • 当原 slice 容量 > threshold，进入一个循环，每次容量增加（旧容量+3*threshold）/4。

公式如下：

568.新版的golang slice切片扩容机制 - 图2

如下代码所示：

  1. go
  2. 复制代码
  3. //1.18
  4. newcap := old.cap
  5. doublecap := newcap + newcap
  6. if cap > doublecap {
  7.   newcap = cap
  8. } else {
  9.   const threshold = 256
  10.   if old.cap < threshold {
  11.     newcap = doublecap
  12.   } else {
  13.     // Check 0 < newcap to detect overflow
  14.     // and prevent an infinite loop.
  15.     for 0 < newcap && newcap < cap {
  16.       // Transition from growing 2x for small slices
  17.       // to growing 1.25x for large slices. This formula
  18.       // gives a smooth-ish transition between the two.
  19.       newcap += (newcap + 3*threshold) / 4
  20.     }
  21.     // Set newcap to the requested cap when
  22.     // the newcap calculation overflowed.
  23.     if newcap <= 0 {
  24.       newcap = cap
  25.     }
  26.   }
  27. }

在1.18中，优化了切片扩容的策略，让底层数组大小的增长更加平滑： 通过减小阈值并固定增加一个常数，使得优化后的扩容的系数在阈值前后不再会出现从2到1.25的突变，该commit作者给出了几种原始容量下对应的“扩容系数”：

oldcap 扩容系数
256 2.0
512 1.63
1024 1.44
2048 1.35
4096 1.30

可以看到，Go1.18的扩容策略中，随着容量的增大，其扩容系数是越来越小的，可以更好地节省内存。

我们可以试着求一个极限，当oldcap远大于256的时候，扩容系数将会变成1.25。

总结

总的来说，Go的设计者不断优化切片扩容的机制，其目的只有一个：就是控制让小的切片容量增长速度快一点，减少内存分配次数，而让大切片容量增长率小一点，更好地节省内存。

  • 如果只选择翻倍的扩容策略，那么对于较大的切片来说，现有的方法可以更好的节省内存。
  • 如果只选择每次系数为1.25的扩容策略，那么对于较小的切片来说扩容会很低效。
  • 之所以选择一个小于2的系数，在扩容时被释放的内存块会在下一次扩容时更容易被重新利用