Go 語言切片是如何擴容的?以下這篇文章為大家介紹一下Go 語言中切片的擴容機制,希望對大家有幫助!
在 Go 語言中,有一個很常用的資料結構,那就是切片(Slice)。
切片是一個擁有相同類型元素的可變長度的序列,它是基於陣列類型所做的一層封裝。它非常靈活,支援自動擴容。
切片是一種引用類型,它有三個屬性:指標,長度和容量。
底層原始碼定義如下:
1 2 3 4 5 | type slice struct {
array unsafe.Pointer
len int
cap int
}
|
登入後複製
- #指標: 指向 slice 可以存取到的第一個元素。
- 長度: slice 中元素個數。
- 容量: slice 起始元素到底層陣列最後一個元素間的元素個數。
例如使用make([]byte, 5)
建立一個切片,它看起來是這樣的:
##宣告和初始化
切片的使用還是比較簡單的,這裡舉個例子,直接看程式碼吧。
1 2 3 4 5 6 7 8 9 10 11 12 | func main() {
var nums []int
fmt.Println(len(nums), cap(nums))
nums = append(nums, 1)
fmt.Println(len(nums), cap(nums))
nums1 := []int{1,2,3,4}
fmt.Println(len(nums1), cap(nums1))
nums2 := make([]int,3,5)
fmt.Println(len(nums2), cap(nums2))
}
|
登入後複製
擴容時機
當切片的長度超過其容量時,切片會自動擴容。這通常發生在使用
append 函數向切片中新增元素時。
擴容時,Go 執行時會指派一個新的底層數組,並將原始切片中的元素複製到新數組中。然後,原始切片將指向新數組,並更新其長度和容量。
要注意的是,由於
擴充功能會指派新陣列並複製元素,因此可能會影響效能。如果你知道要添加多少元素,可以使用 make 函數預先分配足夠大的切片來避免頻繁擴容。
接下來看看
append 函數,簽章如下:
1 | func Append(slice []int, items ...int) []int
|
登入後複製
append 函數參數長度可變,可以追加多個值,還可以直接追加一個切片。使用起來比較簡單,分別看兩個例子:
追加多個值:
1 2 3 4 5 6 7 8 9 10 11 | package main
import "fmt"
func main() {
s := []int{1, 2, 3}
fmt.Println( "初始切片:" , s)
s = append(s, 4, 5, 6)
fmt.Println( "追加多个值后的切片:" , s)
}
|
登入後複製
輸出結果為:
1 2 | 初始切片: [1 2 3]
追加多个值后的切片: [1 2 3 4 5 6]
|
登入後複製
再來看一下直接
追加一個切片:
1 2 3 4 5 6 7 8 9 10 11 12 | 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)
}
|
登入後複製
輸出結果為:
1 2 | 初始切片: [1 2 3]
追加另一个切片后的切片: [1 2 3 4 5 6]
|
登入後複製
再來看一個
發生擴容的範例:
1 2 3 4 5 6 7 8 9 10 11 12 13 | package main
import "fmt"
func main() {
s := make([]int, 0, 3)
fmt.Printf( "初始状态: 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)
}
}
|
登入後複製
輸出結果為:
1 2 3 4 5 6 | 初始状态: 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]
|
登入後複製
在這個範例中,我們建立了一個長度為
0,容量為
3 的切片。然後,我們使用
append 函數在切片中新增
5 個元素。
當我們加入第
4 個元素時,切片的長度超過了其容量。此時,切片會自動擴容。新的容量是原始容量的兩倍,即
6。
表面現像已經看到了,接下來,我們就深入到原始碼層面,看看切片的擴容機製到底是什麼樣的。
原始碼分析
在 Go 語言的原始碼中,切片擴容通常是在進行切片的
append 操作時觸發的。在進行
append 操作時,如果切片容量不足以容納新的元素,就需要對切片進行擴容,此時就會呼叫
growslice 函數進行擴容。
growslice 函數定義在 Go 語言的 runtime 套件中,它的呼叫是在編譯後的程式碼中實現的。具體來說,當執行
append 操作時,編譯器會將其轉換為類似下面的程式碼:
1 | slice = append(slice, elem)
|
登入後複製
在上述程式碼中,如果切片容量不足以容納新的元素,則會呼叫
growslice 函數進行擴容。所以
growslice 函數的呼叫是
由編譯器在產生的機器碼中實現的,而不是在原始碼中明確調用的。
切片擴容策略有兩個階段,go1.18 之前和之後是不同的,這一點在 go1.18 的 release notes 中有說明。
下面我用 go1.17 和 go1.18 兩個版本來分開說明。先通過一段測試程式碼,直覺地感受一下兩個版本在擴容上的差異。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 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
}
}
}
|
登入後複製
上述程式碼先建立了一個空的 slice,然後在一個迴圈裡不斷往裡面
append 新元素。
然後記錄容量的變化,每當容量發生變化的時候,記錄下舊的容量,添加的元素,以及添加完元素之後的容量。
這樣就可以觀察,新舊 slice 的容量變化情況,從而找出規律。
運行結果(
1.17 版本):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | [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
|
登入後複製
運行結果(
1.18 版本):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | [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
|
登入後複製
根據上面的結果還是能看到差別的,具體擴容策略下面邊看源碼邊說明。
go1.17
扩容调用的是 growslice
函数,我复制了其中计算新容量部分的代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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 {
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
return slice{p, old.len, newcap}
}
|
登入後複製
在分配内存空间之前需要先确定新的切片容量,运行时根据切片的当前容量选择不同的策略进行扩容:
- 如果期望容量大于当前容量的两倍就会使用期望容量;
- 如果当前切片的长度小于 1024 就会将容量翻倍;
- 如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;
go1.18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | 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 {
for 0 < newcap && newcap < cap {
newcap += (newcap + 3*threshold) / 4
}
if newcap <= 0 {
newcap = cap
}
}
}
return slice{p, old.len, newcap}
}
|
登入後複製
和之前版本的区别,主要在扩容阈值,以及这行代码:newcap += (newcap + 3*threshold) / 4
。
在分配内存空间之前需要先确定新的切片容量,运行时根据切片的当前容量选择不同的策略进行扩容:
- 如果期望容量大于当前容量的两倍就会使用期望容量;
- 如果当前切片的长度小于阈值(默认 256)就会将容量翻倍;
- 如果当前切片的长度大于等于阈值(默认 256),就会每次增加 25% 的容量,基准是
newcap + 3*threshold
,直到新容量大于期望容量;
内存对齐
分析完两个版本的扩容策略之后,再看前面的那段测试代码,就会发现扩容之后的容量并不是严格按照这个策略的。
那是为什么呢?
实际上,growslice
的后半部分还有更进一步的优化(内存对齐等),靠的是 roundupsize
函数,在计算完 newcap
值之后,还会有一个步骤计算最终的容量:
1 2 | capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)
|
登入後複製
这个函数的实现就不在这里深入了,先挖一个坑,以后再来补上。
总结
切片扩容通常是在进行切片的 append
操作时触发的。在进行 append
操作时,如果切片容量不足以容纳新的元素,就需要对切片进行扩容,此时就会调用 growslice
函数进行扩容。
切片扩容分两个阶段,分为 go1.18 之前和之后:
一、go1.18 之前:
- 如果期望容量大于当前容量的两倍就会使用期望容量;
- 如果当前切片的长度小于 1024 就会将容量翻倍;
- 如果当前切片的长度大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;
二、go1.18 之后:
- 如果期望容量大于当前容量的两倍就会使用期望容量;
- 如果当前切片的长度小于阈值(默认 256)就会将容量翻倍;
- 如果当前切片的长度大于等于阈值(默认 256),就会每次增加 25% 的容量,基准是
newcap + 3*threshold
,直到新容量大于期望容量;
以上就是本文的全部内容,如果觉得还不错的话欢迎点赞,转发和关注,感谢支持。
推荐学习:Golang教程
以上是淺析Go語言的切片如何擴容的詳細內容。更多資訊請關注PHP中文網其他相關文章!