[[413340]]

本文轉(zhuǎn)載自微信公眾號「Gopher指北」，作者新世界雜貨鋪。轉(zhuǎn)載本文請聯(lián)系Gopher指北公眾號。

切片底層結(jié)構

切片和結(jié)構體的互轉(zhuǎn)

其他不扯多了，我們還是回歸本篇主題。在正式了解切片底層結(jié)構之前， 我們先看幾行代碼。

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 

在上述代碼中，通過獲取切片的地址，并將其轉(zhuǎn)為*mySlice, 成功獲得了切片的長度和容量。以及一個類似于指針一樣的東西。而這個指針就是指向存儲真實數(shù)據(jù)的數(shù)組，下面我們來進行驗證。

//Data強轉(zhuǎn)為一個數(shù)組 
s2 := (*[5]int)(unsafe.Pointer(s.data)) 
s3 := (*[10]int)(unsafe.Pointer(s.data)) 
// 修改數(shù)組中的數(shù)據(jù)后切片中對應位置的值也發(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é)構已經(jīng)呼之欲出了，不過為了做更進一步的驗證，我們繼續(xù)測試結(jié)構體轉(zhuǎn)為切片的過程。

var ( 
 // 一個長度為5的數(shù)組 
 dt [5]int 
 s4 []int 
) 
s5 := mySlice{ 
 // 將數(shù)組地址賦值給data 
 data: uintptr(unsafe.Pointer(&dt)), 
 len:  2, 
 cap:  5, 
} 
// 結(jié)構體強轉(zhuǎn)為切片 
s4 = *((*[]int)(unsafe.Pointer(&s5))) 
fmt.Println(s4, len(s4), cap(s4)) // [0 0] 2 5 
// 修改數(shù)組中的值， 切片內(nèi)容也會發(fā)生變化 
dt[1] = 3 
fmt.Println(dt, s4) // [0 3 0 0 0] [0 3] 

通過上述三段代碼，我們將切片的底層結(jié)構以結(jié)構體的形式更加清晰的表達出來。如下圖所示，其中第一部分(Data)為指向數(shù)組的地址，第二部分(Len)為切片的長度即數(shù)組已使用的長度， 第三部分(Cap)為數(shù)組的長度。

小結(jié)：切片是對數(shù)組的包裝，底層仍使用數(shù)組存儲數(shù)據(jù)。

額外再多說一嘴：

reflect包要操作切片時通過reflect.SliceHeader結(jié)構體，詳見https://github.com/golang/go/blob/master/src/reflect/value.go#L2329

runtime對切片進行擴容時使用slice結(jié)構體, 詳見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) // 如果注釋此函數(shù)調(diào)用，最終輸出結(jié)果會發(fā)生變化 
*(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(a)) + unsafe.Sizeof(int(*a)))) = 1 
fmt.Println(*a, *b) 

上述代在是否注釋otherOP時，其輸出結(jié)果是不一致的。

當變量逃逸至堆上時變量a和變量b內(nèi)存地址相鄰，故能夠通過a變量地址去設置b變量的值。當未逃逸到堆上時，設置變量b的值并未生效，如此我們根本無法得知修改了哪一塊兒內(nèi)存的值，這種不確定性在老許看來即是我們需要慎重使用此包的原因。

關于上述demo的補充解釋：

reflect.ValueOf會調(diào)用底層的escapes方法以保證對象逃逸到堆中

Go中采用按大小分割的空閑鏈表內(nèi)存分配器以及多級緩存，故a，b變量在大小一致且本demo變量較少的的情況下很有可能被分配到連續(xù)的內(nèi)存空間中

創(chuàng)建切片

創(chuàng)建切片方式有四種。第一種直接通過var進行變量聲明，第二種通過類型推導，第三種通過make方式去創(chuàng)建，第四種通過切片表達式創(chuàng)建。

// 通過變量聲明的方式創(chuàng)建 
var a []int 
// 類型推導 
b := []int{1, 2, 3} 
// make創(chuàng)建 
c := make([]int, 2) // c := make([]int, 0, 5) 
// 切片表達式 
d := c[:3] 

上述例子中，前三種沒什么特別好說的，老許主要介紹一下第四種,以及它的相關限制和注意事項。

簡單的切片表達式

對于字符串、數(shù)組、數(shù)組指針和切片(切片指針不能使用下面的表達式)均可使用下面的表達式：

s[low:high] // 生成的切片長度為high-low 

