# 切片的容量是怎样增长的 一般都是在向 slice 追加了元素之后，才会引起扩容。追加元素调用的是 `append` 函数。 先来看看 `append` 函数的原型： ```go func append(slice []Type, elems ...Type) []Type ``` append 函数的参数长度可变，因此可以追加多个值到 slice 中，还可以用 `...` 传入 slice，直接追加一个切片。 ```go slice = append(slice, elem1, elem2) slice = append(slice, anotherSlice...) ``` `append`函数返回值是一个新的slice，Go编译器不允许调用了 append 函数后不使用返回值。 ```go append(slice, elem1, elem2) append(slice, anotherSlice...) ``` 所以上面的用法是错的，不能编译通过。 使用 append 可以向 slice 追加元素，实际上是往底层数组添加元素。但是底层数组的长度是固定的，如果索引 `len-1` 所指向的元素已经是底层数组的最后一个元素，就没法再添加了。 这时，slice 会迁移到新的内存位置，新底层数组的长度也会增加，这样就可以放置新增的元素。同时，为了应对未来可能再次发生的 append 操作，新的底层数组的长度，也就是新 `slice` 的容量是留了一定的 `buffer` 的。否则，每次添加元素的时候，都会发生迁移，成本太高。 新 slice 预留的 `buffer` 大小是有一定规律的。网上大多数的文章都是这样描述的： > 当原 slice 容量小于 `1024` 的时候，新 slice 容量变成原来的 `2` 倍；原 slice 容量超过 `1024`，新 slice 容量变成原来的`1.25`倍。 我在这里先说结论：以上描述是错误的。 为了说明上面的规律是错误的，我写了一小段玩具代码： ```go 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 // 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 的长度并没有变化，而容量却增大了。 【引申1】 来看一个例子，来源于[这里](https://jiajunhuang.com/articles/2017_07_18-golang_slice.md.html) ```go package main import "fmt" func main() { s := []int{5} s = append(s, 7) s = append(s, 9) x := append(s, 11) y := append(s, 12) fmt.Println(s, x, y) } ``` | 代码 | 切片对应状态 | | ------------------ | ----------------------------------------------------------------------------------------------------------------------------------- | | s := \[]int{5} | s 只有一个元素，`[5]` | | s = append(s, 7) | s 扩容，容量变为2，`[5, 7]` | | s = append(s, 9) | s 扩容，容量变为4，`[5, 7, 9]`。注意，这时 s 长度是3，只有3个元素 | | x := append(s, 11) | 由于 s 的底层数组仍然有空间，因此并不会扩容。这样，底层数组就变成了 `[5, 7, 9, 11]`。注意，此时 s = `[5, 7, 9]`，容量为4；x = `[5, 7, 9, 11]`，容量为4。这里 s 不变 | | y := append(s, 12) | 这里还是在 s 元素的尾部追加元素，由于 s 的长度为3，容量为4，所以直接在底层数组索引为3的地方填上12。结果：s = `[5, 7, 9]`，y = `[5, 7, 9, 12]`，x = `[5, 7, 9, 12]`，x，y 的长度均为4，容量也均为4 | 所以最后程序的执行结果是： ``` [5 7 9] [5 7 9 12] [5 7 9 12] ``` 这里要注意的是，append函数执行完后，返回的是一个全新的 slice，并且对传入的 slice 并不影响。 【引申2】 关于 `append`，我们最后来看一个例子，来源于 [Golang Slice的扩容规则](https://jodezer.github.io/2017/05/golangSlice%E7%9A%84%E6%89%A9%E5%AE%B9%E8%A7%84%E5%88%99)。 ```go 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 // 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` 了三个元素后，长度变为 5，容量最小要变成 5，即调用 `growslice` 函数时，传入的第三个参数应该为 5。即 `cap=5`。而一方面，`doublecap` 是原 `slice`容量的 2 倍，等于 4。满足第一个 `if` 条件，所以 `newcap` 变成了 5。 接着调用了 `roundupsize` 函数，传入 40。（代码中ptrSize是指一个指针的大小，在64位机上是8） 我们再看内存对齐，搬出 `roundupsize` 函数的代码： ```go // src/runtime/msize.go:13 func roundupsize(size uintptr) uintptr { if size < _MaxSmallSize { if size <= smallSizeMax-8 { return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]]) } else { //…… } } //…… } const _MaxSmallSize = 32768 const smallSizeMax = 1024 const smallSizeDiv = 8 ``` 很明显，我们最终将返回这个式子的结果： ```go class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]] ``` 这是 `Go` 源码中有关内存分配的两个 `slice`。`class_to_size`通过 `spanClass`获取 `span`划分的 `object`大小。而 `size_to_class8` 表示通过 `size` 获取它的 `spanClass`。 ```go var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 3, 4, 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, 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, 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, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31} var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 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} ``` 我们传进去的 `size` 等于 40。所以 `(size+smallSizeDiv-1)/smallSizeDiv = 5`；获取 `size_to_class8` 数组中索引为 `5` 的元素为 `4`；获取 `class_to_size` 中索引为 `4` 的元素为 `48`。 最终，新的 slice 的容量为 `6`： ```go newcap = int(capmem / ptrSize) // 6 ``` 至于，上面的两个`魔法数组`的由来，就不展开了。 【引申2】 向一个nil的slice添加元素会发生什么？为什么？ 其实 `nil slice` 或者 `empty slice` 都是可以通过调用 append 函数来获得底层数组的扩容。最终都是调用 `mallocgc` 来向 Go 的内存管理器申请到一块内存，然后再赋给原来的`nil slice` 或 `empty slice`，然后摇身一变，成为“真正”的 `slice` 了。