切片扩容机制

2024-03-23 2025-05-14 约 2400 字预计阅读 5 分钟 - 次阅读 - 条评论

切片定义

slice源代码定义：

1
2
3
4
5


type slice struct {
	array unsafe.Pointer //指向底层数组的指针
	len   int            //切片长度
	cap   int            //切片容量
}

如果仅仅是提供通过下标值来操作元素的类数组操作接口，那么切片也不会在 Go 中占据重要的位置。Go 切片还支持一个重要的高级特性：动态扩容。我们提到过切片类型是部分满足零值可用理念的，即零值切片也可以通过 append 预定义函数进行元素赋值操作：

1
2


var s []byte // s被赋予零值nil
s = append(s, 1)

由于初值为零值，s 这个描述符并没有绑定对应的底层数组。而经过 append 操作后，s 显然已经绑定了属于它的底层数组。

切片扩容案例

为了方便查看切片是如何动态扩容的，我们打印出每次 append 操作后切片 s 的 len 和 cap 值：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


var s [] int  //s 被赋予零值 nil
s = append (s, 11)
fmt.Println (len (s), cap (s)) //1 1
s = append (s, 12)
fmt.Println (len (s), cap (s)) //2 2
s = append (s, 13)
fmt.Println (len (s), cap (s)) //3 4
s = append (s, 14)
fmt.Println (len (s), cap (s)) //4 4
s = append (s, 15)
fmt.Println (len (s), cap (s)) //5 8

我们看到切片 s 的 len 值是线性增长的，但 cap 值却呈现出不规则的变化。通过下图，我们更容易看清楚多次 append 操作究竟是如何让切片进行动态扩容的。

我们看到 append 会根据切片对底层数组容量的需求对底层数组进行动态调整。

1）最初 s 初值为零值（nil），此时 s 没有绑定底层数组。

2）通过 append 操作向切片 s 添加一个元素 11，此时 append 会首先分配底层数组 u1（数组长度 1），然后将 s 内部表示中的 array 指向 u1，并设置 len = 1，cap =1。

3）通过 append 操作向切片 s 再添加一个元素 12，此时 len (s) = 1，cap (s) = 1，append 判断底层数组剩余空间不满足添加新元素的要求，于是创建了一个新的底层数组 u2，长度为 2（u1 数组长度的 2 倍），并将 u1 中的元素复制到 u2 中，最后将 s 内部表示中的 array 指向 u2，并设置 len = 2，cap = 2。

4）通过 append 操作向切片 s 再添加一个元素 13，此时 len (s) = 2，cap (s) = 2，append 判断底层数组剩余空间不满足添加新元素的要求，于是创建了一个新的底层数组 u3，长度为 4（u2 数组长度的 2 倍），并将 u2 中的元素复制到 u3 中，最后将 s 内部表示中的 array 指向 u3，并设置 len = 3，cap 为 u3 数组长度，即 4。

5）通过 append 操作向切片 s 再添加一个元素 14，此时 len (s) = 3，cap (s) = 4，append 判断底层数组剩余空间满足添加新元素的要求，于是将 14 放在下一个元素的位置（数组 u3 末尾），并将 s 内部表示中的 len 加 1，变为 4。

6）通过 append 操作向切片 s 添加最后一个元素 15，此时 len (s) = 4，cap (s) = 4，append 判断底层数组剩余空间不满足添加新元素的要求，于是创建了一个新的底层数组 u4，长度为 8（u3 数组长度的 2 倍），并将 u3 中的元素复制到 u4 中，最后将 s 内部表示中的 array 指向 u4，并设置 len = 5，cap 为 u4 数组长度，即 8。

我们看到 append 会根据切片的需要，在当前底层数组容量无法满足的情况下，动态分配新的数组，新数组长度会按一定算法扩展（参见 $GOROOT/src/runtime/slice.go 中的 growslice 函数）。新数组建立后，append 会把旧数组中的数据复制到新数组中，之后新数组便成为切片的底层数组，旧数组后续会被垃圾回收掉。这样的 append 操作有时会给 Gopher 带来一些困惑，比如通过语法 u [low: high] 形式进行数组切片化而创建的切片，一旦切片 cap 触碰到数组的上界，再对切片进行 append 操作，切片就会和原数组解除绑定：

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


