講的是切片，但好像又不隻是切片？

來自公#衆#号：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