Go 语言切片如何扩容？（全面解析原理和过程）

Go 语言切片如何扩容？（全面解析原理和过程）

一、结构介绍

切片（Slice）在 Go 语言中，有一个很常用的数据结构，切片是一个拥有相同类型元素的可变长度的序列，它是基于数组类型做的一层封装。它非常灵活，支持自动扩容。并发不安全。
切片是一种引用类型，它有三个属性：指针，长度和容量。

底层源码定义：

type slice struct { array unsafe.Pointer len int cap int }

• 1
• 2
• 3
• 4
• 5

1.指针： 指向 slice 可以访问到的第一个元素。
2.长度： slice 中元素个数。
3.容量： slice 起始元素到底层数组最后一个元素间的元素个数。

比如使用 make([]byte, 5) 创建一个切片，它看起来是这样的：

二、扩容时机与过程

Go 中切片的扩容机制是基于动态数组的，这意味着切片的底层数组会动态调整大小以适应元素的增加。下面是 Go 切片扩容的一般过程：

1.初始分配：

当使用 make 创建一个切片时，Go 会为其分配一块初始的底层数组，并将切片的长度和容量都设置为相同的值。

2.追加元素：

当你使用 append 向切片追加元素时，Go 会检查是否有足够的容量来容纳新的元素。如果有足够的容量，新元素会被添加到底层数组的末尾，切片的长度会增加。如果没有足够的容量，就需要进行扩容。

3.扩容：

当切片需要扩容时，Go 会创建一个新的更大的底层数组（具体的扩容策略看下面扩容原理）。然后，原数组的元素会被复制到新数组中，新元素会被添加到新数组的末尾。最后，切片的引用会指向新的底层数组，原数组会被垃圾回收。
这个扩容的过程保证了在大多数情况下，append 操作都是高效的。由于每次扩容都会涉及元素的复制，因此在涉及大量元素的情况下可能会导致一些性能开销。如果你知道切片需要存储的元素数量，可以使用 make 函数make([]T, length, capacity)的第三个参数显式指定容量，以减少扩容的次数。

三、扩容原理

Go1.18之前切片的扩容是以容量1024为临界点，当旧容量 < 1024个元素,扩容变成2倍；当旧容量 > 1024个元素，那么会进入一个循环，每次增加25%直到大于期望容量。
然而这个扩容机制已经被Go 1.18弃用了，官方说新的扩容机制能更平滑地过渡。
具体扩容原理分别如下：

Go 1.18版本 之前扩容原理

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；
2. 如果当前切片的长度小于 1024 就会将容量翻倍；
3. 如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

注：解释一下第一条：
比如 nums := []int{1, 2} nums = append(nums, 2, 3, 4)，这样期望容量为2+3 = 5，而5 > 2*2，故使用期望容量（这只是不考虑内存对齐的情况下）

记录容量变化如下：

[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

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

Go 1.18版本 之后扩容原理

和之前版本的区别，主要在扩容阈值，以及这行源码：newcap += (newcap + 3*threshold) / 4。

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；
2. 如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
3. 如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；

记录容量变化如下：

[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 = 848 [0 -> 847] cap = 848 | after append 848 cap = 1280 [0 -> 1279] cap = 1280 | after append 1280 cap = 1792 [0 -> 1791] cap = 1792 | after append 1792 cap = 2560

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

大致规则如下：

其中,当扩容前容量 >= 256时，会按照公式进行扩容

newcap += (newcap + 3*threshold) / 4

• 1

这样得到的预估容量并不是最终结果，还有内存对齐，进一步调整newcap

在1.18中，优化了切片扩容的策略，让底层数组大小的增长更加平滑：通过减小阈值并固定增加一个常数，使得优化后的扩容的系数在阈值前后不再会出现从2到1.25的突变，该commit作者给出了几种原始容量下对应的“扩容系数”：

oldcap	扩容系数
256	2.0
512	1.63
1024	1.44
2048	1.35
4096	1.30

可以看到，Go1.18的扩容策略中，随着容量的增大，其扩容系数是越来越小的，可以更好地节省内存。

可以试着求一个极限，当oldcap远大于256的时候，扩容系数将会变成1.25。

四、内存对齐

扩容之后的容量并不是严格按照这个策略的。那是为什么呢？

实际上，growslice​ 的后半部分还有更进一步的优化（内存对齐等），靠的是 roundupsize​ 函数，在计算完 newcap 值之后，还会有一个步骤计算最终的容量：

capmem = roundupsize(uintptr(newcap) * ptrSize) newcap = int(capmem / ptrSize)

• 1
• 2

举例：
还是上面的例子：

nums := []int{1, 2} nums = append(nums, 2, 3, 4) fmt.Printf("len:%v cap:%v", len(nums), cap(nums))

• 1
• 2
• 3

按照上述策略的结果，应该是 len:5，cap:5。但是最终结果为 len:5，cap:6
解释：容量计算完了后还要考虑到内存的高效利用，进行内存对齐，则会调用这个函数 roundupsize 。（具体可以看源码）

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 { return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]]) } } if size+_PageSize < size { return size } return alignUp(size, _PageSize) }

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

size 表示新切片需要的内存大小 我们传入的 int 类型，每个占用 8 字节 (可以调用 unsafe.Sizeof() 函数查看占用的大小)，一共 5 个 所以是 40，size 小于_MaxSmallSize 并且小于 smallSizeMax-8 ，那么使用通用公式 (size+smallSizeDiv-1)/smallSizeDiv 计算得到 5，然后到 size_to_class8 找到第五号元素 为 4，再从 class_to_size 找到 第四号元素 为 48，这就是新切片占用的内存大小，每个 int 占用 8 字节，所以最终切片的容量为 6 。所以说切片的扩容有它基本的扩容规则，在规则之后还要考虑内存对齐，这就代表不同数据类型的切片扩容的容量大小是会不一致。

五、总结

切片扩容通常是在进行切片的 append​ 操作时触发的。在进行 append​ 操作时，如果切片容量不足以容纳新的元素，就需要对切片进行扩容，此时就会调用 growslice 函数进行扩容。
切片扩容分两个阶段，分为 go1.18 之前和之后：

一、go1.18 之前：

1.如果期望容量大于当前容量的两倍就会使用期望容量；
2.如果当前切片的长度小于 1024 就会将容量翻倍；
3.如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

二、go1.18 之后：

1.如果期望容量大于当前容量的两倍就会使用期望容量；
2.如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
3.如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；

总的来说，Go的设计者不断优化切片扩容的机制，其目的只有一个：就是控制让小的切片容量增长速度快一点，减少内存分配次数，而让大切片容量增长率小一点，更好地节省内存。

• 如果只选择翻倍的扩容策略，那么对于较大的切片来说，现有的方法可以更好的节省内存。
• 如果只选择每次系数为1.25的扩容策略，那么对于较小的切片来说扩容会很低效。
• 之所以选择一个小于2的系数，在扩容时被释放的内存块会在下一次扩容时更容易被重新利用。

参考文章：
https://juejin.cn/post/7101928883280150558
https://www.51cto.com/article/750934.html
https://yufengbiji.com/posts/golang-slice

注：微信公众号搜 ：飞川撸码