講的是切片，但好像又不只是切片？
本文轉載自微信公眾號「Gopher指北」，作者新世界雜貨鋪。轉載本文請聯系Gopher指北公眾號。
切片底層結構
切片和結構體的互轉
其他不扯多了，我們還是回歸本篇主題。在正式了解切片底層結構之前， 我們先看幾行代碼。
- type mySlice struct {
- data uintptr
- len int
- cap int
- }
- s := mySlice{}
- fmt.Println(fmt.Sprintf("%+v", s))
- // {data:0 len:0 cap:0}
- s1 := make([]int, 10)
- s1[2] = 2
- fmt.Println(fmt.Sprintf("%+v, len(%d), cap(%d)", s1, len(s1), cap(s1))) // [0 0 2 0 0 0 0 0 0 0], len(10), cap(10)
- s = *(*mySlice)(unsafe.Pointer(&s1))
- fmt.Println(fmt.Sprintf("%+v", s)) // {data:824634515456 len:10 cap:10}
- fmt.Printf("%p, %v\n", s1, unsafe.Pointer(s.data)) // 0xc0000c2000, 0xc0000c2000
在上述代碼中，通過獲取切片的地址，并將其轉為*mySlice, 成功獲得了切片的長度和容量。以及一個類似于指針一樣的東西。而這個指針就是指向存儲真實數據的數組，下面我們來進行驗證。
- //Data強轉為一個數組
- s2 := (*[5]int)(unsafe.Pointer(s.data))
- s3 := (*[10]int)(unsafe.Pointer(s.data))
- // 修改數組中的數據后切片中對應位置的值也發生了變化
- s2[4] = 4
- fmt.Println(s1) // [0 0 2 0 4 0 0 0 0 0]
- fmt.Println(*s2) // [0 0 2 0 4]
- fmt.Println(*s3) // [0 0 2 0 4 0 0 0 0 0]
到這里，切片的底層結構已經呼之欲出了，不過為了做更進一步的驗證，我們繼續測試結構體轉為切片的過程。
- var (
- // 一個長度為5的數組
- dt [5]int
- s4 []int
- )
- s5 := mySlice{
- // 將數組地址賦值給data
- data: uintptr(unsafe.Pointer(&dt)),
- len: 2,
- cap: 5,
- }
- // 結構體強轉為切片
- s4 = *((*[]int)(unsafe.Pointer(&s5)))
- fmt.Println(s4, len(s4), cap(s4)) // [0 0] 2 5
- // 修改數組中的值， 切片內容也會發生變化
- dt[1] = 3
- fmt.Println(dt, s4) // [0 3 0 0 0] [0 3]
通過上述三段代碼，我們將切片的底層結構以結構體的形式更加清晰的表達出來。如下圖所示，其中第一部分(Data)為指向數組的地址，第二部分(Len)為切片的長度即數組已使用的長度， 第三部分(Cap)為數組的長度。
小結：切片是對數組的包裝，底層仍使用數組存儲數據。
額外再多說一嘴：
reflect包要操作切片時通過reflect.SliceHeader結構體，詳見https://github.com/golang/go/blob/master/src/reflect/value.go#L2329
runtime對切片進行擴容時使用slice結構體, 詳見https://github.com/golang/go/blob/master/src/runtime/slice.go#L12
unsafe題外話
在前一部分的Demo中幾乎離不開unsafe包的使用。當然本篇并不是介紹此包的用法，只是作為一個題外話簡單看一下它為什么不安全。
- func otherOP(a, b *int) {
- reflect.ValueOf(a)
- reflect.ValueOf(b)
- }
- var (
- a = new(int)
- b = new(int)
- )
- otherOP(a, b) // 如果注釋此函數調用，最終輸出結果會發生變化
- *(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(a)) + unsafe.Sizeof(int(*a)))) = 1
- fmt.Println(*a, *b)
上述代在是否注釋otherOP時，其輸出結果是不一致的。
當變量逃逸至堆上時變量a和變量b內存地址相鄰，故能夠通過a變量地址去設置b變量的值。當未逃逸到堆上時，設置變量b的值并未生效，如此我們根本無法得知修改了哪一塊兒內存的值，這種不確定性在老許看來即是我們需要慎重使用此包的原因。
關于上述demo的補充解釋：
reflect.ValueOf會調用底層的escapes方法以保證對象逃逸到堆中
Go中采用按大小分割的空閑鏈表內存分配器以及多級緩存，故a，b變量在大小一致且本demo變量較少的的情況下很有可能被分配到連續的內存空間中
創建切片
創建切片方式有四種。第一種直接通過var進行變量聲明，第二種通過類型推導，第三種通過make方式去創建，第四種通過切片表達式創建。
- // 通過變量聲明的方式創建
- var a []int
- // 類型推導
- b := []int{1, 2, 3}
- // make創建
- c := make([]int, 2) // c := make([]int, 0, 5)
- // 切片表達式
- d := c[:3]
上述例子中，前三種沒什么特別好說的，老許主要介紹一下第四種,以及它的相關限制和注意事項。
簡單的切片表達式
對于字符串、數組、數組指針和切片(切片指針不能使用下面的表達式)均可使用下面的表達式：
- s[low:high] // 生成的切片長度為high-low
通過上述表達式可創建新的子串或者切片。特別注意的是，對字符串使用此表達式時既不是生成字符串切片也不是生成字節切片而是生成子字符串。另外，老許在go中字符串的編碼問題中提到Go中的字符串存儲的就是utf8字節切片，所以我們在使用此方法獲取包含中文等特殊字符時有可能會出現意想不到的結果。正確得到子串的方式應該是先轉為rune切片再截取。
上述表達式已經可以十分方便地創建新的切片，然而更加方便地是low和high還可以省略。
- s[2:] // same as s[2 : len(a)]
- s[:3] // same as s[0 : 3]
- s[:] // same as s[0 : len(a)]
下標限制
對不同的類型使用切片表達式，low和high的取值范圍不同。對于字符串和數組/數組指針而言，low和high的取值范圍為0 <= low <= len(s)。對于切片而言，low和high的取值范圍為0 <= low <= cap(s)。在切片面試題系列一中正是對此知識點的考察。
切片容量
通過切片表達式生成的切片，其底層數組共享，因此切片的容量為底層數組的長度減去low。由此可以推斷下述代碼輸出結果為3 8和3 13。
- var (
- s1 [10]int
- s2 []int = make([]int, 10, 15)
- )
- s := s1[2:5]
- fmt.Println(len(s), cap(s))
- s = s2[2:5]
- fmt.Println(len(s), cap(s))
- return
完整的切片表達式
說實話這種方式真的不常用，雖然它可以控制切片的容量，但老許在實際開發中并未使用過。其完整表達式如下：
- s[low : high : max]
這種表達式有幾個需要注意的點分別是：
- 只適用于數組、數組指針和切片不適用于字符串。
- 和簡單切片表達式不同的是，它只能忽略low這個下標且忽略后該下標默認值為0。
- 和簡單切片表達式一樣，通過完整切片表達式生成的切片底層數組共享
下標限制
對數組/數組指針而言，下標取值范圍為0 <= low <= high <= max <= len(s)。對切片而言，下標取值范圍為0 <= low <= high <= cap(s)。在切片面試題系列二中正是對此知識點的考察。
切片容量
前面提到此切片表達式可以控制切片的容量。在low一定的情況下，通過改變max在允許范圍內的值即可改變切片的容量，其容量計算方式為max - low。
切片擴容
runtime/slice.go文件的growslice函數實現了切片的擴容邏輯,在正式分析內部邏輯之前我們先看看growslice的函數簽名：
- type slice struct {
- array unsafe.Pointer
- len int
- cap int
- }
- func growslice(et *_type, old slice, cap int) slice
第一個參數_type是Go語言類型的運行時表示，其中包含了很多元信息，例如：類型大小、對齊以及種類等。
第二個參數為待擴容切片的信息。
第三個參數為真實需要的容量，即原容量和新增元素數量之和，老許對其簡稱為所需容量。為了更加容易理解所需容量的含義，我們先看一段代碼：
- s := []int{1,2,3} // 此時切片長度和容量均為3
- s = append(s, 4) // 此時所需容量為3 + 1
- s1 := []int{1,2,3} // 此時切片長度和容量均為3
- s1 = append(s1, 4, 5, 6) // 此時所需容量為3 + 3
擴容邏輯
有了上面的概念之后，下面我們看看切片擴容算法：
上圖邏輯總結如下：
首先，如果所需容量大于2倍當前容量則新容量為所需容量。
其次，判斷當前容量是否大于1024。如果當前容量小于1024則新容量等于2倍當前容量。如果當前容量大于等于1024則新容量循環增加1/4倍新容量直到新容量大于等于所需容量。
老許在這里特別提示，和0的比較是有用的。初始時，老許也覺得這邏輯十分多余，后來有一天突然頓悟，這實際上是對整形溢出的判斷。因為平時開發中很少會考慮這個問題，一時間驚為天人。也許我們和大神之間的代碼差距僅僅是少了對溢出的判斷。
另外一個有意思的事情是，切片的邏輯最開始也不是這樣的。這邏輯并不復雜，即使是剛入門的人寫起來也毫無壓力。然而即便是這樣簡單的邏輯，也是經過多個版本的迭代才有了如今的模樣。
有一說一，在老許看來1.6中的擴容邏輯并不算優雅。想到這兒，一種“我贏了”的感覺油然而生，程序猿的快樂就是如此簡單。
計算內存容量
前文中的擴容邏輯是理想的內存分配容量，而真實的內存分配十分復雜。在Go1.6中切片擴容分配內存時分為四種情況，分別是類型大小為1字節、類型大小為指針大小、類型大小為2的n次冪和其他。而切片擴容分配內存時在不同的Go版本中又略有不同，這里只介紹1.16中類型大小為2的n次冪時內存分配。
下面直接上代碼：
- var shift uintptr
- if sys.PtrSize == 8 {
- // Mask shift for better code generation.
- // et.size = 1 << n
- // shift = n
- // &63是因為uint64中1最大左移63，再大就溢出了
- shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
- } else {
- shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
- }
上述代碼中，通過對指針大小判斷以區分當前運行的是32位還是64位平臺。Ctz64和Ctz32函數是針對不同類型計算最低位0的個數。又因為類型大小是2的n次冪，則0的個數即為n。
類型大小為2的n次冪，則類型大小一定為 1 << n，因此計算最低位0的個數即可得到左移的位數。
源碼中通過x&(x-1) == 0表達式判斷一個無符號整數是否為2的n次冪。我們平時開發中如果有類似的邏輯，請參考切片擴容源碼開始裝逼之旅。
接下來是計算內存容量的邏輯：
- capmem = roundupsize(uintptr(newcap) << shift)
- newcap = int(capmem >> shift)
結合前文易知，uintptr(newcap) << shift實際上可以理解為uintptr(newcap) * et.size，capmem >> shift可理解為capmem / et.size。uintptr(newcap) << shift是最理想的所需內存大小，而實際分配內存時因為內存對齊等問題無法達到理想狀況，所以通過roundupsize計算出實際需要的內存大小,最后再計算出真實容量。有了這個理解之后我們接下來著重分析roundupsize函數。
- func roundupsize(size uintptr) uintptr {
- if size < _MaxSmallSize {
- if size <= smallSizeMax-8 {
- return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
- } else {
- return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
- }
- }
- if size+_PageSize < size {
- return size
- }
- return alignUp(size, _PageSize)
- }
上面函數有很多含義不清楚的變量，老許接下來會對其一一解釋。
_MaxSmallSize: 其值為32768，即32kb大小。在Go中，當對象大小超過32kb時，內存分配策略和小于等于32kB時是有區別的。
smallSizeMax: 其值為1024字節。
smallSizeDiv: 其值為8字節。
largeSizeDiv: 其值為128字節。
_PageSize: 8192字節，即8kb大小。Go按頁來管理內存，而每一頁的大小就為8kb。
class_to_size: Go中的內存分配會按照不同跨度(也可理解為內存大小)將內存分割成不同內存塊鏈表。當需要分配內存時，按照對象大小去匹配最合適的跨度找到空閑的內存塊兒。Go中總共分為67個跨度，class_to_size是一個長度為68的數組，分別記錄0和這67個跨度的值。源碼詳見sruntime/izeclasses.go。
size_to_class8: 這是一個長度為129的數組，代表的內存大小區間為0~1024字節。以索引i為例，此位置的對象大小m為i * smallSizeDiv，size_to_class8[i]的值為class_to_size數組中跨度最接近m的下標。
size_to_class128：這是一個長度為249的數組，代表的內存大小區間為1024~32768字節。以索引i為例，此位置的對象大小m為smallSizeMax + i*largeSizeDiv, size_to_class128[i]的值為class_to_size數組中跨度最接近m的下標。
divRoundUp: 此函數返回a/b向上舍入最接近的整數。
alignUp: alignUp(size, _PageSize) = _PageSize * divRoundUp(size, _PageSize)。
最終將計算實際需要內存大小的邏輯表示如下：
到這里，切片擴容的核心邏輯就已經分析完畢。本篇不對類型大小為1字節、類型大小為指針大小以及其他大小進行擴容邏輯分析的原因是整體邏輯差別不大。在老許看來源碼中對類型大小區分的主要目的是為了盡可能減少除法和乘法運算。每每閱讀這些優秀的源碼都令老許直呼細節怪物。
為了加深印象我們以切片面試題系列三中的一個例子進行一次演算。
- s3 := []int{1, 2}
- s3 = append(s3, 3, 4, 5)
- fmt.Println(cap(s3))
根據前文知，所需容量為5，又因所需容量大于2倍當前容量，故新容量也為5。
又因為int類型大小為8(等于64位平臺上的指針大小)，所以實際需要的內存大小為5 * 8 = 40字節。而67個跨度中最接近40字節的跨度為48字節，所以實際分配的內存容量為48字節。
最終計算真實的容量為48 / 8 = 6，和老許實際運行輸出一致。
最后，衷心希望本文能夠對各位讀者有一定的幫助。
注：
寫本文時， 筆者所用go版本為: go1.16.6
文章中所用完整例子：https://github.com/Isites/go-coder/blob/master/slice/main.go
