Day1. Go語言精進之路：切片的原理並高效使用

由於近期忙於編寫公司的專案，導致懈怠了 golang 的學習，故而開啟 Go語言精進之路 系列文章，記錄學習過程中的理解和筆記。

關於切片#

Slice，中文譯作 切片，是 Go 語言中基於數組提供的一個抽象數據類型，在 Go 語言中，大部分需要使用數組的場景，皆可用切片代替。
在 Go 語言中，切片對數組實現了完美代替，並提供了更靈活、更高效的數據序列訪問接口。

切片究竟是什麼？#

在了解 Go 語言的 slice 之前，我們需要先了解數組。

切片是什麼？#

在 Go 中，數組是一個固定長度、容納相同類型元素的持續序列，因此，Go 數組有兩個屬性：元素類型 和 數組長度，這兩個類型都相同的數組是等價的。也就是：

var a [8]int
var b [8]int

這裡 a 的數組長度為 8，元素類型則為 int，與 b 相同，所以可以說，a 與 b 是等價的。

Go 是值語義的，那麼就意味著，一個數組變量表示的是整個數組，而不是數組的第一個元素的指針（這是 C 語言的做法）。而在 Go 語言中，傳遞數組使用的是值拷貝，那麼就導致如果需要傳遞元素類型長度較大，或者元素較多的數組時，會有不小的性能損耗。

在 C 語言中，這樣的場景可以使用數組指針類型來處理，但在 Go 語言中，一般使用切片處理。

切片與數組的關係#

切片與數組的關係，相當於文件描述符於文件一樣。在 Go 語言中，數組一般退居 "幕後"，作為數據存儲的 “底層”；而切片則走向 “前台”，為底層的存儲提供了對外訪問的接口。

所以，可以將切片稱為數組的 “描述符”。而切片之所以能在不同函數之間任意傳遞，就是因為 “描述符” 的特性，不管底層的數據存儲有多大，描述符的大小總是固定的。

切片的創建方式和 runtime 中的表示#

切片在 Go runtime 中的表示：

//$GOROOT/src/runtime/slice.go
type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

可以看到，slice 中有三個元素，分別是：

array：指向下層數組某元素的指針，這個元素也是切片的第一個元素。
len：切片的長度，也就是當前切片的元素個數
cap：切片的最大容量，cap >= len

在運行時中，每一個切片都是一個 runtime.slice 結構體的實例，可以用下面的語句創建一個切片：

s := make([]byte, 5)

切片運行時（創建新數組）

我們可以看到，在我們創建切片時，編譯器會默認創建一個底層數組，在我們沒有指定 cap 時，默認 cap = len。

我們也可以通過對已有數組的操作，來創建一個切片，我們將其稱為 數組的切片化：

