在 Go 語言中，有一個很常用的數(shù)據(jù)結(jié)構(gòu)，那就是切片（Slice）。

切片是一個擁有相同類型元素的可變長度的序列，它是基于數(shù)組類型做的一層封裝。它非常靈活，支持自動擴容。

切片是一種引用類型，它有三個屬性：指針，長度和容量。

底層源碼定義如下：

type?slice?struct?{
????array?unsafe.Pointer
????len???int
????cap???int
}

• 指針： 指向 slice 可以訪問到的第一個元素。
• 長度： slice 中元素個數(shù)。
• 容量： slice 起始元素到底層數(shù)組最后一個元素間的元素個數(shù)。

比如使用 make([]byte, 5) 創(chuàng)建一個切片，它看起來是這樣的：

聲明和初始化

切片的使用還是比較簡單的，這里舉一個例子，直接看代碼吧。

func?main()?{
????var?nums?[]int??//?聲明切片
????fmt.Println(len(nums),?cap(nums))?//?0?0
????nums?=?append(nums,?1)???//?初始化
????fmt.Println(len(nums),?cap(nums))?//?1?1

????nums1?:=?[]int{1,2,3,4}????//?聲明并初始化
????fmt.Println(len(nums1),?cap(nums1))????//?4?4

????nums2?:=?make([]int,3,5)???//?使用make()函數(shù)構(gòu)造切片
????fmt.Println(len(nums2),?cap(nums2))????//?3?5
}

擴容時機

當(dāng)切片的長度超過其容量時，切片會自動擴容。這通常發(fā)生在使用 append 函數(shù)向切片中添加元素時。

擴容時，Go 運行時會分配一個新的底層數(shù)組，并將原始切片中的元素復(fù)制到新數(shù)組中。然后，原始切片將指向新數(shù)組，并更新其長度和容量。

需要注意的是，由于擴容會分配新數(shù)組并復(fù)制元素，因此可能會影響性能。如果你知道要添加多少元素，可以使用 make 函數(shù)預(yù)先分配足夠大的切片來避免頻繁擴容。

接下來看看 append 函數(shù)，簽名如下：

func?Append(slice?[]int,?items?...int)?[]int

append 函數(shù)參數(shù)長度可變，可以追加多個值，還可以直接追加一個切片。使用起來比較簡單，分別看兩個例子：

追加多個值：

package?main

import?"fmt"

func?main()?{
????s?:=?[]int{1,?2,?3}
????fmt.Println("初始切片:",?s)

????s?=?append(s,?4,?5,?6)
????fmt.Println("追加多個值后的切片:",?s)
}

輸出結(jié)果為：

初始切片: [1 2 3]
追加多個值后的切片: [1 2 3 4 5 6]

再來看一下直接追加一個切片：

package?main

import?"fmt"

func?main()?{
????s1?:=?[]int{1,?2,?3}
????fmt.Println("初始切片:",?s1)

????s2?:=?[]int{4,?5,?6}
????s1?=?append(s1,?s2...)
????fmt.Println("追加另一個切片后的切片:",?s1)
}

輸出結(jié)果為：

初始切片: [1 2 3]
追加另一個切片后的切片: [1 2 3 4 5 6]

再來看一個發(fā)生擴容的例子：

package?main

import?"fmt"

func?main()?{
????s?:=?make([]int,?0,?3)?//?創(chuàng)建一個長度為0，容量為3的切片
????fmt.Printf("初始狀態(tài):?len=%d?cap=%d?%v\n",?len(s),?cap(s),?s)

????for?i?:=?1;?i?<=?5;?i++?{
????????s?=?append(s,?i)?//?向切片中添加元素
????????fmt.Printf("添加元素%d:?len=%d?cap=%d?%v\n",?i,?len(s),?cap(s),?s)
????}
}

輸出結(jié)果為：

