Go的slice扩容机制
扩容
说实话，我看到别的文章中说slice的扩容很简单，小于1024，按照两倍去扩容；大于等于1024，按照1.25去扩容；像这样不负责任的文章误导初学者使我非常不爽，今天就给大家带来源码级别的slice扩容机制，别怕，一切都是那么简单。
1. 先看一个例子（<1024）
package main import "fmt" func main() { s1 := make([]int, 1023) s2 := make([]int, 1) s1 = append(s1, s2...) fmt.Println(cap(s1), len(s1)) } 输出结果是： 2048 1024 从结果可以看出，小于1024的确实按照2倍去扩容的，我们不妨计作： f(x) = 2x (x<1024)
大家知道为什么是1024吗？有人问过go作者，说为啥不是2048啊之类的，你猜作者怎么回答，非常简单的一句话：因为在计算机世界中1024这个数字很特别，它就是一个数字，是一个以2为底，10为指数的数，就这样简单。所以有时候大家看源码别纠结细节，一旦陷入就要请求旁边的高人将自己解救出来呀。
2. 再看一个例子(>=1024)
package main import "fmt" func main() { s1 := make([]int, 1024) s2 := make([]int, 258) s1 = append(s1, s2...) fmt.Println(cap(s1), len(s1)) } 输出结果是： 1696 1282 从结果可以看出，大于等于1024，不是按照1.25(1+1/4)的倍速增长的，所以: f(x) = x + x/4 (x>=1024)就突然不成立了，这到底是为什么？是不是想要一探究尽呢？接下来剖析源码就知道啦。
3. 两个函数
f(x) = 2x (x<1024) f(x) = x + x/4 (x >= 1024)
确认：函数1成立，函数2在有些条件下成立 嗯？为什么在有些条件下成立呢？再看一个例子：
package main import "fmt" func main() { s1 := make([]int, 1024) s2 := make([]int, 1) s1 = append(s1, s2...) fmt.Println(cap(s1), len(s1)) } 输出结果是： 1280 1025
我们可以带函数2去计算下：f(1024) = 1024 + 1024/4 = 1024 + 256 = 1280你看这样的就可以满足函数2了，接下来分析下上面不满足函数2的例子。
4. 源码剖析不满足1.25增速的原因
在源码中主要是看growslice这个函数。
func growslice(et *_type, old slice, cap int) slice { ... ... ... //省略前面无关紧要的代码 newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if old.len < 1024 { //小于1024 double就可以 newcap = doublecap } else { for 0 < newcap && newcap < cap { // 容量比之前大，那么按照1.25的倍速增长 newcap += newcap / 4 } } } ... //省略部分代码 var lenmem, newlenmem, capmem uintptr switch { ... //省略 case et.size == sys.PtrSize: lenmem = uintptr(old.len) * sys.PtrSize newlenmem = uintptr(cap) * sys.PtrSize // 看这里 核心函数roundupsize 按照内存字节对齐 capmem = roundupsize(uintptr(newcap) * sys.PtrSize) overflow = uintptr(newcap) > maxAlloc/sys.PtrSize newcap = int(capmem / sys.PtrSize) //1696 ...//省略部分代码 } }
好了按照代码流程先走一遍：
- 首先我们的长度是大于等于1024的，那么按照上面逻辑先计算得出：f(1024)=1280，发现其实空间还不够，那么继续扩容
f(1280)=1280+1280/4=1600。 - 紧接着进入switch case中，这里的sys.PtrSize=8，而我们的et.size因为是int存储所以也是8，刚好命中这个case，进入。
- 然后计算新元素
capmem=roundupsize(uintptr(newcap) * sys.PtrSize)，则capmem=roundupsize(1600*8)=roundupsize(12800)。 - 在
roundupsize函数中size=12800<_MaxSmallSize(32768)，并且size<=smallSizeMax(1024)-8不满足，所以最终进入else代码段。
func roundupsize(size uintptr) uintptr { if size < _MaxSmallSize { if size <= smallSizeMax-8 { return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]]) } else { // 进入到这里 return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]]) } } if size+_PageSize < size { return size } return alignUp(size, _PageSize) } // divRoundUp returns ceil(n / a). func divRoundUp(n, a uintptr) uintptr { // a is generally a power of two. This will get inlined and // the compiler will optimize the division. return (n + a - 1) / a }
- 看下class_to_size和size_to_class128
const ( _MaxSmallSize = 32768 smallSizeDiv = 8 smallSizeMax = 1024 largeSizeDiv = 128 _NumSizeClasses = 67 _PageShift = 13 ) 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} var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{ 32, 33, 34, 35, 36, 37, 37, 38, 38, 39, 39, 40, 40, 40, 41, 41, 41, 42, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 48, 48, 48, 49, 49, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67}
- 通过函数
divRoundUp(size-smallSizeMax, largeSizeDiv)计算出：divRoundUp(12800-1024, 128) = divRoundUp(12800-1024, 128) = (12800-1024+128-1) / 128 = 11903/128=92 - 我们根据92在size_to_class128中找到是57，然后在class_to_size中根据索引57找到是13568。
- 所以roundupsize函数返回13568，而
newcap = int(capmem / sys.PtrSize) = 13568/8 = 1696，至此我们就求出来cap的最终容量是1696啦。 - 注意我的go源码版本是
go1.16.7
5. 小结
看完源码之后心情舒爽，我相信大家肯定会更自信了，不管同事问你还是面试官问你，你可以自豪的给他从源码角度分析了，而且别人一听就能判断出你是读过源码的，求知欲满满！
如果你觉得这篇文章对你帮助很大，请你转发、分享、关注、点赞哦，写作不易，还望大家多多支持哈。
