image

原文地址：深入理解 Go Slice

是什么

在 Go 中，Slice（切片）是抽象在 Array（數(shù)組）之上的特殊類型。為了更好地了解 Slice，第一步需要先對(duì) Array 進(jìn)行理解。深刻了解 Slice 與 Array 之間的區(qū)別后，就能更好的對(duì)其底層一番摸索 ??

用法

Array

func main() {
    nums := [3]int{}
    nums[0] = 1

    n := nums[0]
    n = 2

    fmt.Printf("nums: %v\n", nums)
    fmt.Printf("n: %d\n", n)
}

我們可得知在 Go 中，數(shù)組類型需要指定長(zhǎng)度和元素類型。在上述代碼中，可得知 [3]int{} 表示 3 個(gè)整數(shù)的數(shù)組，并進(jìn)行了初始化。底層數(shù)據(jù)存儲(chǔ)為一段連續(xù)的內(nèi)存空間，通過(guò)固定的索引值（下標(biāo)）進(jìn)行檢索

image

數(shù)組在聲明后，其元素的初始值（也就是零值）為 0。并且該變量可以直接使用，不需要特殊操作

同時(shí)數(shù)組的長(zhǎng)度是固定的，它的長(zhǎng)度是類型的一部分，因此 [3]int 和 [4]int 在類型上是不同的，不能稱為 “一個(gè)東西”

輸出結(jié)果

nums: [1 0 0] 
n: 2 

Slice

func main() {
    nums := [3]int{}
    nums[0] = 1

    dnums := nums[:]

    fmt.Printf("dnums: %v", dnums)
}

Slice 是對(duì) Array 的抽象，類型為 []T。在上述代碼中，dnums 變量通過(guò) nums[:] 進(jìn)行賦值。需要注意的是，Slice 和 Array 不一樣，它不需要指定長(zhǎng)度。也更加的靈活，能夠自動(dòng)擴(kuò)容

數(shù)據(jù)結(jié)構(gòu)

image

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

Slice 的底層數(shù)據(jù)結(jié)構(gòu)共分為三部分，如下：

• array：指向所引用的數(shù)組指針（unsafe.Pointer 可以表示任何可尋址的值的指針）
• len：長(zhǎng)度，當(dāng)前引用切片的元素個(gè)數(shù)
• cap：容量，當(dāng)前引用切片的容量（底層數(shù)組的元素總數(shù)）

在實(shí)際使用中，cap 一定是大于或等于 len 的。否則會(huì)導(dǎo)致 panic

示例

為了更好的理解，我們回顧上小節(jié)的代碼便于演示，如下：

func main() {
    nums := [3]int{}
    nums[0] = 1

    dnums := nums[:]

    fmt.Printf("dnums: %v", dnums)
}

image

在代碼中，可觀察到 dnums := nums[:]，這段代碼確定了 Slice 的 Pointer 指向數(shù)組，且 len 和 cap 都為數(shù)組的基礎(chǔ)屬性。與圖示表達(dá)一致

len、cap 不同

func main() {
    nums := [3]int{}
    nums[0] = 1

    dnums := nums[0:2]

    fmt.Printf("dnums: %v, len: %d, cap: %d", dnums, len(dnums), cap(dnums))
}

image

輸出結(jié)果

dnums: [1 0], len: 2, cap: 3

顯然，在這里指定了 Slice[0:2]，因此 len 為所引用元素的個(gè)數(shù)，cap 為所引用的數(shù)組元素總個(gè)數(shù)。與期待一致 ??

創(chuàng)建

Slice 的創(chuàng)建有兩種方式，如下：

• var []T 或 []T{}
• func make（[] T，len，cap）[] T

可以留意 make 函數(shù)，我們都知道 Slice 需要指向一個(gè) Array。那 make 是怎么做的呢？

它會(huì)在調(diào)用 make 的時(shí)候，分配一個(gè)數(shù)組并返回引用該數(shù)組的 Slice

func makeslice(et *_type, len, cap int) slice {
    maxElements := maxSliceCap(et.size)
    if len < 0 || uintptr(len) > maxElements {
        panic(errorString("makeslice: len out of range"))
    }

    if cap < len || uintptr(cap) > maxElements {
        panic(errorString("makeslice: cap out of range"))
    }

    p := mallocgc(et.size*uintptr(cap), et, true)
    return slice{p, len, cap}
}

