append函数的使用方法,all函数的使用方法

8个月前 (04-23)

一般都是在向 slice 追加了元素之后，才会引起扩容。追加元素调用的是 append 函数。

先来看看 append 函数的原型：

func ? append(slice []Type, elems ...Type) []Type

append 函数的参数长度可变，因此可以追加多个值到 slice 中，还可以用 ... 传入 slice，直接追加一个切片。

1 ? ? 2

slice = append(slice, elem1, elem2) ? ? slice = append(slice, anotherSlice...)

append函数返回值是一个新的slice，Go编译器不允许调用了 append 函数后不使用返回值。

1 ? ? 2

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倍。

我在这里先说结论：以上描述是错误的。

为了说明上面的规律是错误的，我写了一小段玩具代码：

?1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?5 ? ? ?6 ? ? ?7 ? ? ?8 ? ? ?9 ? ? 10 ? ? 11 ? ? 12 ? ? 13 ? ? 14 ? ? 15 ? ? 16 ? ? 17 ? ? 18 ? ? 19 ? ? 20

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 -> M] cap = %-4d? |? ? after append %-4d? cap = ? %-4d\", 0, i-1, oldCap, i, ? newCap) ? ? ??????????????????????? oldCap = ? newCap ? ? ??????????????? } ? ? ??????? } ? ? }

我先创建了一个空的 slice，然后，在一个循环里不断往里面 append 新的元素。然后记录容量的变化，并且每当容量发生变化的时候，记录下老的容量，以及添加完元素之后的容量，同时记下此时 slice 里的元素。这样，我就可以观察，新老 slice 的容量变化情况，从而找出规律。

运行结果：

?1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?5 ? ? ?6 ? ? ?7 ? ? ?8 ? ? ?9 ? ? 10 ? ? 11 ? ? 12 ? ? 13 ? ? 14

[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 函数，所以我们直接看它的代码。

?1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?5 ? ? ?6 ? ? ?7 ? ? ?8 ? ? ?9 ? ? 10 ? ? 11 ? ? 12 ? ? 13 ? ? 14 ? ? 15 ? ? 16 ? ? 17 ? ? 18 ? ? 19 ? ? 20 ? ? 21

// 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】

?1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?5 ? ? ?6 ? ? ?7 ? ? ?8 ? ? ?9 ? ? 10 ? ? 11 ? ? 12

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】

1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? 8 ? ? 9

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

这是错误的！我们来仔细看看，为什么会这样，再次搬出代码：

?1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?5 ? ? ?6 ? ? ?7 ? ? ?8 ? ? ?9 ? ? 10 ? ? 11 ? ? 12 ? ? 13 ? ? 14 ? ? 15

// 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 函数的代码：

?1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?5 ? ? ?6 ? ? ?7 ? ? ?8 ? ? ?9 ? ? 10 ? ? 11 ? ? 12 ? ? 13 ? ? 14 ? ? 15

// src/runtime/msize.go:13 ? ? func roundupsize(size uintptr) uintptr { ? ? ??????? if ? size < _MaxSmallSize { ? ? ??????????????? if ? size <= allSizeMax-8 { ? ? ??????????????????????? return ? uintptr(class_to_size[size_to_class8[(size+allSizeDiv-1)/allSizeDiv]]) ? ? ??????????????? } else ? { ? ? ??????????????????????? //…… ? ? ??????????????? } ? ? ??????? } ? ? ??? //…… ? ? }

const ? _MaxSmallSize = 32768 ? ? const allSizeMax = 1024 ? ? const allSizeDiv = 8

很明显，我们最终将返回这个式子的结果：

class_to_size[size_to_class8[(size+allSizeDiv-1)/allSizeDiv]]

这是 Go 源码中有关内存分配的两个 slice。class_to_size通过 spanClass获取 span划分的 object大小。而 size_to_class8 表示通过 size 获取它的 spanClass。

1 ? ? 2 ? ? 3

var ? size_to_class8 = [allSizeMax/allSizeDiv + 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+allSizeDiv-1)/allSizeDiv = 5；获取 size_to_class8 数组中索引为 5 的元素为 4；获取 class_to_size 中索引为 4 的元素为 48。

最终，新的 slice 的容量为 6：

newcap = int(capmem / ptrSize) // 6

于，上面的两个魔法数组的由来，就不展开了。

【引申2】向一个nil的slice添加元素会发生什么？为什么？

其实 nil slice 或者 empty slice 都是可以通过调用 append 函数来获得底层数组的扩容。最终都是调用 mallocgc 来向 Go 的内存管理器申请到一块内存，然后再赋给原来的nil slice 或 empty slice，然后摇身一变，成为“真正”的 slice 了。

app