通過上述表達式可創(chuàng)建新的子串或者切片。特別注意的是，對字符串使用此表達式時既不是生成字符串切片也不是生成字節(jié)切片而是生成子字符串。另外，老許在go中字符串的編碼問題中提到Go中的字符串存儲的就是utf8字節(jié)切片，所以我們在使用此方法獲取包含中文等特殊字符時有可能會出現(xiàn)意想不到的結(jié)果。正確得到子串的方式應該是先轉(zhuǎn)為rune切片再截取。

上述表達式已經(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)] 

下標限制

對不同的類型使用切片表達式，low和high的取值范圍不同。對于字符串和數(shù)組/數(shù)組指針而言，low和high的取值范圍為0 <= low <= len(s)。對于切片而言，low和high的取值范圍為0 <= low <= cap(s)。在切片面試題系列一中正是對此知識點的考察。

切片容量

通過切片表達式生成的切片，其底層數(shù)組共享，因此切片的容量為底層數(shù)組的長度減去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 

完整的切片表達式

說實話這種方式真的不常用，雖然它可以控制切片的容量，但老許在實際開發(fā)中并未使用過。其完整表達式如下：

s[low : high : max] 

這種表達式有幾個需要注意的點分別是：

• 只適用于數(shù)組、數(shù)組指針和切片不適用于字符串。
• 和簡單切片表達式不同的是，它只能忽略low這個下標且忽略后該下標默認值為0。
• 和簡單切片表達式一樣，通過完整切片表達式生成的切片底層數(shù)組共享

下標限制

對數(shù)組/數(shù)組指針而言，下標取值范圍為0 <= low <= high <= max <= len(s)。對切片而言，下標取值范圍為0 <= low <= high <= cap(s)。在切片面試題系列二中正是對此知識點的考察。

切片容量

前面提到此切片表達式可以控制切片的容量。在low一定的情況下，通過改變max在允許范圍內(nèi)的值即可改變切片的容量，其容量計算方式為max - low。

切片擴容

runtime/slice.go文件的growslice函數(shù)實現(xiàn)了切片的擴容邏輯,在正式分析內(nèi)部邏輯之前我們先看看growslice的函數(shù)簽名：

type slice struct { 
 array unsafe.Pointer 
 len   int 
 cap   int 
} 
 
func growslice(et *_type, old slice, cap int) slice 

第一個參數(shù)_type是Go語言類型的運行時表示，其中包含了很多元信息，例如：類型大小、對齊以及種類等。

第二個參數(shù)為待擴容切片的信息。

第三個參數(shù)為真實需要的容量，即原容量和新增元素數(shù)量之和，老許對其簡稱為所需容量。為了更加容易理解所需容量的含義，我們先看一段代碼：

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 

擴容邏輯

有了上面的概念之后，下面我們看看切片擴容算法：

上圖邏輯總結(jié)如下：

首先，如果所需容量大于2倍當前容量則新容量為所需容量。

其次，判斷當前容量是否大于1024。如果當前容量小于1024則新容量等于2倍當前容量。如果當前容量大于等于1024則新容量循環(huán)增加1/4倍新容量直到新容量大于等于所需容量。

老許在這里特別提示，和0的比較是有用的。初始時，老許也覺得這邏輯十分多余，后來有一天突然頓悟，這實際上是對整形溢出的判斷。因為平時開發(fā)中很少會考慮這個問題，一時間驚為天人。也許我們和大神之間的代碼差距僅僅是少了對溢出的判斷。

另外一個有意思的事情是，切片的邏輯最開始也不是這樣的。這邏輯并不復雜，即使是剛?cè)腴T的人寫起來也毫無壓力。然而即便是這樣簡單的邏輯，也是經(jīng)過多個版本的迭代才有了如今的模樣。

有一說一，在老許看來1.6中的擴容邏輯并不算優(yōu)雅。想到這兒，一種“我贏了”的感覺油然而生，程序猿的快樂就是如此簡單。

計算內(nèi)存容量

前文中的擴容邏輯是理想的內(nèi)存分配容量，而真實的內(nèi)存分配十分復雜。在Go1.6中切片擴容分配內(nèi)存時分為四種情況，分別是類型大小為1字節(jié)、類型大小為指針大小、類型大小為2的n次冪和其他。而切片擴容分配內(nèi)存時在不同的Go版本中又略有不同，這里只介紹1.16中類型大小為2的n次冪時內(nèi)存分配。

下面直接上代碼：

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 
} 

