切片是怎样扩容的
切片扩容发生在调用 append() 时，如果切片的底层数组长度已经不足以容纳新添加的元素时，就会触发扩容，此时go编译器会调用 growslice() 确定新的容量大小，然后拷贝老的元素到新的底层数组。
扩容策略自 runtime: make slice growth formula a bit smoother提交后有一些改变，这个提交自Go1.18后生效，主要有2处优化：2倍扩容由1024改成256，超过之后固定1.25倍扩容改成了表达式计算，使扩容下降的更平滑。
Go1.17扩容实现
扩容策略源码如下：
// go.17 src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
newcap := old.cap
doublecap := newcap + newcap
// 1.新容量计算
if cap > doublecap {
newcap = cap
} else {
if old.cap < 1024 {
newcap = doublecap
} else {
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
// ...
// 2.内存对齐计算，最终的的容量会大于等于上面的 newcap
var overflow bool
var lenmem, newlenmem, capmem uintptr
switch {
case et.size == 1:
// ...
case et.size == sys.PtrSize:
lenmem = uintptr(old.len) * sys.PtrSize
newlenmem = uintptr(cap) * sys.PtrSize
capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
newcap = int(capmem / sys.PtrSize)
case isPowerOfTwo(et.size):
// ...
default:
// ...
}
//...
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
}
- 新容量计算
- 如果期望大小超过现有容量2倍，则直接使用期望容量
- 如果容量小于1024（
Go1.18后是256），2倍扩容，否则1.25倍扩容（Go1.18后由表达式计算）
- 最终容量计算：为了避免内存碎片，最后会进行
内存对齐计算，所以最后的结果会大于等于上面计算的值。
roundupsize 函数用来计算内存对齐后最终的容量值，实际上就是根据所需内存大小进行向上取整，然后使用数组 class_to_size 中的整数以提供内存分配效率并减少内存碎片：
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, ...}
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, ...}
func roundupsize(size uintptr) uintptr {
if size < _MaxSmallSize { // 32768
if size <= smallSizeMax-8 { // 1024
return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
} else {
return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
}
}
// ...
}
下面是这个数组预定义的内存大小（class是size_to_class8计算的索引，bytes/obj是class_to_size中存放的整数）：
class bytes/obj bytes/span objects tail waste max waste min align
1 8 8192 1024 0 87.50% 8
2 16 8192 512 0 43.75% 16
3 24 8192 341 8 29.24% 8
4 32 8192 256 0 21.88% 32
5 48 8192 170 32 31.52% 16
...
67 32768 32768 1 0 12.50% 8192
我们来看一个实例：
var s []int // len: 0 cap: 0
s = append(s, 1, 2)
fmt.Println(s, len(s), cap(s)) // len: 2 cap: 2
s = append(s, 3, 4, 5)
fmt.Println(s, len(s), cap(s)) // len: 5 cap: 6
s = append(s, 6, 7)
fmt.Println(s, len(s), cap(s)) // len: 6 cap: 12
- nil切片
s的len和cap都为0 - 当添加元素
1,2时，期望容量是2，当前容量是0，满足cap > doublecap条件，故新容量为2。然后进行内存对齐计算，int在64位占8字节，于是需要2*6=16字节的内存，查上表Go可分配该大小，于是cap最终为2。 - 当添加元素
3,4,5时，也满足期望容量超过2倍当前容量的条件（cap > doublecap），于是初步计算出新容量为5。此时需要内存大小为5*8=40，为了减少内存碎片以及提高分配效率，进行内存对齐计算后向上取整得到48，48/8=6个元素，于是cap最终为6。 - 当添加元素
6,7时，旧容量小于1024（G1.18后要小于256），于是2倍扩容得到12，12*8=96满足内存分配要求，故最终cap为12。
最后，自 Go1.18 开始，超过256扩容大小改成了表达式计算，不再是固定的1.25倍（1.25倍 < growth factor < 2倍）：
// go1.18 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 {
const threshold = 256 // 之前是1024
if old.cap < threshold {
newcap = doublecap
} else {
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
}
if newcap <= 0 {
newcap = cap
}
}
}
//...
}
引入该表达式后，扩容会更加平滑， Keith Randall 大神提交的描述给出了一个示例（growth factor越来越小）：
runtime: make slice growth formula a bit smoother
Instead of growing 2x for < 1024 elements and 1.25x for >= 1024 elements,
use a somewhat smoother formula for the growth factor. Start reducing
the growth factor after 256 elements, but slowly.
starting cap growth factor
256 2.0
512 1.63
1024 1.44
2048 1.35
4096 1.30