前情提要
最近在复习Golang的切片知识，在网上看大佬们的博客讲解，自己在本地测试发现和博客讲的对不上。
自己查阅源码后，发现是Golang版本不同，每个版本对切片扩容机制的实现也不同。
因此保存一篇博客来记录Golang切片的扩容机制，以及如何阅读这部分源码。
尽管之后版本变动，也可以再通过源码的方式来进行查证。
注明：
本博客只是提供一种了解Golang切片扩容机制的方式，仅供参考。
因为不同版本下扩容机制的实现可能不同，小伙伴如果想要了解自己Go版本的切片扩容机制，也可以参考下本博客的方式。
源码分析
Golang源码版本：1.19.5，mac的arm架构。源码下载链接：https://go.dev/dl/
切片本身具有3个基本要素：指向底层数组元素的指针、长度len、容量cap。
切片在append过程中，如果len > cap，就会触发扩容机制。
切片扩容机制相关的源码都位于go/src/runtime包下，切片在触发扩容后会调用runtime.growslice函数。
growslice函数的扩容机制主要代码如下：
func growslice(et *_type, old slice, cap int) slice {
...
newcap := old.cap
doublecap := newcap + newcap
// 如果期望容量 > 当前容量的2倍，扩容到期望容量
if cap > doublecap {
newcap = cap
} else { // 期望容量 <= 当前容量的2倍
const threshold = 256
// 如果当前容量 < 256，容量翻倍
if old.cap < threshold {
newcap = doublecap
} else { // 如果当前容量 >= 256
// 循环扩容，初始值为当前容量，每次扩容为上次的25%，外加256*3/4=192，直到新容量 >= 期望容量
for 0 < newcap && newcap < cap {
newcap += (newcap + 3*threshold) / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
...
}
这里的参数cap看作期望容量，可以理解为append后的元素个数，也就是扩容后的切片长度，期望能够有的容量。
上述代码只会确定切片的大致容量，还需要根据切片中的元素类型大小对齐内存，这部分代码也在growslice函数中。
growslice函数的扩容后内存对齐机制主要代码如下：
func growslice(et *_type, old slice, cap int) slice {
...
var overflow bool
var lenmem, newlenmem, capmem uintptr
switch {
case et.size == 1:
...
case et.size == goarch.PtrSize: // 元素类型大小为8字节
lenmem = uintptr(old.len) * goarch.PtrSize
newlenmem = uintptr(cap) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap) * goarch.PtrSize) // 内存对齐，获取对齐后真正要申请的内存大小
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize) // 内存对齐后计算真正的扩容后容量
case isPowerOfTwo(et.size):
...
default:
...
}
...
}
为了方便，这里只考虑切片元素类型为int64的内存对齐机制。
内存对齐时会调用runtime.roundupsize函数对内存进行向上取整，获取对齐后要申请的内存大小，计算出真正扩容后的容量。
roundupsize函数的内存对齐机制代码如下：
func roundupsize(size uintptr) uintptr {
if size < _MaxSmallSize { // size < 32768，即扩容后容量 < 4096，需要根据class_to_size数组来对内存向上取整
if size <= smallSizeMax-8 { // size <= 1024 - 8，即扩容后容量 <= 127
// size_to_class8数组用来获取class_to_size数组的索引
// divRoundUp(size, smallSizeDiv)，相当于计算ceil(size / 8)
return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
} else { // size > 1024 - 8，即扩容后容量 > 127
// size_to_class128数组用来获取class_to_size数组的索引
// divRoundUp(size-smallSizeMax, largeSizeDiv)，相当于计算ceil((size - 1024) / 128)
return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
}
}
if size+_PageSize < size { // size + 8192 < size，抱歉这块代码没看懂
return size
}
return alignUp(size, _PageSize) // 向上对齐，alignUp(size, 8192)
}
简单理解为：
（1）扩容后容量 < 4096时，需要根据class_to_size数组来对内存向上取整。
class_to_size数组声明代码如下：
var class_to_size = [_NumSizeClasses]uint16{
0, 8, 16, 24, 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,
}
向上取整的含义：在class_to_size数组中找到所有大于等于"对齐前size"值中最小的值。比如对齐前size为120，对齐后变为128
（2）扩容后容量 >= 4096时，需要根据runtime.alignUp函数来对内存向上取整
alignUp函数代码如下：
func alignUp(n, a uintptr) uintptr {
return (n + a - 1) &^ (a - 1)
}
扩容过程总结
切片在append的过程中，当len > cap时，会触发切片的扩容机制。
扩容时会分配一个容量更大的底层数组，并把原来切片的元素复制到新底层数组中，再添加新元素进去。
扩容机制分为两部分：计算新容量（确定大致容量）、内存对齐（获取真实的扩容后容量）。
计算新容量
期望容量可以理解为append后的元素个数，也就是扩容后的切片长度，期望能够有的容量。
（1）如果期望容量 > 当前容量的2倍，扩容到期望容量，否则走（2）和（3）
（2）如果当前容量 < 256，容量翻倍
（3）如果当前容量 >= 256，循环扩容直到新容量 >= 期望容量。初始值为当前容量，每次扩容为上次的25%，外加256*3/4=192
内存对齐
为了方便，这里只考虑切片元素类型为int64的内存对齐机制。
（1）扩容后容量 < 4096时，需要根据class_to_size数组来对内存向上取整。
class_to_size数组如下：
var class_to_size = [_NumSizeClasses]uint16{
0, 8, 16, 24, 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,
}
向上取整的含义：在class_to_size数组中找到所有大于等于"对齐前size"值中最小的值。比如对齐前size为120，对齐后变为128
（2）扩容后容量 >= 4096时，需要根据runtime.alignUp函数来对内存向上取整，实际为alignUp(n, 8192)
为了方便，省略掉参数a（已知为8192），alignUp函数代码可改写为：
func alignUp(n int64) int64 {
return (n + 8192 - 1) &^ (8292 - 1)
}
这里记录几组值，后面会用到：
alignUp(35616) = 40960，换算容量为5120
alignUp(52736) = 57344，换算容量为7168
alignUp(73216) = 73728，换算容量为9216
alignUp(93696) = 98304，换算容量为12288
代码验证
以int64元素类型的切片为例，记录切片长度从0扩容增长到10000的过程中所有的容量大小变化。
根据上述源码分析，整个扩容过程可以分为3个不同的阶段：
（1）当前容量 < 256（扩容后容量 < 4096，必定）
（2）当前容量 >= 256 && 扩容后容量 < 4096
（3）扩容后容量 >= 4096
测试代码如下：
func main() {
numbers := make([]int64, 0)
count := int64(0)
oldCap := cap(numbers)
for {
count++
// 记录每次刚刚发生扩容时的len和cap
if cap(numbers) != oldCap {
fmt.Printf("len = %d, cap = %d\n", len(numbers), cap(numbers))
}
oldCap = cap(numbers)
numbers = append(numbers, count)
if count > 10000 {
break
}
}
}
// 方便观察验证
var class_to_size = [_NumSizeClasses]uint16{
0, 8, 16, 24, 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,
}
func alignUp(n int64) int64 {
return (n + 8192 - 1) &^ (8292 - 1)
}
输出结果如下
len = 1, cap = 1
len = 2, cap = 2
len = 3, cap = 4
len = 5, cap = 8
len = 9, cap = 16
len = 17, cap = 32
len = 33, cap = 64
len = 65, cap = 128
len = 129, cap = 256
len = 257, cap = 512
len = 513, cap = 848
len = 849, cap = 1280
len = 1281, cap = 1792
len = 1793, cap = 2560
len = 2561, cap = 3408
len = 3409, cap = 5120
len = 5121, cap = 7168
len = 7169, cap = 9216
len = 9217, cap = 12288
把输出结果分为3个阶段。
1、第1部分为当前容量 < 256（扩容后容量 < 4096，必定），分析如下：
// 扩容前len=1，cap=0，期望容量为1 > 当前容量0的2倍，扩容到期望容量1
// 期望分配的内存为8字节，class_to_size数组对齐内存后依然为8字节，扩容后容量为1
len = 1, cap = 1
// 扩容前len=2，cap=1，期望容量为2 <= 当前容量1的2倍，当前容量为1 < 256，容量翻倍，扩容到容量为2
// 期望分配的内存为16字节，class_to_size数组对齐内存后依然为16字节，扩容后容量为2
len = 2, cap = 2
// 扩容前len=3，cap=2，期望容量为3 <= 当前容量2的2倍，当前容量为2 < 256，容量翻倍，扩容到容量为4
// 期望分配的内存为32字节，class_to_size数组对齐内存后依然为32字节，扩容后容量为4
len = 3, cap = 4
// 扩容前len=5，cap=4，期望容量为5 <= 当前容量4的2倍，当前容量为4 < 256，容量翻倍，扩容到容量为8
// 期望分配的内存为64字节，class_to_size数组对齐内存后依然为64字节，扩容后容量为8
len = 5, cap = 8
// 扩容前len=9，cap=8，期望容量为9 <= 当前容量8的2倍，当前容量为8 < 256，容量翻倍，扩容到容量为16
// 期望分配的内存为128字节，class_to_size数组对齐内存后依然为128字节，扩容后容量为16
len = 9, cap = 16
// 扩容前len=17，cap=16，期望容量为17 <= 当前容量16的2倍，当前容量为16 < 256，容量翻倍，扩容到容量为32
// 期望分配的内存为256字节，class_to_size数组对齐内存后依然为256字节，扩容后容量为32
len = 17, cap = 32
// 扩容前len=33，cap=32，期望容量为33 <= 当前容量32的2倍，当前容量为32 < 256，容量翻倍，扩容到容量为64
// 期望分配的内存为512字节，class_to_size数组对齐内存后依然为512字节，扩容后容量为64
len = 33, cap = 64
// 扩容前len=65，cap=64，期望容量为65 <= 当前容量64的2倍，当前容量为64 < 256，容量翻倍，扩容到容量为128
// 期望分配的内存为1024字节，class_to_size数组对齐内存后依然为1024字节，扩容后容量为128
len = 65, cap = 128
// 扩容前len=129，cap=128，期望容量为129 <= 当前容量128的2倍，当前容量为128 < 256，容量翻倍，扩容到容量为256
// 期望分配的内存为2048字节，class_to_size数组对齐内存后依然为2048字节，扩容后容量为256
len = 129, cap = 256
2、第2部分为当前容量 >= 256 && 扩容后容量 < 4096，分析如下：
// 扩容前len=257，cap=256，期望容量为257 <= 当前容量256的2倍
// 当前容量为256 >= 256，每次扩容25%外加192，直到512 >= 期望容量257，扩容到容量为512
// 期望分配的内存为4096字节，class_to_size数组对齐内存后依然为4096字节，扩容后容量为512
len = 257, cap = 512
// 扩容前len=513，cap=512，期望容量为513 <= 当前容量512的2倍
// 当前容量为512 >= 256，每次扩容25%外加192，直到832 >= 期望容量513，扩容到容量为832
// 期望分配的内存为6656字节，class_to_size数组对齐内存后为6784字节，扩容后容量为848
len = 513, cap = 848
// 扩容前len=849，cap=848，期望容量为849 <= 当前容量848的2倍
// 当前容量为848 >= 256，每次扩容25%外加192，直到1252 >= 期望容量849，扩容到容量为1252
// 期望分配的内存为10016字节，class_to_size数组对齐内存后为10240字节，扩容后容量为1280
len = 849, cap = 1280
// 扩容前len=1281，cap=1280，期望容量为1281 <= 当前容量1280的2倍
// 当前容量为1280 >= 256，每次扩容25%外加192，直到1792 >= 期望容量1281，扩容到容量为1792
// 期望分配的内存为14336字节，class_to_size数组对齐内存后依然为14336字节，扩容后容量为1792
len = 1281, cap = 1792
// 扩容前len=1793，cap=1792，期望容量为1793 <= 当前容量1792的2倍
// 当前容量为1792 >= 256，每次扩容25%外加192，直到2432 >= 期望容量1793，扩容到容量为2432
// 期望分配的内存为19456字节，class_to_size数组对齐内存后为20480字节，扩容后容量为2560
len = 1793, cap = 2560
// 扩容前len=2561，cap=2560，期望容量为2561 <= 当前容量2560的2倍
// 当前容量为2560 >= 256，每次扩容25%外加192，直到3392 >= 期望容量2561，扩容到容量为3392
// 期望分配的内存为27136字节，class_to_size数组对齐内存后为27264字节，扩容后容量为3408
len = 2561, cap = 3408
3、第3部分为扩容后容量 >= 4096，分析如下：
// 扩容前len=3409，cap=3408，期望容量为3409 <= 当前容量3408的2倍
// 当前容量为3408 >= 256，每次扩容25%外加192，直到4452 >= 期望容量3409，扩容到容量为4452
// 期望分配的内存为35616字节，alignUp(35616)对齐内存后为40960字节，扩容后容量为5120
len = 3409, cap = 5120
// 扩容前len=5121，cap=5120，期望容量为5121 <= 当前容量5120的2倍
// 当前容量为5120 >= 256，每次扩容25%外加192，直到6592 >= 期望容量5121，扩容到容量为6592
// 期望分配的内存为52736字节，alignUp(52736)对齐内存后为57344字节，扩容后容量为7168
len = 5121, cap = 7168
// 扩容前len=7169，cap=7168，期望容量为7169 <= 当前容量7168的2倍
// 当前容量为7168 >= 256，每次扩容25%外加192，直到9152 >= 期望容量7169，扩容到容量为9152
// 期望分配的内存为73216字节，alignUp(73216)对齐内存后为73728字节，扩容后容量为9216
len = 7169, cap = 9216
// 扩容前len=9217，cap=9216，期望容量为9217 <= 当前容量9216的2倍
// 当前容量为9216 >= 256，每次扩容25%外加192，直到11712 >= 期望容量9217，扩容到容量为11712
// 期望分配的内存为93696字节，alignUp(93696)对齐内存后为98304字节，扩容后容量为12288
len = 9217, cap = 12288
谢谢大家～，喜欢本篇文章的话，记得收藏加关注！！！