Go slice 擴容機制分析
前言
我們都知道 Go 語言中的 slice 具有動態擴容的機制（不知道的同學請先補課 Go 切片)
但是其底層機制是什麼呢？本著知其然，知其所以然的探索精神去研究一番。還不是為了應試 手動狗頭
go version go1.15.6 windows/amd64
擴容
既然是八股文，哪就先說結論，切片的擴容分兩步：預估擴容後的容量，確定記憶體佔用後得到最終的容量
下文給出了一個例子，讀者可以先猜測一下結果，帶著問題尋找答案。不然上來就看源碼分析，還不得暈
s := []int32{1, 2}
s = append(s, 3, 4, 5)
fmt.Printf("len=%d, cap=%d", len(s), cap(s))
預估容量
刪除一些邊界檢查，溢出檢查，基於 cap 的預估演算法非常簡單
// src/runtime/slice.go
/*
參數分析：
old 是老切片
cap 是新切片容量的最小值（即舊切片的容量加上新加入元素的數量），上面的例子中，cap 值為 5（2+3=5）
*/
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 { // 如果舊切片長度小於 1024，則新容量為舊切片容量的 2 倍
newcap = doublecap
} else {
for newcap < cap {
newcap += newcap / 4 // 每次增長 25%，直到大於最小值
}
}
}
}
按照這種演算法，得出上個例子新切片的容量為 5（3+2 大於 2*2）
記憶體佔用
記憶體佔用 = 元素個數 * 元素類型大小。
不過，由於 Go 語言的記憶體分配是由其 runtime 來管理的，程式並不是直接和作業系統打交道。
在程式啟動時，runtime 會提前向作業系統申請一批記憶體，按照不同的規格管理起來，如下所示（重點看 bytes/obj 這列）：
// src/runtime/sizeclasses.go
// Code generated by mksizeclasses.go; DO NOT EDIT.
//go:generate go run mksizeclasses.go
package runtime
// class bytes/obj bytes/span objects tail waste max waste
// 1 8 8192 1024 0 87.50%
// 2 16 8192 512 0 43.75%
// 3 32 8192 256 0 46.88%
// 4 48 8192 170 32 31.52%
// 5 64 8192 128 0 23.44%
// 6 80 8192 102 32 19.07%
// 7 96 8192 85 32 15.95%
// 8 112 8192 73 16 13.56%
// 9 128 8192 64 0 11.72%
// 10 144 8192 56 128 11.82%
// 11 160 8192 51 32 9.73%
// ......
當程式向 runtime 申請記憶體時，它會匹配足夠大，且最接近的規格
上例中，int32 佔用 4 byte，總記憶體佔用為 5 * 4=20 byte，則 runtime 實際分配的記憶體為 32 byte，最終的容量為 32 / 4（每個 int 32 佔用大小） = 8
練習
s := []int64{1, 2}
s = append(s, 3, 4, 5)
fmt.Printf("len=%d, cap=%d", len(s), cap(s))
-
2（老容量）+ 3（新添加的元素）= 5，超出 4 （老容量的兩倍），即預估容量為 5
-
int64 佔用 8 byte，總記憶體 5 * 8 = 40 byte，runtime 實際分配 48 byte，48 / 8 = 6
參考
slice類型存什麼？make和new？slice和數組？擴容規則？