• 根據(jù)傳入的 Slice 類型，獲取其類型能夠申請(qǐng)的最大容量大小
• 判斷 len 是否合規(guī)，檢查是否在 0 < x < maxElements 范圍內(nèi)
• 判斷 cap 是否合規(guī)，檢查是否在 len < x < maxElements 范圍內(nèi)
• 申請(qǐng) Slice 所需的內(nèi)存空間對(duì)象。若為大型對(duì)象（大于 32 KB）則直接從堆中分配
• 返回申請(qǐng)成功的 Slice 內(nèi)存地址和相關(guān)屬性（默認(rèn)返回申請(qǐng)到的內(nèi)存起始地址）

擴(kuò)容

當(dāng)使用 Slice 時(shí)，若存儲(chǔ)的元素不斷增長(zhǎng)（例如通過(guò) append）。當(dāng)條件滿足擴(kuò)容的策略時(shí)，將會(huì)觸發(fā)自動(dòng)擴(kuò)容

那么分別是什么規(guī)則呢？讓我們一起看看源碼是怎么說(shuō)的 ??

zerobase

func growslice(et *_type, old slice, cap int) slice {
    ...
    if et.size == 0 {
        if cap < old.cap {
            panic(errorString("growslice: cap out of range"))
        }
        
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }
    ...
}

當(dāng) Slice size 為 0 時(shí)，若將要擴(kuò)容的容量比原本的容量小，則拋出異常（也就是不支持縮容操作）。否則，將重新生成一個(gè)新的 Slice 返回，其 Pointer 指向一個(gè) 0 byte 地址（不會(huì)保留老的 Array 指向）

擴(kuò)容 - 計(jì)算策略

func growslice(et *_type, old slice, cap int) slice {
    ...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            ...
        }
    }
    ...
}

• 若 Slice cap 大于 doublecap，則擴(kuò)容后容量大小為 新 Slice 的容量（超了基準(zhǔn)值，我就只給你需要的容量大?。?/li>
• 若 Slice len 小于 1024 個(gè)，在擴(kuò)容時(shí)，增長(zhǎng)因子為 1（也就是 3 個(gè)變 6 個(gè)）
• 若 Slice len 大于 1024 個(gè)，在擴(kuò)容時(shí)，增長(zhǎng)因子為 0.25（原本容量的四分之一）

注：也就是小于 1024 個(gè)時(shí)，增長(zhǎng) 2 倍。大于 1024 個(gè)時(shí)，增長(zhǎng) 1.25 倍

擴(kuò)容 - 內(nèi)存策略

func growslice(et *_type, old slice, cap int) slice {
    ...
    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    const ptrSize = unsafe.Sizeof((*byte)(nil))
    switch et.size {
    case 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        overflow = uintptr(newcap) > _MaxMem
        newcap = int(capmem)
        ...
    }

    if cap < old.cap || overflow || capmem > _MaxMem {
        panic(errorString("growslice: cap out of range"))
    }

    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        p = mallocgc(capmem, nil, false)
        memmove(p, old.array, lenmem)
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        p = mallocgc(capmem, et, true)
        if !writeBarrier.enabled {
            memmove(p, old.array, lenmem)
        } else {
            for i := uintptr(0); i < lenmem; i += et.size {
                typedmemmove(et, add(p, i), add(old.array, i))
            }
        }
    }
    ...
}

1、獲取老 Slice 長(zhǎng)度和計(jì)算假定擴(kuò)容后的新 Slice 元素長(zhǎng)度、容量大小以及指針地址（用于后續(xù)操作內(nèi)存的一系列操作）

2、確定新 Slice 容量大于老 Sice，并且新容量?jī)?nèi)存小于指定的最大內(nèi)存、沒(méi)有溢出。否則拋出異常

3、若元素類型為 kindNoPointers，也就是非指針類型。則在老 Slice 后繼續(xù)擴(kuò)容