初始狀態(tài): len=0 cap=3 []
添加元素1: len=1 cap=3 [1]
添加元素2: len=2 cap=3 [1 2]
添加元素3: len=3 cap=3 [1 2 3]
添加元素4: len=4 cap=6 [1 2 3 4]
添加元素5: len=5 cap=6 [1 2 3 4 5]

在這個例子中，我們創(chuàng)建了一個長度為 0，容量為 3 的切片。然后，我們使用 append 函數(shù)向切片中添加 5 個元素。

當(dāng)我們添加第 4 個元素時，切片的長度超過了其容量。此時，切片會自動擴容。新的容量是原始容量的兩倍，即 6。

表面現(xiàn)象已經(jīng)看到了，接下來，我們就深入到源碼層面，看看切片的擴容機制到底是什么樣的。

源碼分析

在 Go 語言的源碼中，切片擴容通常是在進行切片的 append 操作時觸發(fā)的。在進行 append 操作時，如果切片容量不足以容納新的元素，就需要對切片進行擴容，此時就會調(diào)用 growslice 函數(shù)進行擴容。

growslice 函數(shù)定義在 Go 語言的 runtime 包中，它的調(diào)用是在編譯后的代碼中實現(xiàn)的。具體來說，當(dāng)執(zhí)行 append 操作時，編譯器會將其轉(zhuǎn)換為類似下面的代碼：

slice?=?append(slice,?elem)

在上述代碼中，如果切片容量不足以容納新的元素，則會調(diào)用 growslice 函數(shù)進行擴容。所以 growslice 函數(shù)的調(diào)用是由編譯器在生成的機器碼中實現(xiàn)的，而不是在源代碼中顯式調(diào)用的。

切片擴容策略有兩個階段，go1.18 之前和之后是不同的，這一點在 go1.18 的 release notes 中有說明。

下面我用 go1.17 和 go1.18 兩個版本來分開說明。先通過一段測試代碼，直觀感受一下兩個版本在擴容上的區(qū)別。

package?main

import?"fmt"

func?main()?{
????s?:=?make([]int,?0)

????oldCap?:=?cap(s)

????for?i?:=?0;?i?<?2048;?i++?{
????????s?=?append(s,?i)

????????newCap?:=?cap(s)

????????if?newCap?!=?oldCap?{
????????????fmt.Printf("[%d?->?%4d]?cap?=?%-4d??|??after?append?%-4d??cap?=?%-4d\n",?0,?i-1,?oldCap,?i,?newCap)
????????????oldCap?=?newCap
????????}
????}
}

上述代碼先創(chuàng)建了一個空的 slice，然后在一個循環(huán)里不斷往里面 append 新元素。

然后記錄容量的變化，每當(dāng)容量發(fā)生變化的時候，記錄下老的容量，添加的元素，以及添加完元素之后的容量。

這樣就可以觀察，新老 slice 的容量變化情況，從而找出規(guī)律。

運行結(jié)果（1.17 版本）：

[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

運行結(jié)果（1.18 版本）：

[0 ->   -1] cap = 0     |  after append 0     cap = 1
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 848 
[0 ->  847] cap = 848   |  after append 848   cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1792
[0 -> 1791] cap = 1792  |  after append 1792  cap = 2560

根據(jù)上面的結(jié)果還是能看到區(qū)別的，具體擴容策略下面邊看源碼邊說明。

go1.17

擴容調(diào)用的是 growslice 函數(shù)，我復(fù)制了其中計算新容量部分的代碼。

//?src/runtime/slice.go

func?growslice(et?*_type,?old?slice,?cap?int)?slice?{
????//?...

????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
????????????}
????????}
????}

????//?...

????return?slice{p,?old.len,?newcap}
}

在分配內(nèi)存空間之前需要先確定新的切片容量，運行時根據(jù)切片的當(dāng)前容量選擇不同的策略進行擴容：

