golang slice append 後 capacity 增長的演算法
一道題目：
append函式
函式定義： func append(slice []Type, elems ...Type) []Type
函式說明：內建函式append追加一個或多個elems到一個slice依賴的array的末尾，如果這個slice有足夠的capacity，則reslice以容納新增元素；如果capacity空間不夠，則重新分配記憶體儲存新的slice依賴的array，函式返回更新後的slice.(slice是引用，array儲存真正的資料，slice切片理解： https://blog.haohtml.com/arch...
注意：append不會修改傳參進來的slice(len和cap)，只會在不夠用的時候新分配一個array，並把之前的slice依賴的array資料拷貝過來；所以對同一個slice 重複 append，只要不超過cap，都是修改的同一個array，後面的會覆蓋前面
capacity如何增長?
圖片裡提到"Capacity grows in a way not related to the size of appending data"，那麼，增長演算法是什麼樣的呢?看原始碼 src/runtime/slice.go:
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 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
}
}
}
- 先將舊的slice容量乘以2，如果乘以2後的容量仍小於新的slice容量，則取新的slice容量(append多個elems)
- 如果新slice小於等於舊slice容量的2倍，則取舊slice容量乘以2
- 如果舊的slice容量大於1024，則新slice容量取舊slice容量乘以1.25
程式碼後面還會對newcap進行roundup，比如在64位平臺，newcap是奇數的話就會+1
回頭看題
package main
import (
"fmt"
)
func main(){
a := []int{1,2}
b := append(a,3)
fmt.Printf("cap(a)=%v,cap(b)=%v\n",cap(a),cap(b))
c := append(b,4)
d := append(b,5)
fmt.Printf("cap(a)=%v,cap(b)=%v\n",cap(a),cap(b))
fmt.Println(a,b,c,d)
fmt.Printf("%p,%p,%p,%p\n",a,b,c,d)
}
第一次append，超出了a的cap範圍，分配一個新的newcap為oldcap*2的array，即4；a不變
第二次append，len(b)是3，cap(b)是4，沒有超出b的cap範圍，b所依賴的array在len(b)的位置追加4，c共用這個array；b不變
第三次append，由於b沒有變化，b所依賴的array在len(b)的位置追加5，會覆蓋上一步的4
所以：c[3]和d[3]引用的是同一塊記憶體，都是5
另外，如果 d:= append(c,5) 則結果就是 c[3]=4,d[3]=4,d[4]=5因為這一步會新分配array,並將c的資料拷貝過來
總結
寫得比較匆忙，如有紕漏，歡迎指正。