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