也就是新 slice
的容量是留了一定的 buffer
的。否则,每次添加元素的时候,都会发生迁移,成本太高。
新 slice 预留的 buffer
大小是有一定规律的。网上大多数的文章都是这样描述的:
当原 slice 容量小于 1024
的时候,新 slice 容量变成原来的 2
倍;原 slice 容量超过 1024
,新 slice 容量变成原来的1.25
倍。
我在这里先说结论:以上描述是错误的。
为了说明上面的规律是错误的,我写了一小段玩具代码:
package main
import "fmt"
func main() {
s := make([]int, 0)
oldCap := cap(s)
for i := 0; i < 2048; i++ {
s = append(s, i)
newCap := cap(s)
if newCap != oldCap {
fmt.Printf("[%d -> %4d] cap = %-4d | after append %-4d cap = %-4d\n", 0, i-1, oldCap, i, newCap)
oldCap = newCap
}
}
}
我先创建了一个空的 slice
,然后,在一个循环里不断往里面 append
新的元素。然后记录容量的变化,并且每当容量发生变化的时候,记录下老的容量,以及添加完元素之后的容量,同时记下此时 slice
里的元素。这样,我就可以观察,新老 slice
的容量变化情况,从而找出规律。
运行结果:
[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
在老 slice 容量小于1024的时候,新 slice 的容量的确是老 slice 的2倍。目前还算正确。
但是,当老 slice 容量大于等于 1024
的时候,情况就有变化了。当向 slice 中添加元素 1280
的时候,老 slice 的容量为 1280
,之后变成了 1696
,两者并不是 1.25
倍的关系(1696/1280=1.325)。添加完 1696
后,新的容量 2304
当然也不是 1696
的 1.25
倍。
可见,现在网上各种文章中的扩容策略并不正确。我们直接搬出源码:源码面前,了无秘密。
从前面汇编代码我们也看到了,向 slice 追加元素的时候,若容量不够,会调用 growslice
函数,所以我们直接看它的代码。
// go 1.9.5 src/runtime/slice.go:82
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 {
newcap = doublecap
} else {
for newcap < cap {
newcap += newcap / 4
}
}
}
// ……
capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)
}
看到了吗?如果只看前半部分,现在网上各种文章里说的 newcap
的规律是对的。现实是,后半部分还对 newcap
作了一个内存对齐
,这个和内存分配策略相关。进行内存对齐之后,新 slice 的容量是要 大于等于
老 slice 容量的 2倍
或者1.25倍
。
之后,向 Go 内存管理器申请内存,将老 slice 中的数据复制过去,并且将 append 的元素添加到新的底层数组中。
最后,向 growslice
函数调用者返回一个新的 slice,这个 slice 的长度并没有变化,而容量却增大了。
关于 append
,我们最后来看一个例子,来源于参考资料部分的【Golang Slice的扩容规则】。
package main
import "fmt"
func main() {
s := []int{1,2}
s = append(s,4,5,6)
fmt.Printf("len=%d, cap=%d",len(s),cap(s))
}
运行结果是:
len=5, cap=6
如果按网上各种文章中总结的那样:小于原 slice 长度小于 1024 的时候,容量每次增加 1 倍。添加元素 4 的时候,容量变为4;添加元素 5 的时候不变;添加元素 6 的时候容量增加 1 倍,变成 8。
那上面代码的运行结果就是:
len=5, cap=8
这是错误的!我们来仔细看看,为什么会这样,再次搬出代码:
// go 1.9.5 src/runtime/slice.go:82
func growslice(et *_type, old slice, cap int) slice {
// ……
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
// ……
}
// ……
capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)
}
这个函数的参数依次是 元素的类型,老的 slice,新 slice 最小求的容量
。
例子中 s
原来只有 2 个元素,len
和 cap
都为 2,append
了三个元素后,长度变为 3,容量最小要变成 5,即调用 growslice
函数时,传入的第三个参数应该为 5。即 cap=5
。而一方面,doublecap
是原 slice
容量的 2 倍,等于 4。满足第一个 if
条件,所以 newcap
变成了 5。
接着调用了 roundupsize
函数,传入 40。(代码中ptrSize是指一个指针的大小,在64位机上是8)
我们再看内存对齐,搬出 roundupsize
函数的代码:
// src/runtime/msize.go:13
func roundupsize(size uintptr) uintptr {
if size < _MaxSmallSize {
if size <= smallSizeMax-8 {
return uintptr(c