在《切片傳遞的隱藏危機(jī)》一文中芯急，小菜刀有簡(jiǎn)單地提及到切片擴(kuò)容的問(wèn)題。在讀者討論群中驶俊，有人舉了以下例子娶耍，想得到一個(gè)合理的回答。
package main
func main() {
s := []int{1,2}
s = append(s, 3,4,5)
println(cap(s))
}
// output: 6
為什么結(jié)果不是5饼酿，不是8榕酒，而是6呢？由于小菜刀在該文中關(guān)于擴(kuò)容的描述不夠準(zhǔn)確故俐，讓讀者產(chǎn)生了疑惑奈应。因此本文想借此機(jī)會(huì)細(xì)致分析一下append函數(shù)及其背后的擴(kuò)容機(jī)制。
我們知道购披，append是一種用戶在使用時(shí)杖挣，并不需要引入相關(guān)包而可直接調(diào)用的函數(shù)。它是內(nèi)置函數(shù)刚陡，其定義位于源碼包 builtin 的builtin.go惩妇。
// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
// slice = append(slice, elem1, elem2)
// slice = append(slice, anotherSlice...)
// As a special case, it is legal to append a string to a byte slice, like this:
// slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type
append 會(huì)追加一個(gè)或多個(gè)數(shù)據(jù)至 slice 中，這些數(shù)據(jù)會(huì)存儲(chǔ)至 slice 的底層數(shù)組筐乳。其中歌殃，數(shù)組長(zhǎng)度是固定的，如果數(shù)組的剩余空間足以容納追加的數(shù)據(jù)蝙云，則可以正常地將數(shù)據(jù)存入該數(shù)組氓皱。一旦追加數(shù)據(jù)后總長(zhǎng)度超過(guò)原數(shù)組長(zhǎng)度，原數(shù)組就無(wú)法滿足存儲(chǔ)追加數(shù)據(jù)的要求勃刨。此時(shí)會(huì)怎么處理呢波材？
同時(shí)我們發(fā)現(xiàn)，該文件中僅僅定義了函數(shù)簽名身隐，并沒有包含函數(shù)實(shí)現(xiàn)的任何代碼廷区。這里我們不免好奇，append究竟是如何實(shí)現(xiàn)的呢贾铝？
編譯過(guò)程
為了回答上述問(wèn)題隙轻，我們不妨從編譯入手。Go編譯可分為四個(gè)階段：詞法與語(yǔ)法分析垢揩、類型檢查與抽象語(yǔ)法樹（AST）轉(zhuǎn)換玖绿、中間代碼生成和生成最后的機(jī)器碼。
我們主要需要關(guān)注的是編譯期第二和第三階段的代碼叁巨，分別是位于src/cmd/compile/internal/gc/typecheck.go下的類型檢查邏輯
func typecheck1(n *Node, top int) (res *Node) {
...
switch n.Op {
case OAPPEND:
...
}
位于src/cmd/compile/internal/gc/walk.go下的抽象語(yǔ)法樹轉(zhuǎn)換邏輯
func walkexpr(n *Node, init *Nodes) *Node {
...
case OAPPEND:
// x = append(...)
r := n.Right
if r.Type.Elem().NotInHeap() {
yyerror("%v can't be allocated in Go; it is incomplete (or unallocatable)", r.Type.Elem())
}
switch {
case isAppendOfMake(r):
// x = append(y, make([]T, y)...)
r = extendslice(r, init)
case r.IsDDD():
r = appendslice(r, init) // also works for append(slice, string).
default:
r = walkappend(r, init, n)
}
...
}
和位于src/cmd/compile/internal/gc/ssa.go下的中間代碼生成邏輯
// append converts an OAPPEND node to SSA.
// If inplace is false, it converts the OAPPEND expression n to an ssa.Value,
// adds it to s, and returns the Value.
// If inplace is true, it writes the result of the OAPPEND expression n
// back to the slice being appended to, and returns nil.
// inplace MUST be set to false if the slice can be SSA'd.
func (s *state) append(n *Node, inplace bool) *ssa.Value {
...
}
其中斑匪，中間代碼生成階段的state.append方法，是我們重點(diǎn)關(guān)注的地方俘种。入?yún)?inplace 代表返回值是否覆蓋原變量秤标。如果為false绝淡，展開邏輯如下（注意：以下代碼只是為了方便理解的偽代碼宙刘，并不是 state.append 中實(shí)際的代碼）苍姜。同時(shí)，小菜刀注意到如果寫成 append(s, e1, e2, e3) 不帶接收者的形式悬包，并不能通過(guò)編譯衙猪，所以暫未明白它的場(chǎng)景在哪。
// If inplace is false, process as expression "append(s, e1, e2, e3)":
ptr, len, cap := s
newlen := len + 3
if newlen > cap {
ptr, len, cap = growslice(s, newlen)
newlen = len + 3 // recalculate to avoid a spill
}
// with write barriers, if needed:
*(ptr+len) = e1
*(ptr+len+1) = e2
*(ptr+len+2) = e3
return makeslice(ptr, newlen, cap)
如果是true布近，例如 slice = append(slice, 1, 2, 3) 語(yǔ)句垫释，那么返回值會(huì)覆蓋原變量。展開方式邏輯如下
// If inplace is true, process as statement "s = append(s, e1, e2, e3)":
a := &s
ptr, len, cap := s
newlen := len + 3
if uint(newlen) > uint(cap) {
newptr, len, newcap = growslice(ptr, len, cap, newlen)
vardef(a) // if necessary, advise liveness we are writing a new a
*a.cap = newcap // write before ptr to avoid a spill
*a.ptr = newptr // with write barrier
}
newlen = len + 3 // recalculate to avoid a spill
*a.len = newlen
// with write barriers, if needed:
*(ptr+len) = e1
*(ptr+len+1) = e2
*(ptr+len+2) = e3
不管 inpalce 是否為true撑瞧，我們均會(huì)獲取切片的數(shù)組指針棵譬、大小和容量，如果在追加元素后预伺，切片新的大小大于原始容量订咸，就會(huì)調(diào)用 runtime.growslice 對(duì)切片進(jìn)行擴(kuò)容，并將新的元素依次加入切片酬诀。
因此脏嚷，通過(guò)append向元素類型為 int 的切片（已包含元素 1，2瞒御，3）追加元素 1父叙， slice=append(slice,1)可分為兩種情況。
情況1肴裙，切片的底層數(shù)組還有可容納追加元素的空間趾唱。
情況2，切片的底層數(shù)組已無(wú)可容納追加元素的空間蜻懦，需調(diào)用擴(kuò)容函數(shù)鲸匿，進(jìn)行擴(kuò)容。
擴(kuò)容函數(shù)
前面我們提到阻肩，追加操作時(shí)带欢，當(dāng)切片底層數(shù)組的剩余空間不足以容納追加的元素，就會(huì)調(diào)用 growslice烤惊，其調(diào)用的入?yún)?cap 為追加元素后切片的總長(zhǎng)度乔煞。
growslice 的代碼較長(zhǎng)，我們可以根據(jù)邏輯分為三個(gè)部分柒室。
- 初步確定切片容量
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 {
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
}
}
}
...
}
在該環(huán)節(jié)中渡贾，如果需要的容量 cap 超過(guò)原切片容量的兩倍 doublecap，會(huì)直接使用需要的容量作為新容量newcap雄右。否則空骚，當(dāng)原切片長(zhǎng)度小于1024時(shí)纺讲，新切片的容量會(huì)直接翻倍。而當(dāng)原切片的容量大于等于1024時(shí)囤屹，會(huì)反復(fù)地增加25%熬甚，直到新容量超過(guò)所需要的容量。
- 計(jì)算容量所需內(nèi)存大小
var overflow bool var lenmem, newlenmem, capmem uintptr switch { case et.size == 1: lenmem = uintptr(old.len) newlenmem = uintptr(cap) capmem = roundupsize(uintptr(newcap)) overflow = uintptr(newcap) > maxAlloc newcap = int(capmem) case et.size == sys.PtrSize: lenmem = uintptr(old.len) * sys.PtrSize newlenmem = uintptr(cap) * sys.PtrSize capmem = roundupsize(uintptr(newcap) * sys.PtrSize) overflow = uintptr(newcap) > maxAlloc/sys.PtrSize newcap = int(capmem / sys.PtrSize) case isPowerOfTwo(et.size): var shift uintptr if sys.PtrSize == 8 { // Mask shift for better code generation. shift = uintptr(sys.Ctz64(uint64(et.size))) & 63 } else { shift = uintptr(sys.Ctz32(uint32(et.size))) & 31 } lenmem = uintptr(old.len) << shift newlenmem = uintptr(cap) << shift capmem = roundupsize(uintptr(newcap) << shift) overflow = uintptr(newcap) > (maxAlloc >> shift) newcap = int(capmem >> shift) default: lenmem = uintptr(old.len) * et.size newlenmem = uintptr(cap) * et.size capmem, overflow = math.MulUintptr(et.size, uintptr(newcap)) capmem = roundupsize(capmem) newcap = int(capmem / et.size) }
在該環(huán)節(jié)肋坚，通過(guò)判斷切片元素的字節(jié)大小是否為1乡括，系統(tǒng)指針大小（32位為4智厌，64位為8）或2的倍數(shù)诲泌，進(jìn)入相應(yīng)所需內(nèi)存大小的計(jì)算邏輯。
這里需要注意的是 roundupsize 函數(shù)铣鹏，它根據(jù)輸入期望大小 size 敷扫，返回 mallocgc 實(shí)際將分配的內(nèi)存塊的大小。
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)]]) } } // Go的內(nèi)存管理虛擬地址頁(yè)大小為 8k（_PageSize） // 當(dāng)size的大小即將溢出時(shí)诚卸，就不采用向上取整的做法葵第，直接用當(dāng)前期望size值。 if size+_PageSize < size { return size } return alignUp(size, _PageSize)}
根據(jù)內(nèi)存分配中的大小對(duì)象原則惨险，如果期望分配內(nèi)存非大對(duì)象 ( <_MaxSmallSize )羹幸，即小于32k，則需要根據(jù) divRoundUp 函數(shù)將待申請(qǐng)的內(nèi)存向上取整辫愉，取整時(shí)會(huì)使用 class_to_size 以及 size_to_class8 和 size_to_class128 數(shù)組栅受。這些數(shù)組方便于內(nèi)存分配器進(jìn)行分配，以提高分配效率并減少內(nèi)存碎片恭朗。
// _NumSizeClasses = 67 代表67種特定大小的對(duì)象類型var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112,...}
當(dāng)期望分配內(nèi)存為大對(duì)象時(shí)屏镊，會(huì)通過(guò) alignUp 將該 size 的大小向上取值為虛擬頁(yè)大小（_PageSize）的倍數(shù)痰腮。
- 內(nèi)存分配
if overflow || capmem > maxAlloc { panic(errorString("growslice: cap out of range")) } var p unsafe.Pointer if et.ptrdata == 0 { p = mallocgc(capmem, nil, false) memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { p = mallocgc(capmem, et, true) if lenmem > 0 && writeBarrier.enabled { bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata) } } memmove(p, old.array, lenmem) return slice{p, old.len, newcap}
如果在第二個(gè)環(huán)節(jié)中而芥，造成了溢出或者期望分配的內(nèi)存超過(guò)最大分配限制，會(huì)引起 panic膀值。
mallocgc 分配一個(gè)大小為前面計(jì)算得到的 capmem 對(duì)象棍丐。如果是小對(duì)象，則直接從當(dāng)前G所在P的緩存空閑列表中分配沧踏；如果是大對(duì)象歌逢，則從堆上進(jìn)行分配。同時(shí)翘狱，如果切片中的元素不是指針類型秘案，那么會(huì)調(diào)用 memclrNoHeapPointers將超出切片當(dāng)前長(zhǎng)度的位置清空；如果是元素是指針類型，且原有切片元素個(gè)數(shù)不為0 并可以打開寫屏障時(shí)阱高，需要調(diào)用 bulkBarrierPreWriteSrcOnly 將舊切片指針標(biāo)記隱藏赚导，在新切片中保存為nil指針。
在最后使用memmove將原數(shù)組內(nèi)存中的內(nèi)容拷貝到新申請(qǐng)的內(nèi)存中赤惊，并將新的內(nèi)存指向指針p 和舊的長(zhǎng)度值吼旧，新的容量值賦值給新的 slice 并返回。
注意荐捻，在 growslice 完成后黍少，只是把舊有數(shù)據(jù)拷貝到了新的內(nèi)存中去寡夹，且計(jì)算得到新的 slice 容量大小处面，并沒有完成最終追加數(shù)據(jù)的操作。如果 slice 當(dāng)前 len =3菩掏，cap=3魂角，slice=append(slice,1)，那它完成的工作如下圖所示智绸。
growslice之后野揪，此時(shí)新的slice已經(jīng)拷貝了舊的slice數(shù)據(jù)，并且其底層數(shù)組有充足的剩余空間追加數(shù)據(jù)瞧栗。后續(xù)只需拷貝追加數(shù)據(jù)至剩余空間斯稳，并修改 len 值即可，這一部分就不再深究了迹恐。
總結(jié)
這里回到文章開頭中的例子
package mainfunc main() { s := []int{1,2} s = append(s, 3,4,5) println(cap(s))}
由于初始 s 的容量是2挣惰，現(xiàn)需要追加3個(gè)元素，所以通過(guò) append 一定會(huì)觸發(fā)擴(kuò)容殴边，并調(diào)用 growslice 函數(shù)憎茂，此時(shí)他的入?yún)?cap 大小為2+3=5。通過(guò)翻倍原有容量得到 doublecap = 2+2锤岸，doublecap 小于 cap 值竖幔，所以在第一階段計(jì)算出的期望容量值 newcap=5。在第二階段中是偷，元素類型大小 int 和 sys.PtrSize 相等拳氢，通過(guò) roundupsize 向上取整內(nèi)存的大小到 capmem = 48 字節(jié)，所以新切片的容量newcap 為 48 / 8 = 6 蛋铆，成功解釋馋评！
在切片 append 操作時(shí)，如果底層數(shù)組已無(wú)可容納追加元素的空間戒职，則需擴(kuò)容栗恩。擴(kuò)容并不是在原有底層數(shù)組的基礎(chǔ)上增加內(nèi)存空間，而是新分配一塊內(nèi)存空間作為切片的底層數(shù)組，并將原有數(shù)據(jù)和追加數(shù)據(jù)拷貝至新的內(nèi)存空間中磕秤。
在擴(kuò)容的容量確定上乳乌，相對(duì)比較復(fù)雜，它與CPU位數(shù)市咆、元素大小汉操、是否包含指針、追加個(gè)數(shù)等都有關(guān)系蒙兰。當(dāng)我們看完擴(kuò)容源碼邏輯后磷瘤，發(fā)現(xiàn)去糾結(jié)它的擴(kuò)容確切值并沒什么必要。
在實(shí)際使用中搜变，如果能夠確定切片的容量范圍采缚，比較合適的做法是：切片初始化時(shí)就分配足夠的容量空間，在append追加操作時(shí)挠他，就不用再考慮擴(kuò)容帶來(lái)的性能損耗問(wèn)題扳抽。
func BenchmarkAppendFixCap(b *testing.B) { for i := 0; i < b.N; i++ { a := make([]int, 0, 1000) for i := 0; i < 1000; i++ { a = append(a, i) } }}func BenchmarkAppend(b *testing.B) { for i := 0; i < b.N; i++ { a := make([]int, 0) for i := 0; i < 1000; i++ { a = append(a, i) } }}
它們的壓測(cè)結(jié)果如下，孰優(yōu)孰劣殖侵，一目了然贸呢。
$ go test -bench=. -benchmem
BenchmarkAppendFixCap-8 1953373 617 ns/op 0 B/op 0 allocs/op
BenchmarkAppend-8 426882 2832 ns/op 16376 B/op 11 allocs/op