• 如果期望容量大于當(dāng)前容量的兩倍就會使用期望容量；
• 如果當(dāng)前切片的長度小于 1024 就會將容量翻倍；
• 如果當(dāng)前切片的長度大于等于 1024 就會每次增加 25% 的容量，直到新容量大于期望容量；

go1.18

//?src/runtime/slice.go

func?growslice(et?*_type,?old?slice,?cap?int)?slice?{
????//?...

????newcap?:=?old.cap
????doublecap?:=?newcap?+?newcap
????if?cap?>?doublecap?{
????????newcap?=?cap
????}?else?{
????????const?threshold?=?256
????????if?old.cap?<?threshold?{
????????????newcap?=?doublecap
????????}?else?{
????????????//?Check?0?<?newcap?to?detect?overflow
????????????//?and?prevent?an?infinite?loop.
????????????for?0?<?newcap?&&?newcap?<?cap?{
????????????????//?Transition?from?growing?2x?for?small?slices
????????????????//?to?growing?1.25x?for?large?slices.?This?formula
????????????????//?gives?a?smooth-ish?transition?between?the?two.
????????????????newcap?+=?(newcap?+?3*threshold)?/?4
????????????}
????????????//?Set?newcap?to?the?requested?cap?when
????????????//?the?newcap?calculation?overflowed.
????????????if?newcap?<=?0?{
????????????????newcap?=?cap
????????????}
????????}
????}

????//?...

????return?slice{p,?old.len,?newcap}
}

和之前版本的區(qū)別，主要在擴容閾值，以及這行代碼：newcap += (newcap + 3*threshold) / 4。

在分配內(nèi)存空間之前需要先確定新的切片容量，運行時根據(jù)切片的當(dāng)前容量選擇不同的策略進行擴容：

• 如果期望容量大于當(dāng)前容量的兩倍就會使用期望容量；
• 如果當(dāng)前切片的長度小于閾值（默認 256）就會將容量翻倍；
• 如果當(dāng)前切片的長度大于等于閾值（默認 256），就會每次增加 25% 的容量，基準(zhǔn)是 newcap + 3*threshold，直到新容量大于期望容量；

內(nèi)存對齊

分析完兩個版本的擴容策略之后，再看前面的那段測試代碼，就會發(fā)現(xiàn)擴容之后的容量并不是嚴格按照這個策略的。

那是為什么呢？

實際上，growslice 的后半部分還有更進一步的優(yōu)化（內(nèi)存對齊等），靠的是 roundupsize 函數(shù)，在計算完 newcap 值之后，還會有一個步驟計算最終的容量：

capmem?=?roundupsize(uintptr(newcap)?*?ptrSize)
newcap?=?int(capmem?/?ptrSize)

這個函數(shù)的實現(xiàn)就不在這里深入了，先挖一個坑，以后再來補上。

總結(jié)

切片擴容通常是在進行切片的 append 操作時觸發(fā)的。在進行 append 操作時，如果切片容量不足以容納新的元素，就需要對切片進行擴容，此時就會調(diào)用 growslice 函數(shù)進行擴容。

切片擴容分兩個階段，分為 go1.18 之前和之后：

一、go1.18 之前：

• 如果期望容量大于當(dāng)前容量的兩倍就會使用期望容量；
• 如果當(dāng)前切片的長度小于 1024 就會將容量翻倍；
• 如果當(dāng)前切片的長度大于 1024 就會每次增加 25% 的容量，直到新容量大于期望容量；

二、go1.18 之后：

• 如果期望容量大于當(dāng)前容量的兩倍就會使用期望容量；
• 如果當(dāng)前切片的長度小于閾值（默認 256）就會將容量翻倍；
• 如果當(dāng)前切片的長度大于等于閾值（默認 256），就會每次增加 25% 的容量，基準(zhǔn)是 newcap + 3*threshold，直到新容量大于期望容量；

到此這篇關(guān)于一文詳解Go語言切片是如何擴容的的文章就介紹到這了,更多相關(guān)Go語言切片擴容內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論