你好，我是太白，今天和你探索下Go语言的切片扩容机制。

如果觉得文章对你有帮助，记得点赞+关注。目前本公众号没有评论功能，有问题请联系我。

【关注二维码】




1 前言 

append

关于Go切片的扩容机制，网上文章很多，很多结论是这样的：

结论1：

  • 1、当需要的容量超过原切片容量的两倍时，会使用需要的容量作为新容量。
  • 2、当原切片长度小于1024时，新切片的容量会直接翻倍。而当原切片的容量大于等于1024时，会反复地增加25%，直到新容量超过所需要的容量。

结论2：

内存对齐

其中结论1，可能最让人熟知。

本文将和你一起来探索下这个切片的扩容机制，看看到底是不是这样的。

2 代码片段1 

 s := make([]int, 0)
 s = append(s, 1)
 fmt.Println("cap s", cap(s)) // cap s 1
 s = append(s, 2)
 fmt.Println("cap s", cap(s)) // cap s 2
 s = append(s, 3)
 fmt.Println("cap s", cap(s)) // cap s 4
 s = append(s, 4)
 fmt.Println("cap s", cap(s)) // cap s 4
 s = append(s, 5)
 fmt.Println("cap s", cap(s)) // cap s 8

从代码的结果，我们可以看到，容量是成翻倍扩容的。符合前言提到的结论1的第一点。

 s2 := make([]int, 1024)
 fmt.Println("cap s2", cap(s2)) // cap s2 1024
 s2 = append(s2, 1)
 fmt.Println("cap s2", cap(s2)) // cap s2 1280
 s2 = append(s2, 2)
 fmt.Println("cap s2", cap(s2)) // cap s2 1280

从代码的结果，我们可以看到，当原切片的容量大于1024时，符合前言提到的结论1的第二点。

3 代码片段2

我们来看下下面的这端代码，执行结果是6，为什么不是8呢？这个和前言提到的结论1貌似有冲突。

 s3 := make([]int, 0)
 s3 = append(s3, 1, 2, 3, 4, 5)
 fmt.Println("cap s3", cap(s3)) // cap s3 6

4 growslice源代码

为了解释上面的代码片段2，我们开看下go的runtime帮我们干了什么。

1.16.5
b main.mainsiruntime.growslice()
(dlv) si
> runtime.growslice() /Users/xujiajun/go/go1.16.5/src/runtime/slice.go:125 (PC: 0x10483a0)
Warning: debugging optimized function
   120: // NOT to the new requested capacity.
   121: // This is for codegen convenience. The old slice's length is used immediately
   122: // to calculate where to write new values during an append.
   123: // TODO: When the old backend is gone, reconsider this decision.
   124: // The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
=> 125: func growslice(et *_type, old slice, cap int) slice {
   126:  if raceenabled {
   127:   callerpc := getcallerpc()
   128:   racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
   129:  }
   130:  if msanenabled {

growslice$GOROOT/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 {
  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
...
if cap > doublecap {
  newcap = cap
 } else {
  
...

locals
newcap = 5
doublecap = 0

那么newcap最后怎么变成了6呢？我们继续往下看。通过debug，我们发现执行到以下代码位置：

   178:  case et.size == sys.PtrSize:
   179:   lenmem = uintptr(old.len) * sys.PtrSize
   180:   newlenmem = uintptr(cap) * sys.PtrSize
   181:   capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
   182:   overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
=> 183:   newcap = int(capmem / sys.PtrSize)

localsnewcap = int(capmem / sys.PtrSize)capmem=48sys.PtrSize
(dlv) locals
newcap = 6
doublecap = (unreadable could not find loclist entry at 0x2b3ae for address 0x1050d70)
overflow = false
newlenmem = 5
lenmem = 0
capmem = 48

lenmem=0newlenmem=5capmem = roundupsize(uintptr(newcap) * sys.PtrSize)capmem = roundupsize(5 * 8)roundupsize
return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
    11:
    12: // Returns size of the memory block that mallocgc will allocate if you ask for the size.
    13: func roundupsize(size uintptr) uintptr {
    14:  if size < _MaxSmallSize {
    15:   if size <= smallSizeMax-8 {
=>  16:    return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
    17:   } else {
    18:    return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
    19:   }
    20:  }
    21:  if size+_PageSize < size {

uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])divRoundUp(40, 8) returns ceil(n / a).
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32}


size_to_class8[divRoundUp(size, smallSizeDiv)]
class_to_size
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}

带入结果5，class_to_size[5] 刚好对应的是 48。

总结下上面的关键值：

doublecap = 0 + 0

newcap = 5 

newcap > doublecap 

capmem = roundupsize(5 * 8)  = 48

newcap = int(48 / 8) = 6

5 代码片段3

特别提下，下面两端切片类型不同，扩容的结果也不同，大家可以自行debug下，所以前言提到的结论1中翻倍的结论也是有问题的。

 s := make([]int32, 0)
 s = append(s, 1)
 fmt.Println("cap s", cap(s)) // cap s 2

 s := make([]int, 0)
 s = append(s, 1)
 fmt.Println("cap s", cap(s)) // cap s 1

6 go1.18beta1的变化 

growslice
1024256newcap += newcap / 4newcap += (newcap + 3*threshold) / 4
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
   }
  }
 }

7 总结 

不同的切片类型，扩容值可能是不同的roundupsize
读完文章觉得对你有帮助，记得关注下方公众号二维码，第一时间收到最新文章推送。