• 第一步：根據(jù)先前計(jì)算的 capmem，在老 Slice cap 后繼續(xù)申請(qǐng)內(nèi)存空間，其后用于擴(kuò)容
• 第二步：將 old.array 上的 n 個(gè) bytes（根據(jù) lenmem）拷貝到新的內(nèi)存空間上
• 第三步：新內(nèi)存空間（p）加上新 Slice cap 的容量地址。最終得到完整的新 Slice cap 內(nèi)存地址 add(p, newlenmem) （ptr）
• 第四步：從 ptr 開始重新初始化 n 個(gè) bytes（capmem-newlenmem）

注：那么問(wèn)題來(lái)了，為什么要重新初始化這塊內(nèi)存呢？這是因?yàn)?ptr 是未初始化的內(nèi)存（例如：可重用的內(nèi)存，一般用于新的內(nèi)存分配），其可能包含 “垃圾”。因此在這里應(yīng)當(dāng)進(jìn)行 “清理”。便于后面實(shí)際使用（擴(kuò)容）

4、不滿足 3 的情況下，重新申請(qǐng)并初始化一塊內(nèi)存給新 Slice 用于存儲(chǔ) Array

5、檢測(cè)當(dāng)前是否正在執(zhí)行 Write Barrier（寫屏障）。若正在啟用 Write Barrier，則通過(guò) memmove 采取拷貝的方式將 lenmem 個(gè)字節(jié)從 old.array 拷貝到 ptr。否則使用 typedmemmove 的方式，利用指針循環(huán)拷貝。以此達(dá)到更高的效率

注：一般會(huì)在 GC 標(biāo)記階段啟用 Write Barrier，并且 Write Barrier 只針對(duì)指針啟用。那么在第 5 點(diǎn)中，你就不難理解為什么會(huì)有兩種截然不同的處理方式了

小結(jié)

這里需要注意的是，擴(kuò)容時(shí)的內(nèi)存管理的選擇項(xiàng)，如下：

• 翻新擴(kuò)展：當(dāng)前元素為 kindNoPointers，將在老 Slice cap 的地址后繼續(xù)申請(qǐng)空間用于擴(kuò)容
• 舉家搬遷：重新申請(qǐng)一塊內(nèi)存地址，整體遷移并擴(kuò)容

兩個(gè)小 “陷阱”

一、同根

func main() {
    nums := [3]int{}
    nums[0] = 1

    fmt.Printf("nums: %v , len: %d, cap: %d\n", nums, len(nums), cap(nums))

    dnums := nums[0:2]
    dnums[0] = 5

    fmt.Printf("nums: %v ,len: %d, cap: %d\n", nums, len(nums), cap(nums))
    fmt.Printf("dnums: %v, len: %d, cap: %d\n", dnums, len(dnums), cap(dnums))
}

輸出結(jié)果：

nums: [1 0 0] , len: 3, cap: 3
nums: [5 0 0] ,len: 3, cap: 3
dnums: [5 0], len: 2, cap: 3

在未擴(kuò)容前，Slice array 指向所引用的 Array。因此在 Slice 上的變更。會(huì)直接修改到原始 Array 上（兩者所引用的是同一個(gè)）

image

二、時(shí)過(guò)境遷

隨著 Slice 不斷 append，內(nèi)在的元素越來(lái)越多，終于觸發(fā)了擴(kuò)容。如下代碼：

func main() {
    nums := [3]int{}
    nums[0] = 1

    fmt.Printf("nums: %v , len: %d, cap: %d\n", nums, len(nums), cap(nums))

    dnums := nums[0:2]
    dnums = append(dnums, []int{2, 3}...)
    dnums[1] = 1

    fmt.Printf("nums: %v ,len: %d, cap: %d\n", nums, len(nums), cap(nums))
    fmt.Printf("dnums: %v, len: %d, cap: %d\n", dnums, len(dnums), cap(dnums))
}

輸出結(jié)果：

nums: [1 0 0] , len: 3, cap: 3
nums: [1 0 0] ,len: 3, cap: 3
dnums: [1 1 2 3], len: 4, cap: 6

往 Slice append 元素時(shí)，若滿足擴(kuò)容策略，也就是假設(shè)插入后，原本數(shù)組的容量就超過(guò)最大值了

這時(shí)候內(nèi)部就會(huì)重新申請(qǐng)一塊內(nèi)存空間，將原本的元素拷貝一份到新的內(nèi)存空間上。此時(shí)其與原本的數(shù)組就沒(méi)有任何關(guān)聯(lián)關(guān)系了，再進(jìn)行修改值也不會(huì)變動(dòng)到原始數(shù)組。這是需要注意的