func main () {
    u := [] int {11, 12, 13, 14, 15}
    fmt.Println ("array:", u) // [11, 12, 13, 14, 15]
    s := u [1:3]
    fmt.Printf ("slice (len=% d, cap=% d): % v\n", len (s), cap (s), s) // [12, 13]
    s = append (s, 24)
    fmt.Println ("after append 24, array:", u)
    fmt.Printf ("after append 24, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)
    s = append (s, 25)
    fmt.Println ("after append 25, array:", u)
    fmt.Printf ("after append 25, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)
    s = append (s, 26)
    fmt.Println ("after append 26, array:", u)
    fmt.Printf ("after append 26, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)

    s [0] = 22
    fmt.Println ("after reassign 1st elem of slice, array:", u)
    fmt.Printf ("after reassign 1st elem of slice, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)
}

运行这段代码，得到如下结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


$go run slice_unbind_orig_array.go
array: [11 12 13 14 15]
slice (len=2, cap=4): [12 13]
after append 24, array: [11 12 13 24 15]
after append 24, slice (len=3, cap=4): [12 13 24]
after append 25, array: [11 12 13 24 25]
after append 25, slice (len=4, cap=4): [12 13 24 25]
after append 26, array: [11 12 13 24 25]
after append 26, slice (len=5, cap=8): [12 13 24 25 26]
after reassign 1st elem of slice, array: [11 12 13 24 25]
after reassign 1st elem of slice, slice (len=5, cap=8): [22 13 24 25 26]

我们看到在添加元素 25 之后，切片的元素已经触碰到底层数组 u 的边界；此后再添加元素 26，append 发现底层数组已经无法满足添加新元素的要求，于是新创建了一个底层数组（数组长度为 cap (s) 的 2 倍，即 8），并将原切片的元素复制到新数组中。在这之后，即便再修改切片中的元素值，原数组 u 的元素也没有发生任何改变，因为此时切片 s 与数组 u 已经解除了绑定关系，s 已经不再是数组 u 的描述符了。

扩容源代码

growslice函数部分源代码：

（此为1.18版本之后）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
	// 前面代码省略...
	newcap := old.cap
	doublecap := newcap + newcap //双倍扩容（原容量的两倍）
	if cap > doublecap {         //如果所需容量大于 两倍扩容，则直接扩容到所需容量
		newcap = cap
	} else {
		const threshold = 256    //这里设置了一个 阈值 -- 256
		if old.cap < threshold { //如果旧容量 小于 256，则两倍扩容
			newcap = doublecap
		} else {
			// 检查 0 < newcap 以检测溢出并防止无限循环。
			for 0 < newcap && newcap < cap { //如果新容量 > 0 并且 原容量 小于 所需容量
				// 从小片的增长2x过渡到大片的增长1.25x。这个公式给出了两者之间的平滑过渡。(这里的系数会随着容量的大小发生变化，从2.0到无线接近1.25)
				newcap += (newcap + 3*threshold) / 4

				//当newcap计算溢出时，将newcap设置为请求的上限。
				if newcap <= 0 { // 如果发生了溢出，将新容量设置为请求的容量大小
					newcap = cap
				}
			}
		}
		// 后面代码省略...
		return slice{p, newLen, newcap}
	}
}

扩容规则如下：

如果请求容量大于两倍现有容量，则新容量直接为请求容量。
否则（请求容量小于等于两倍现有容量）
- 如果现有容量小于 256 ，则新容量是原来的两倍；
- 否则：新容量 = 1.25 原容量 + 3/4 阈值 “这个公式给出了从1.25倍增长过渡到2 倍增长，两者之间的平滑过渡。” 在此情况下，如果发生了溢出，将新容量设置为请求的容量大小。