你知道的Go切片扩容机制可能是错的

太白技术

发布于 2022-09-01 14:32:31

5870

发布于 2022-09-01 14:32:31

文章被收录于专栏：太白技术太白技术

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

1 前言
2 代码片段1
3 代码片段2
4 growslice源代码
5 代码片段3
6 go1.18beta1的变化
7 总结

1 前言

上一篇《Go切片与技巧（附图解）》，我们讲到了Go内置函数append操作，当append操作的时候，切片容量如果不够，会触发扩容。

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

结论1：

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

结论2：

在结论1的基础上（切片的预估容量阶段），提到了内存对齐，容量计算完了后还要考虑到内存的高效利用，进行内存对齐。

其中结论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帮我们干了什么。

我们可以通过delve来调式我们的Go代码。这边演示的Go版本：1.16.5。

通过打断点b main.main、然后用si指令定位到以下代码，runtime.growslice()正式Go扩容的源代码。

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

通过刚才的debug我们可以找到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)

我们通过locals指令获取newcap的变量变成了6，newcap = int(capmem / sys.PtrSize)，从下面结构结果看出capmem=48，而sys.PtrSize等于8（case et.size == sys.PtrSize，et为int类型的，在64位操作系统是8字节），所以6(newcap) = 48(capmem) / 8(sys.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

那么关键点在于capmem怎么变成了48而不是40，lenmem=0，newlenmem=5，所以capmem = roundupsize(uintptr(newcap) * sys.PtrSize) 带入变量变成capmem = roundupsize(5 * 8)，所以主要是roundupsize影响了最终的结果。

通过debug，我们发现执行到了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 {

这个时候我们的size是40，uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])带入变量变成：divRoundUp(40, 8) returns ceil(n / a).等于40 / 8 = 5

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)]结果是5，

我们来看下这个变量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的变化

上面分析是基于go1.16.5的，太白注意到go1.18之后，growslice改了

1024变成了256，公式也改了，newcap += newcap / 4变成了newcap += (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 总结

1、前言中的结论1讲法不严谨，讲对了一部分（代码片段1可知），不同的切片类型，扩容值可能是不同的（代码片段3可知），Go的runtime分配内存的时候，会调用roundupsize，取整内存值（代码片段2可知）。
2、前言中的结论2比结论1好一点，但它是基于结论1的，随着Go版本的迭代，这个结论也会过时。
3、Go切片的扩容机制还是比较复杂的，受到Go版本、操作系统、数据类型等因数，其机制都会有不同，要具体情况具体分析，不要单一的记下一个结论就觉得ok。
4、网上的文章参差不齐，大家在搜资料的时候，需要我们去甄别，最好自己去验证下。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-02-06，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自太白技术微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度