Go 语言切片如何扩容？（全面解析原理和过程）
一、结构介绍
切片（Slice）在 Go 语言中，有一个很常用的数据结构，切片是一个拥有相同类型元素的可变长度的序列，它是基于数组类型做的一层封装。它非常灵活，支持自动扩容。并发不安全。
切片是一种引用类型，它有三个属性：指针，长度和容量。
底层源码定义：
type slice struct { array unsafe.Pointer len int cap int }
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
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
大致规则如下：
其中,当扩容前容量 >= 256时，会按照公式进行扩容
newcap += (newcap + 3*threshold) / 4
这样得到的预估容量并不是最终结果，还有内存对齐，进一步调整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)
举例：
还是上面的例子：
nums := []int{1, 2} nums = append(nums, 2, 3, 4) fmt.Printf("len:%v cap:%v", len(nums), cap(nums))
按照上述策略的结果，应该是 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) }
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