u := [10]byte{11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
s := u[3:7]

切片運行時（切片化）

可以看到，切片 s 打開了一個數組 u 的操作窗口，s 的第一個元素為 u[3]，通過 s 可以看到並操作的數組元素有 4 個。切片的 cap 取決於底層數組的長度，從 u[3] 到末尾一共有 7 個存儲元素的槽位，所以 s 的 cap 為 7。

當然，我們也可以為一個數組創建多個操作數組的切片，但由於創建的多個切片都是同一個數組的描述符，所以對任意一個切片的修改都會反應到其他切片中。

我們也可以通過對切片的操作，來創建新的切片，這個操作稱為 reslicing。同樣的，基於老切片創建的新切片共享同一個底層數組，所以對新切片的修改也會反應到老切片中。

所以，當切片作為參數傳遞時，傳遞的是 runtime.slice，因此不管底層數組有多大，切片帶來的性能損耗都是很小且恆定的，甚至可以忽略不計，這就是在函數中通常使用切片而不是數組的原因之一。另一個原因是切片可以提供比指針數組更強大的功能，如下標訪問、邊界溢出校驗、動態擴容。

切片的高級特性#

動態擴容#

切片是滿足零值可用概念的，因為切片擁有一個高級特性：動態擴容，即便是零值切片，也可以通過 append 預定義函數進行元素賦值操作。

var k []int
k = append(k, 1)

k 被初始化為零值，所以 k 並沒有綁定對應的底層數組。但是，在經過 append 操作後，k 顯然已經綁定了屬於它的底層數組。

下面，我將通過一系列實操，來展示每次 append 後的 len 和 cap：

var s []int
s = append(s, 1)
fmt.Println(len(s), cap(s)) // 1 1
s = append(s, 2)
fmt.Println(len(s), cap(s)) // 2 2
s = append(s, 3)
fmt.Println(len(s), cap(s)) // 3 4
s = append(s, 4)
fmt.Println(len(s), cap(s)) // 4 4
s = append(s, 5)
fmt.Println(len(s), cap(s)) // 5 8

可以看出，len 的值是線性增長的，但是 cap 則是不規則增長。這張圖則形象的展示出了 append 操作是如何讓切片動態擴容的：

我們可以看到，最初 s 為零值，此時 s 還沒有綁定底層數組
通過 append 後，向切片 s 添加了一個元素 11，此時會分配一個底層數組 u1，數組長度為 1，然後將 s 內部的 array 指向 u1，所以此時，len = 1, cap = 1
然後再次 append，將 12 插入切片 s，但是此時切片顯然已經沒有空間再存儲 12 了。所以就需要再次擴容。所以就創建了底層數組 u2，長度為 2（u1 數組長度 * 2），並將 u1 中的所有元素複製到 u2 中，最後將 array 指向 u2，並設置 len = 2, cap = 2
通過 append 向 s 中再次插入一個元素 13，此時切片空間再次不足，需要再次擴容。所以，創建了新的底層數組 u3，長度為 4（u2 數組長度 * 2），並將 u2 的所有元素複製到 u3 中，然後將 array 指向 u3，並設置 len = 3, cap = 4
通過 append 向 s 中插入元素 14，此時切片 cap = 4，空間充足。所以將 14 放在下一個元素的位置，也就是 u3 的末尾，並將 s 內部的 len 加 1，變為 4
最後再次通過 append 向 s 插入 15，此時切片 len = 4, cap = 4，空間已經不足，再次擴容。所以，創建新的底層數組 u4，數組長度為 8（u3 數組長度 * 2），並將 u3 的所有元素複製到 u4 中，然後將 array 指向 u4，並設置 len = 5, cap = 8

可以發現，當切片的底層數組空間不足時，append 會根據需要去自動的將切片分配到新的底層數組，新數組長度會按照一定算法進行拓展（參見 $GOROOT/src/runtime/slice.go 中的 growslice 函數）。在新數組建立後，會將舊數組中的所有數據複製到新數組中，然後將 array 指向新數組，這樣，新數組就是切片的底層數組，舊數組則會被 gc 回收掉。

但是這樣，如果我們使用 數組的切片化 來創建的切片，一旦切片的 cap 觸碰到上邊界，再對切片進行 append 操作，那麼該切片就和原數組解除綁定。

u := [6]int{1, 2, 3, 4, 5, 6}
s := u[2:4]
fmt.Printf("u = %v, s = %v len(s) = %d, cap(s) = %d\n", u, s, len(s), cap(s))
s = append(s, 7)
fmt.Printf("append 7: u = %v, s = %v len(s) = %d, cap(s) = %d\n", u, s, len(s), cap(s))
s = append(s, 8)
fmt.Printf("append 8: u = %v, s = %v len(s) = %d, cap(s) = %d\n", u, s, len(s), cap(s))
s = append(s, 9)
fmt.Printf("append 9: u = %v, s = %v len(s) = %d, cap(s) = %d\n", u, s, len(s), cap(s))

// output:
// u = [1 2 3 4 5 6], s = [3 4] len(s) = 2, cap(s) = 4
// append 7: u = [1 2 3 4 7 6], s = [3 4 7] len(s) = 3, cap(s) = 4
// append 8: u = [1 2 3 4 7 8], s = [3 4 7 8] len(s) = 4, cap(s) = 4
// append 9: u = [1 2 3 4 7 8], s = [3 4 7 8 9] len(s) = 5, cap(s) = 8
// append 10: u = [1 2 3 4 7 8], s = [3 4 7 8 9 10] len(s) = 6, cap(s) = 8

從輸入結果可以看出，在添加元素 9 之後，cap(s) 就等於 8 了，也就是觸發了切片的動態擴容，而此時的切片 s，就已經與數組 u 解绑了，也就是 s 不再是 u 的描述符了。

儘量使用 cap 參數創建切片#

append 操作是一個利器，它讓切片支持了零值可用的理念，並讓切片變得更加易用。

但是從原理我們可以看出，每次擴容，都需要從老底層數組中將全部元素複製到新的底層數組，這一步所需要消耗的資源其實還是不少的，尤其是元素很多的情況下。那么如何避免過多內存分配和複製元素所付出的代價呢？

有一個有效的方案是，在編寫代碼時，有意識的去估算切片的所需容量，並在切片創建時，傳遞 cap 參數給內置函數 make。

s := make([]T, len, cap)

下面對兩種情況進行性能測試：

const sliceSize = 10000

func BenchmarkSliceInitWithoutCap(b *testing.B) {
	for n := 0; n < b.N; n++ {
		sl := make([]int, 0)
		for i := 0; i < sliceSize; i++ {
			sl = append(sl, i)
		}
	}
}

func BenchmarkSliceInitWithCap(b *testing.B) {
	for n := 0; n < b.N; n++ {
		sl := make([]int, 0, sliceSize)
		for i := 0; i < sliceSize; i++ {
			sl = append(sl, i)
		}
	}
}

得出的結果是：

goos: windows
goarch: amd64
pkg: prometheus_for_go
cpu: AMD Ryzen 7 5800H with Radeon Graphics         
BenchmarkSliceInitWithoutCap
BenchmarkSliceInitWithoutCap-16    	   34340	     34443 ns/op
BenchmarkSliceInitWithCap
BenchmarkSliceInitWithCap-16       	  106251	     11122 ns/op
PASS

可以看出，使用 cap 參數的切片在 append 時的平均性能為 11122 ns/op，大概是不使用 cap 參數的三倍。

所以，在創建切片時，建議攜帶 cap 參數。