Go 語(yǔ)言切片是如何擴(kuò)容的？

作者：yongxinz 2023-04-03 08:02:16

切片擴(kuò)容通常是在進(jìn)行切片的 append? 操作時(shí)觸發(fā)的。在進(jìn)行 append? 操作時(shí)，如果切片容量不足以容納新的元素，就需要對(duì)切片進(jìn)行擴(kuò)容，此時(shí)就會(huì)調(diào)用 growslice 函數(shù)進(jìn)行擴(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)度和容量。

底層源碼定義如下：

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

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

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

聲明和初始化

切片的使用還是比較簡(jiǎn)單的，這里舉一個(gè)例子，直接看代碼吧。

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
}

擴(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ù)，簽名如下：

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

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

追加多個(gè)值：

package main

import "fmt"

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

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

輸出結(jié)果為：

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

再來(lái)看一下直接追加一個(gè)切片：

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("追加另一個(gè)切片后的切片:", s1)
}

輸出結(jié)果為：

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

再來(lái)看一個(gè)發(fā)生擴(kuò)容的例子：

package main

import "fmt"

func main() {
    s := make([]int, 0, 3) // 創(chuàng)建一個(gè)長(zhǎ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]

在這個(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)似下面的代碼：

slice = append(slice, elem)

在上述代碼中，如果切片容量不足以容納新的元素，則會(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ū)別。

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)建了一個(gè)空的 slice，然后在一個(gè)循環(huán)里不斷往里面 append 新元素。

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

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

運(yùn)行結(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

運(yùn)行結(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ū)別的，具體擴(kuò)容策略下面邊看源碼邊說(shuō)明。

go1.17

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

// 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)存空間之前需要先確定新的切片容量，運(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

// 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ū)別，主要在擴(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ì)算最終的容量：

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

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

總結(jié)

切片擴(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ò)的話歡迎點(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/

責(zé)任編輯：武曉燕來(lái)源： AlwaysBeta

切片擴(kuò)容 GO