Go 語(yǔ)言切片是如何擴(kuò)容的?
在 Go 語(yǔ)言中,有一個(gè)很常用的數(shù)據(jù)結(jié)構(gòu),那就是切片(Slice)。
切片是一個(gè)擁有相同類(lèi)型元素的可變長(zhǎng)度的序列,它是基于數(shù)組類(lèi)型做的一層封裝。它非常靈活,支持自動(dòng)擴(kuò)容。
切片是一種引用類(lèi)型,它有三個(gè)屬性:指針,長(zhǎng)度和容量。
底層源碼定義如下:
- 指針: 指向 slice 可以訪(fǎng)問(wèn)到的第一個(gè)元素。
- 長(zhǎng)度: slice 中元素個(gè)數(shù)。
- 容量: slice 起始元素到底層數(shù)組最后一個(gè)元素間的元素個(gè)數(shù)。
比如使用 make([]byte, 5) 創(chuàng)建一個(gè)切片,它看起來(lái)是這樣的:
聲明和初始化
切片的使用還是比較簡(jiǎn)單的,這里舉一個(gè)例子,直接看代碼吧。
擴(kuò)容時(shí)機(jī)
當(dāng)切片的長(zhǎng)度超過(guò)其容量時(shí),切片會(huì)自動(dòng)擴(kuò)容。這通常發(fā)生在使用 append 函數(shù)向切片中添加元素時(shí)。
擴(kuò)容時(shí),Go 運(yùn)行時(shí)會(huì)分配一個(gè)新的底層數(shù)組,并將原始切片中的元素復(fù)制到新數(shù)組中。然后,原始切片將指向新數(shù)組,并更新其長(zhǎng)度和容量。
需要注意的是,由于擴(kuò)容會(huì)分配新數(shù)組并復(fù)制元素,因此可能會(huì)影響性能。如果你知道要添加多少元素,可以使用 make 函數(shù)預(yù)先分配足夠大的切片來(lái)避免頻繁擴(kuò)容。
接下來(lái)看看 append 函數(shù),簽名如下:
append 函數(shù)參數(shù)長(zhǎng)度可變,可以追加多個(gè)值,還可以直接追加一個(gè)切片。使用起來(lái)比較簡(jiǎn)單,分別看兩個(gè)例子:
追加多個(gè)值:
輸出結(jié)果為:
再來(lái)看一下直接追加一個(gè)切片:
輸出結(jié)果為:
再來(lái)看一個(gè)發(fā)生擴(kuò)容的例子:
輸出結(jié)果為:
在這個(gè)例子中,我們創(chuàng)建了一個(gè)長(zhǎng)度為 0?,容量為 3? 的切片。然后,我們使用 append? 函數(shù)向切片中添加 5 個(gè)元素。
當(dāng)我們添加第 4? 個(gè)元素時(shí),切片的長(zhǎng)度超過(guò)了其容量。此時(shí),切片會(huì)自動(dòng)擴(kuò)容。新的容量是原始容量的兩倍,即 6。
表面現(xiàn)象已經(jīng)看到了,接下來(lái),我們就深入到源碼層面,看看切片的擴(kuò)容機(jī)制到底是什么樣的。
源碼分析
在 Go 語(yǔ)言的源碼中,切片擴(kuò)容通常是在進(jìn)行切片的 append? 操作時(shí)觸發(fā)的。在進(jìn)行 append? 操作時(shí),如果切片容量不足以容納新的元素,就需要對(duì)切片進(jìn)行擴(kuò)容,此時(shí)就會(huì)調(diào)用 growslice 函數(shù)進(jìn)行擴(kuò)容。
growslice? 函數(shù)定義在 Go 語(yǔ)言的 runtime 包中,它的調(diào)用是在編譯后的代碼中實(shí)現(xiàn)的。具體來(lái)說(shuō),當(dāng)執(zhí)行 append 操作時(shí),編譯器會(huì)將其轉(zhuǎn)換為類(lèi)似下面的代碼:
在上述代碼中,如果切片容量不足以容納新的元素,則會(huì)調(diào)用 growslice? 函數(shù)進(jìn)行擴(kuò)容。所以 growslice 函數(shù)的調(diào)用是由編譯器在生成的機(jī)器碼中實(shí)現(xiàn)的,而不是在源代碼中顯式調(diào)用的。
切片擴(kuò)容策略有兩個(gè)階段,go1.18 之前和之后是不同的,這一點(diǎn)在 go1.18 的 release notes 中有說(shuō)明。
下面我用 go1.17 和 go1.18 兩個(gè)版本來(lái)分開(kāi)說(shuō)明。先通過(guò)一段測(cè)試代碼,直觀感受一下兩個(gè)版本在擴(kuò)容上的區(qū)別。
上述代碼先創(chuàng)建了一個(gè)空的 slice,然后在一個(gè)循環(huán)里不斷往里面 append 新元素。
然后記錄容量的變化,每當(dāng)容量發(fā)生變化的時(shí)候,記錄下老的容量,添加的元素,以及添加完元素之后的容量。
這樣就可以觀察,新老 slice 的容量變化情況,從而找出規(guī)律。
運(yùn)行結(jié)果(1.17 版本):
運(yùn)行結(jié)果(1.18 版本):
根據(jù)上面的結(jié)果還是能看到區(qū)別的,具體擴(kuò)容策略下面邊看源碼邊說(shuō)明。
go1.17
擴(kuò)容調(diào)用的是 growslice 函數(shù),我復(fù)制了其中計(jì)算新容量部分的代碼。
在分配內(nèi)存空間之前需要先確定新的切片容量,運(yùn)行時(shí)根據(jù)切片的當(dāng)前容量選擇不同的策略進(jìn)行擴(kuò)容:
- 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
- 如果當(dāng)前切片的長(zhǎng)度小于 1024 就會(huì)將容量翻倍;
- 如果當(dāng)前切片的長(zhǎng)度大于等于 1024 就會(huì)每次增加 25% 的容量,直到新容量大于期望容量;
go1.18
和之前版本的區(qū)別,主要在擴(kuò)容閾值,以及這行代碼:newcap += (newcap + 3*threshold) / 4。
在分配內(nèi)存空間之前需要先確定新的切片容量,運(yùn)行時(shí)根據(jù)切片的當(dāng)前容量選擇不同的策略進(jìn)行擴(kuò)容:
- 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
- 如果當(dāng)前切片的長(zhǎng)度小于閾值(默認(rèn) 256)就會(huì)將容量翻倍;
- 如果當(dāng)前切片的長(zhǎng)度大于等于閾值(默認(rèn) 256),就會(huì)每次增加 25% 的容量,基準(zhǔn)是 newcap + 3*threshold,直到新容量大于期望容量;
內(nèi)存對(duì)齊
分析完兩個(gè)版本的擴(kuò)容策略之后,再看前面的那段測(cè)試代碼,就會(huì)發(fā)現(xiàn)擴(kuò)容之后的容量并不是嚴(yán)格按照這個(gè)策略的。
那是為什么呢?
實(shí)際上,growslice? 的后半部分還有更進(jìn)一步的優(yōu)化(內(nèi)存對(duì)齊等),靠的是 roundupsize? 函數(shù),在計(jì)算完 newcap 值之后,還會(huì)有一個(gè)步驟計(jì)算最終的容量:
這個(gè)函數(shù)的實(shí)現(xiàn)就不在這里深入了,先挖一個(gè)坑,以后再來(lái)補(bǔ)上。
總結(jié)
切片擴(kuò)容通常是在進(jìn)行切片的 append? 操作時(shí)觸發(fā)的。在進(jìn)行 append? 操作時(shí),如果切片容量不足以容納新的元素,就需要對(duì)切片進(jìn)行擴(kuò)容,此時(shí)就會(huì)調(diào)用 growslice 函數(shù)進(jìn)行擴(kuò)容。
切片擴(kuò)容分兩個(gè)階段,分為 go1.18 之前和之后:
一、go1.18 之前:
- 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
- 如果當(dāng)前切片的長(zhǎng)度小于 1024 就會(huì)將容量翻倍;
- 如果當(dāng)前切片的長(zhǎng)度大于 1024 就會(huì)每次增加 25% 的容量,直到新容量大于期望容量;
二、go1.18 之后:
- 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量;
- 如果當(dāng)前切片的長(zhǎng)度小于閾值(默認(rèn) 256)就會(huì)將容量翻倍;
- 如果當(dāng)前切片的長(zhǎng)度大于等于閾值(默認(rèn) 256),就會(huì)每次增加 25% 的容量,基準(zhǔn)是 newcap + 3*threshold,直到新容量大于期望容量;
以上就是本文的全部?jī)?nèi)容,如果覺(jué)得還不錯(cuò)的話(huà)歡迎點(diǎn)贊,轉(zhuǎn)發(fā)和關(guān)注,感謝支持。
參考文章:
- https://go.dev/doc/go1.18
- https://go.dev/blog/slices
- https://go.dev/blog/slices-intro
- https://golang.design/go-questions/slice/grow/
- https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-array-and-slice/