image

復(fù)制

原型

func copy（dst，src [] T）int

copy 函數(shù)將數(shù)據(jù)從源 Slice復(fù)制到目標(biāo) Slice。它返回復(fù)制的元素?cái)?shù)。

示例

func main() {
    dst := []int{1, 2, 3}
    src := []int{4, 5, 6, 7, 8}
    n := copy(dst, src)

    fmt.Printf("dst: %v, n: %d", dst, n)
}

copy 函數(shù)支持在不同長(zhǎng)度的 Slice 之間進(jìn)行復(fù)制，若出現(xiàn)長(zhǎng)度不一致，在復(fù)制時(shí)會(huì)按照最少的 Slice 元素個(gè)數(shù)進(jìn)行復(fù)制

那么在源碼中是如何完成復(fù)制這一個(gè)行為的呢？我們來(lái)一起看看源碼的實(shí)現(xiàn)，如下：

func slicecopy(to, fm slice, width uintptr) int {
    if fm.len == 0 || to.len == 0 {
        return 0
    }

    n := fm.len
    if to.len < n {
        n = to.len
    }

    if width == 0 {
        return n
    }

    ...

    size := uintptr(n) * width
    if size == 1 {
        *(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
    } else {
        memmove(to.array, fm.array, size)
    }
    return n
}

• 若源 Slice 或目標(biāo) Slice 存在長(zhǎng)度為 0 的情況，則直接返回 0（因?yàn)閴焊恍枰獔?zhí)行復(fù)制行為）
• 通過(guò)對(duì)比兩個(gè) Slice，獲取最小的 Slice 長(zhǎng)度。便于后續(xù)操作
• 若 Slice 只有一個(gè)元素，則直接利用指針的特性進(jìn)行轉(zhuǎn)換
• 若 Slice 大于一個(gè)元素，則從 fm.array 復(fù)制 size 個(gè)字節(jié)到 to.array 的地址處（會(huì)覆蓋原有的值）

"奇特"的初始化

在 Slice 中流傳著兩個(gè)傳說(shuō)，分別是 Empty 和 Nil Slice，接下來(lái)讓我們看看它們的小區(qū)別 ??

Empty

func main() {
    nums := []int{}
    renums := make([]int, 0)
    
    fmt.Printf("nums: %v, len: %d, cap: %d\n", nums, len(nums), cap(nums))
    fmt.Printf("renums: %v, len: %d, cap: %d\n", renums, len(renums), cap(renums))
}

輸出結(jié)果：

nums: [], len: 0, cap: 0
renums: [], len: 0, cap: 0

Nil

func main() {
    var nums []int
}

輸出結(jié)果：

nums: [], len: 0, cap: 0

想一想

乍一看，Empty Slice 和 Nil Slice 好像一模一樣？不管是 len，還是 cap 都為 0。好像沒(méi)區(qū)別？我們?cè)倏纯慈缦麓a：

func main() {
    var nums []int
    renums := make([]int, 0)
    if nums == nil {
        fmt.Println("nums is nil.")
    }
    if renums == nil {
        fmt.Println("renums is nil.")
    }
}

你覺(jué)得輸出結(jié)果是什么呢？你可能已經(jīng)想到了，最終的輸出結(jié)果：

nums is nil.

為什么

Empty

image

Nil

image

從圖示中可以看出來(lái)，兩者有本質(zhì)上的區(qū)別。其底層數(shù)組的指向指針是不一樣的，Nil Slice 指向的是 nil，Empty Slice 指向的是實(shí)際存在的空數(shù)組地址

你可以認(rèn)為，Nil Slice 代指不存在的 Slice，Empty Slice 代指空集合。兩者所代表的意義是完全不同的

總結(jié)

通過(guò)本文，可得知 Go Slice 相當(dāng)靈活。不需要你手動(dòng)擴(kuò)容，也不需要你關(guān)注加多少減多少。對(duì) Array 是動(dòng)態(tài)引用，是 Go 類型的一個(gè)極大的補(bǔ)充，也因此在應(yīng)用中使用的更多、更便捷

雖然有個(gè)別要注意的 “坑”，但其實(shí)是合理的。你覺(jué)得呢？??