上述代碼中，通過對指針大小判斷以區(qū)分當前運行的是32位還是64位平臺。Ctz64和Ctz32函數(shù)是針對不同類型計算最低位0的個數(shù)。又因為類型大小是2的n次冪，則0的個數(shù)即為n。

類型大小為2的n次冪，則類型大小一定為 1 << n，因此計算最低位0的個數(shù)即可得到左移的位數(shù)。

源碼中通過x&(x-1) == 0表達式判斷一個無符號整數(shù)是否為2的n次冪。我們平時開發(fā)中如果有類似的邏輯，請參考切片擴容源碼開始裝逼之旅。

接下來是計算內(nèi)存容量的邏輯：

capmem = roundupsize(uintptr(newcap) << shift) 
newcap = int(capmem >> shift) 

結(jié)合前文易知，uintptr(newcap) << shift實際上可以理解為uintptr(newcap) * et.size，capmem >> shift可理解為capmem / et.size。uintptr(newcap) << shift是最理想的所需內(nèi)存大小，而實際分配內(nèi)存時因為內(nèi)存對齊等問題無法達到理想狀況，所以通過roundupsize計算出實際需要的內(nè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ù)有很多含義不清楚的變量，老許接下來會對其一一解釋。

_MaxSmallSize: 其值為32768，即32kb大小。在Go中，當對象大小超過32kb時，內(nèi)存分配策略和小于等于32kB時是有區(qū)別的。

smallSizeMax: 其值為1024字節(jié)。

smallSizeDiv: 其值為8字節(jié)。

largeSizeDiv: 其值為128字節(jié)。

_PageSize: 8192字節(jié)，即8kb大小。Go按頁來管理內(nèi)存，而每一頁的大小就為8kb。

class_to_size: Go中的內(nèi)存分配會按照不同跨度(也可理解為內(nèi)存大小)將內(nèi)存分割成不同內(nèi)存塊鏈表。當需要分配內(nèi)存時，按照對象大小去匹配最合適的跨度找到空閑的內(nèi)存塊兒。Go中總共分為67個跨度，class_to_size是一個長度為68的數(shù)組，分別記錄0和這67個跨度的值。源碼詳見sruntime/izeclasses.go。

size_to_class8: 這是一個長度為129的數(shù)組，代表的內(nèi)存大小區(qū)間為0~1024字節(jié)。以索引i為例，此位置的對象大小m為i * smallSizeDiv，size_to_class8[i]的值為class_to_size數(shù)組中跨度最接近m的下標。

size_to_class128：這是一個長度為249的數(shù)組，代表的內(nèi)存大小區(qū)間為1024~32768字節(jié)。以索引i為例，此位置的對象大小m為smallSizeMax + i*largeSizeDiv, size_to_class128[i]的值為class_to_size數(shù)組中跨度最接近m的下標。

divRoundUp: 此函數(shù)返回a/b向上舍入最接近的整數(shù)。

alignUp: alignUp(size, _PageSize) = _PageSize * divRoundUp(size, _PageSize)。

最終將計算實際需要內(nèi)存大小的邏輯表示如下：

到這里，切片擴容的核心邏輯就已經(jīng)分析完畢。本篇不對類型大小為1字節(jié)、類型大小為指針大小以及其他大小進行擴容邏輯分析的原因是整體邏輯差別不大。在老許看來源碼中對類型大小區(qū)分的主要目的是為了盡可能減少除法和乘法運算。每每閱讀這些優(yōu)秀的源碼都令老許直呼細節(jié)怪物。

為了加深印象我們以切片面試題系列三中的一個例子進行一次演算。

s3 := []int{1, 2} 
s3 = append(s3, 3, 4, 5) 
fmt.Println(cap(s3)) 

根據(jù)前文知，所需容量為5，又因所需容量大于2倍當前容量，故新容量也為5。

又因為int類型大小為8(等于64位平臺上的指針大小)，所以實際需要的內(nèi)存大小為5 * 8 = 40字節(jié)。而67個跨度中最接近40字節(jié)的跨度為48字節(jié)，所以實際分配的內(nèi)存容量為48字節(jié)。

最終計算真實的容量為48 / 8 = 6，和老許實際運行輸出一致。

最后，衷心希望本文能夠?qū)Ω魑蛔x者有一定的幫助。

注：

寫本文時， 筆者所用go版本為: go1.16.6

文章中所用完整例子：https://github.com/Isites/go-coder/blob/master/slice/main.go