Go 語言切片擴容規則是擴容2倍？1.25倍？到底幾倍
切片，相信大家用了 Go 語言那么久這這種數據類型并不陌生，但是平日里聊到關于切片是如何擴容的，很多人可能會張口就來，切片擴容的時候，如果老切片的容量小于 1024 那么就再擴容 1倍，也就是新的切片容量是老切片容量的兩倍，同理，如果老切片容量大于 1024，那么就擴容1.25 倍
一個人這么說，多個人這么說，你可能就信了????，可是大家都這么認為，我們就應該盲從嗎？還是要自己去確認真實的擴容邏輯和實現方式，那就開始吧??
結論先行，切片對于擴容并不一定是 2 倍，1.25倍，這個要看實際情況
本文分別從如下幾點來聊聊切片的擴容
- 擴容是針對切片的，數組無法擴容
- 切片擴容到底是擴容到原來的幾倍？
- 我們一般使用切片的時候可以如何避免頻繁的擴容？
擴容是針對切片的，數組無法擴容
首先需要明確，數組是不能擴容的，數組定義的時候就已經是定長的了，無法擴容
切片是可以擴容的，我們可以通過 append 追加的方式來向已有的切片尾部進行追加，若原有切片已滿，那么就會發生擴容
另外，我們知道數組是一段連續的內存地址，同一種數據類型的數據集合，例如這樣
func main() {
log.SetFlags(log.Lshortfile)
var demoArray = [5]int{1, 2, 3, 4, 5}
log.Print("unsafe.sizeof(int) == ",unsafe.Sizeof(demoArray[0]))
for i, _ := range demoArray {
log.Printf("&demoAraay[%d] == %p", i, &demoArray[i])
}
}
圖片
可以看到在這個案例的環境中，一個 int 類型的變量占用 8 個字節，自然對于 demoArray 數組中，地址是連續的，每一個元素占用的空間也是我們所期望的
那么切片的數據地址也是連續的嗎？？
如果有人問這個問題，實際上是想問切片的底層數組的地址是不是也是連續的
我們知道，切片 slice 在 Go 中是一個結構體，其中 array 字段是一個指針，指向了一塊連續的內存地址，也就是底層數組
圖片
type slice struct {
array unsafe.Pointer
len int
cap int
}其中 len 字段記錄了當前底層數組的實際有的元素個數，cap 表示底層數組的容量，自然也是切片slice 的容量
func main(){
var demoSli = []int{1,2,3,4,5}
log.Printf("len == %d,cap == %d",len(demoSli),cap(demoSli))
for i, _ := range demoSli {
log.Printf("&demoSli[%d] == %p", i, &demoSli[i])
}
}
圖片
自然，demoSli 中的元素打印出來，地址也是連續的，沒有毛病
此處 xdm 模擬的時候，切勿去打印拷貝值的地址，例如下面這種方式是相當不明智的
圖片
現在簡單的去給 切片追加一個元素
圖片
可以看到切片的容量變成了原來的兩倍（容量從 5 擴容成 10），且切片中底層數組的元素地址自然也是連續的，不需要著急下結論，繼續往下看，好戲在后頭
切片擴容到底是擴容到原來的幾倍？
案例1 向一個cap 為 0 的切片中追加 2000 個元素，查看被擴容了幾次
圖片
總共是擴容了 14 次
可以看到切片容量小于 1024 時，觸發擴容都是擴容到原來的 2 倍，但是 大于 1024 之后，有的是 1.25 倍，有的是 1.35 倍，有的大于 1.35 倍，那么這是為什么呢？后面統一看源碼
案例2 再次驗證切片容量小于 1024，觸發到擴容就一定是擴容 2 倍嗎
- 先初始化一個切片，里面有 5 個元素，len 為 5，cap 為 5
- 再向切片中追加 6 個元素，分別是 6,7,8,9,10,11
- 最終查看切片的容量是多少
func main(){
var demoSli = []int{1, 2, 3, 4, 5}
log.Printf("len == %d,cap == %d", len(demoSli), cap(demoSli))
for i, _ := range demoSli {
log.Printf("&demoSli[%d] == %p", i, &demoSli[i])
}
demoSli = append(demoSli,6,7,8,9,10,11)
log.Printf("len == %d,cap == %d",len(demoSli),cap(demoSli))
for i, _ := range demoSli {
log.Printf("&demoSli[%d] == %p", i, &demoSli[i])
}
}通過這一段代碼，我們可以看到，講一個 len 為 5，cap 為 5 的切片，追加數字 6 的時候，切片應該要擴容到 10，然后追加到數字 11 的時候，切片應該擴容到 20，可實際真的是這樣嗎？
圖片
xdm 可以將上述 demo 貼到自己環境試試，得到的結果仍然會是切片的容量 cap 最終是 12，并不是 20
那么這一切都是為什么呢？我們來查看源碼一探究竟
源碼賞析
查看公共庫中 runtime/slice.go 的 growslice 函數就可以解開我們的疑惑
圖片
可以看出在我們使用 append 對切片追加元素的時候，實際上會調用到 growslice 函數， growslice 中的核心邏輯我們就可以理解為計算基本的 newcap 和進行字節對齊
- 進行基本的新切片容量計算
// 省略部分
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.cap < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
// 省略部分此處邏輯可以知道
- 如果當前傳入的 cap 是比原有切片 cap 的 2 倍還要大，那么就會按照當前傳入的 cap 來作為新切片的容量
- 否則去校驗原有切片的容量是否小于 1024
若小于 1024 ，則按照原有的切片容量的 2 倍進行擴容
若大于等于 1024 ，那么就按照原有切片的 1.25 倍繼續擴容
然后是否看到這里就就結束了呢？就下定論來呢？并不，我們切莫斷章取義，需要看全整個流程
- 進行基本的字節對齊
growslice 函數 計算出基本的 newcap 之后，還需要按照類型進行基本的字節對齊，此處字節對齊之后主要是 roundupsize 的函數實現，順便將其涉及到的常量放到一起給大家展示一波
const (
_MaxSmallSize = 32768
smallSizeDiv = 8
smallSizeMax = 1024
largeSizeDiv = 128
_NumSizeClasses = 68
_PageShift = 13
)
func roundupsize(size uintptr) uintptr {
if size < _MaxSmallSize {
if size <= smallSizeMax-8 {
return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
} else {
return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
}
}
if size+ _PageSize < size {
return size
}
return alignUp(size, _PageSize)
}
func divRoundUp(n, a uintptr) uintptr {
// a is generally a power of two. This will get inlined and
// the compiler will optimize the division.
return (n + a - 1) / a
}
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, ...}光看這個函數，沒啥感覺，函數邏輯比較簡單，就是基本的計算和索引，那么我們講上述的案例2帶入，來計算一下
圖片
此處很明確，當前舊的切片的 cap 為 5
也就是 growslice 函數 中 old.cap 為 5，傳入的 cap 為 11，因此 cap > 2*old.cap
因此 newcap 此處等于 11
圖片
開始計算字節對齊之后的結果
- roundupsize(uintptr(newcap) * sys.PtrSize) ，其中 newcap = 11，sys.PtrSize = 8，則 roundupsize 參數傳入 88 ，此環境指針占用 8 字節
- 按照如下邏輯進行計算
divRoundUp(88, 8) = 11
size_to_class8[11] = 8
class_to_size[8] = 96
此處環境我們的 int 類型是占用 8 個字節，因此最終的 newcap = 96/8 = 12
圖片
經過上述源碼的處理，最終我們就可以正常的得到最終切片容量被擴容到 12 ，xdm 可以去看實際的源碼
小結
使用 append 進行切片擴容的時候，先會按照基本的邏輯來計算 newcap 的大小
- 如果當前傳入的cap是比原有切片cap的2倍還要大，那么就會按照當前傳入的cap來作為新切片的容量，否則去校驗原有切片的容量是否小于 1024
- 若小于1024，則按照原有的切片容量的2倍進行擴容
- 若大于等于 1024，那么就按照原有切片的 1.25 倍繼續擴容最終再進行字節對齊
那么實際上，最終的切片容量一般是會等于或者大于原有的 2倍 或者是 1.25 倍的
我們一般使用切片的時候可以如何避免頻繁的擴容？
一般在使用切片的時候，盡量避免頻繁的去擴容，我們可以對已知數據量的數據，進行一次性去分配切片的容量
例如，數據量有 1000 個，那么我們就可以使用 make 的方式來進行初始化
sli := make([]int, 0, 1000)本次就是這樣，如果對源碼還挺感興趣的話，xdm 可以去實際查看一下源碼哦，希望對你有幫助
