Go 語言切片是如何擴容的？

原文鏈接： Go 語言切片是如何擴容的？

在 Go 語言中，有一個很常用的資料結構，那就是切片（Slice），

切片是一個擁有相同型別元素的可變長度的序列，它是基于陣列型別做的一層封裝，它非常靈活，支持自動擴容，

切片是一種參考型別，它有三個屬性：指標，長度和容量，

底層原始碼定義如下：

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

1. 指標： 指向 slice 可以訪問到的第一個元素，
2. 長度： slice 中元素個數，
3. 容量： slice 起始元素到底層陣列最后一個元素間的元素個數，

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

宣告和初始化

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

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()函式構造切片
    fmt.Println(len(nums2), cap(nums2))    // 3 5
}

擴容時機

當切片的長度超過其容量時，切片會自動擴容，這通常發生在使用 append 函式向切片中添加元素時，

擴容時，Go 運行時會分配一個新的底層陣列，并將原始切片中的元素復制到新陣列中，然后，原始切片將指向新陣列，并更新其長度和容量，

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

接下來看看 append 函式，簽名如下：

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

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

追加多個值：

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

輸出結果為：

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

再來看一個發生擴容的例子：

package main

import "fmt"

func main() {
    s := make([]int, 0, 3) // 創建一個長度為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)
    }
}

輸出結果為：

初始狀態: 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 操作時，編譯器會將其轉換為類似下面的代碼：

slice = append(slice, elem)

在上述代碼中，如果切片容量不足以容納新的元素，則會呼叫 growslice 函式進行擴容，所以 growslice 函式的呼叫是由編譯器在生成的機器碼中實作的，而不是在源代碼中顯式呼叫的，

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

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

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 版本）：

[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 版本）：

[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 函式，我復制了其中計算新容量部分的代碼，

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

在分配記憶體空間之前需要先確定新的切片容量，運行時根據切片的當前容量選擇不同的策略進行擴容：

1. 如果期望容量大于當前容量的兩倍就會使用期望容量；
2. 如果當前切片的長度小于 1024 就會將容量翻倍；
3. 如果當前切片的長度大于等于 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}
}

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

在分配記憶體空間之前需要先確定新的切片容量，運行時根據切片的當前容量選擇不同的策略進行擴容：

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

記憶體對齊

分析完兩個版本的擴容策略之后，再看前面的那段測驗代碼，就會發現擴容之后的容量并不是嚴格按照這個策略的，

那是為什么呢？

實際上，growslice 的后半部分還有更進一步的優化（記憶體對齊等），靠的是 roundupsize 函式，在計算完 newcap 值之后，還會有一個步驟計算最終的容量：

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

這個函式的實作就不在這里深入了，先挖一個坑，以后再來補上，

總結

切片擴容通常是在進行切片的 append 操作時觸發的，在進行 append 操作時，如果切片容量不足以容納新的元素，就需要對切片進行擴容，此時就會呼叫 growslice 函式進行擴容，

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

一、go1.18 之前：

1. 如果期望容量大于當前容量的兩倍就會使用期望容量；
2. 如果當前切片的長度小于 1024 就會將容量翻倍；
3. 如果當前切片的長度大于 1024 就會每次增加 25% 的容量，直到新容量大于期望容量；

二、go1.18 之后：

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

以上就是本文的全部內容，如果覺得還不錯的話歡迎點贊，轉發和關注，感謝支持，

參考文章：

• 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/

推薦閱讀：

• Go 語言陣列和切片的區別
• Go 語言 new 和 make 關鍵字的區別
• 為什么 Go 不支持 []T 轉換為 []interface
• 為什么 Go 語言 struct 要使用 tags

標籤：其他

上一篇：Golang與Java全方位對比總結

下一篇：推薦演算法在商城系統實踐