在 Go 语言中,有一个很常用的数据结构,那就是切片(Slice)。
切片是一个拥有相同类型元素的可变长度的序列,它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。
切片是一种引用类型,它有三个属性:指针,长度和容量。
底层源码定义如下:
- 指针: 指向 slice 可以访问到的第一个元素。
- 长度: slice 中元素个数。
- 容量: slice 起始元素到底层数组最后一个元素间的元素个数。
make([]byte, 5)
声明和初始化
切片的使用还是比较简单的,这里举一个例子,直接看代码吧。
扩容时机
append
扩容时,Go 运行时会分配一个新的底层数组,并将原始切片中的元素复制到新数组中。然后,原始切片将指向新数组,并更新其长度和容量。
make
append
append
追加多个值:
输出结果为:
初始切片: [1 2 3]
追加多个值后的切片: [1 2 3 4 5 6]
再来看一下直接追加一个切片:
输出结果为:
初始切片: [1 2 3]
追加另一个切片后的切片: [1 2 3 4 5 6]
再来看一个发生扩容的例子:
输出结果为:
初始状态: len=0 cap=3 []
添加元素1: len=1 cap=3 [1]
添加元素2: len=2 cap=3 [1 2]
添加元素3: len=3 cap=3 [1 2 3]
添加元素4: len=4 cap=6 [1 2 3 4]
添加元素5: len=5 cap=6 [1 2 3 4 5]
03append5
46
表面现象已经看到了,接下来,我们就深入到源码层面,看看切片的扩容机制到底是什么样的。
源码分析
appendappendgrowslice
growsliceappend
growslicegrowslice
切片扩容策略有两个阶段,go1.18 之前和之后是不同的,这一点在 go1.18 的 release notes 中有说明。
下面我用 go1.17 和 go1.18 两个版本来分开说明。先通过一段测试代码,直观感受一下两个版本在扩容上的区别。
append
然后记录容量的变化,每当容量发生变化的时候,记录下老的容量,添加的元素,以及添加完元素之后的容量。
这样就可以观察,新老 slice 的容量变化情况,从而找出规律。
运行结果(1.17 版本):
[0 -> -1] cap = 0 | after append 0 cap = 1
[0 -> 0] cap = 1 | after append 1 cap = 2
[0 -> 1] cap = 2 | after append 2 cap = 4
[0 -> 3] cap = 4 | after append 4 cap = 8
[0 -> 7] cap = 8 | after append 8 cap = 16
[0 -> 15] cap = 16 | after append 16 cap = 32
[0 -> 31] cap = 32 | after append 32 cap = 64
[0 -> 63] cap = 64 | after append 64 cap = 128
[0 -> 127] cap = 128 | after append 128 cap = 256
[0 -> 255] cap = 256 | after append 256 cap = 512
[0 -> 511] cap = 512 | after append 512 cap = 1024
[0 -> 1023] cap = 1024 | after append 1024 cap = 1280
[0 -> 1279] cap = 1280 | after append 1280 cap = 1696
[0 -> 1695] cap = 1696 | after append 1696 cap = 2304
运行结果(1.18 版本):
[0 -> -1] cap = 0 | after append 0 cap = 1
[0 -> 0] cap = 1 | after append 1 cap = 2
[0 -> 1] cap = 2 | after append 2 cap = 4
[0 -> 3] cap = 4 | after append 4 cap = 8
[0 -> 7] cap = 8 | after append 8 cap = 16
[0 -> 15] cap = 16 | after append 16 cap = 32
[0 -> 31] cap = 32 | after append 32 cap = 64
[0 -> 63] cap = 64 | after append 64 cap = 128
[0 -> 127] cap = 128 | after append 128 cap = 256
[0 -> 255] cap = 256 | after append 256 cap = 512
[0 -> 511] cap = 512 | after append 512 cap = 848
[0 -> 847] cap = 848 | after append 848 cap = 1280
[0 -> 1279] cap = 1280 | after append 1280 cap = 1792
[0 -> 1791] cap = 1792 | after append 1792 cap = 2560
根据上面的结果还是能看到区别的,具体扩容策略下面边看源码边说明。
go1.17
growslice
在分配内存空间之前需要先确定新的切片容量,运行时根据切片的当前容量选择不同的策略进行扩容:
- 如果期望容量大于当前容量的两倍就会使用期望容量;
- 如果当前切片的长度小于 1024 就会将容量翻倍;
- 如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;
go1.18
newcap += (newcap + 3*threshold) / 4
在分配内存空间之前需要先确定新的切片容量,运行时根据切片的当前容量选择不同的策略进行扩容:
newcap + 3*threshold
内存对齐
分析完两个版本的扩容策略之后,再看前面的那段测试代码,就会发现扩容之后的容量并不是严格按照这个策略的。
那是为什么呢?
growsliceroundupsizenewcap
这个函数的实现就不在这里深入了,先挖一个坑,以后再来补上。
总结
appendappendgrowslice
切片扩容分两个阶段,分为 go1.18 之前和之后:
一、go1.18 之前:
- 如果期望容量大于当前容量的两倍就会使用期望容量;
- 如果当前切片的长度小于 1024 就会将容量翻倍;
- 如果当前切片的长度大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;
二、go1.18 之后:
newcap + 3*threshold