Go 底層探索 -三-: 切片

@注: 以下內容來自《Go 語言底層原理剖析》、《Go 語言設計與實現》書中的摘要信息，本人使用版本 (Go1.18) 與書中不一致，源碼路徑可能會有出入。

1. 介紹

切片是Go語言中非常常用的數據類型之一，使用方式和數組一樣，但是其長度並不固定，我們可以向切片中追加元素，它會在容量不足時自動擴容。

1.1 聲明

在 Go 語言中，切片類型的聲明方式與數組有一些相似，不過由於切片的長度是動態的，所以聲明時只需要指定切片中的元素類型：

[]int
[]interface{}

從切片的定義我們能推測出，切片在編譯期間的生成的類型只會包含切片中的元素類型，即 int 或者 interface{} 等。cmd/compile/internal/types.NewSlice 就是編譯期間用於創建切片類型的函數：

func NewSlice(elem *Type) *Type {
 if t := elem.cache.slice; t != nil {
  if t.Elem() != elem {
   base.Fatalf("elem mismatch")
  }
  if elem.HasTParam() != t.HasTParam() || elem.HasShape() != t.HasShape() {
   base.Fatalf("Incorrect HasTParam/HasShape flag for cached slice type")
  }
  return t
 }

 t := newType(TSLICE)
 t.extra = Slice{Elem: elem}
 elem.cache.slice = t
 if elem.HasTParam() {
  t.SetHasTParam(true)
 }
 if elem.HasShape() {
  t.SetHasShape(true)
 }
 return t
}

上述方法返回結構體中的 Extra 字段是一個只包含切片內元素類型的結構，也就是說切片內元素的類型都是在編譯期間確定的，編譯器確定了類型之後，會將類型存儲在 Extra 字段中幫助程序在運行時動態獲取。

2. 數據結構

編譯期間的切片是 cmd/compile/internal/types.Slice 類型，但是在運行時切片會轉換成 reflect.SliceHeader 結構體，如下:

type SliceHeader struct {
 Data uintptr
 Len  int
 Cap  int
}

• Data 是指向數組的指針;

• Len 是當前切片的長度；

• Cap 是當前切片的容量，即 Data 數組的大小。

2.1 存儲原理

Data 是一片連續的內存空間，這片內存空間可以用於存儲切片中的全部元素，數組中的元素只是邏輯上的概念，底層存儲其實都是連續的，所以我們可以將切片理解成一片連續的內存空間加上長度與容量的標識。如下圖所示:

從上圖中，我們會發現切片與數組的關係非常密切，切片引入了一個抽象層，提供了對數組中部分連續片段的引用，而作爲數組的引用，我們可以在運行區間可以修改它的長度和範圍。當切片底層的數組長度不足時就會觸發擴容，切片指向的數組可能會發生變化，不過在上層看來切片是沒有變化的，上層只需要與切片打交道不需要關心數組的變化。

3. 初始化

Go 語言中包含三種初始化切片的方式：

• 通過下標的方式獲得數組或者切片的一部分；

• 使用字面量初始化新的切片；

• 使用關鍵字 make 創建切片：

arr[0:3] or slice[0:3]
slice := []int{1, 2, 3}
slice := make([]int, 10)

3.1 使用下標

使用下標創建切片是最原始也最接近彙編語言的方式，它是所有方法中最爲底層的一種，編譯器會將 arr[0:3] 或者 slice[0:3] 等語句轉換成 OpSliceMake 操作；我們可以通過下面的代碼來驗證一下：

import "fmt"

func main() {
 arr := [3]int{1, 2, 3}
 slice := arr[0:1]
 fmt.Println(slice)
}
/** 生成SSA
➜  GOSSAFUNC=main go tool compile main.go                         
dumped SSA to /Users/liuqh/ProjectItem/go-app/ssa.html
*/

通過 GOSSAFUNC 變量編譯上述代碼可以得到一系列 SSA 中間代碼，其中 slice := arr[0:1] 語句在 decompose builtin 階段對應的代碼如下圖所示：

SliceMake 操作會接受四個參數創建新的切片，元素類型、數組指針、切片大小和容量，這也是我們在數據結構一節中提到的切片的幾個字段 ，需要注意的是使用下標初始化切片不會拷貝原數組或者原切片中的數據，它只會創建一個指向原數組的切片結構體，所以修改新切片的數據也會修改原切片。

func TestRun(t *testing.T) {
 oldArr := [5]int{1, 2, 3, 4, 5}
 // 使用下標創建切片
 newSlice := oldArr[0:3]
 fmt.Println("修改切片前-> oldArr:", oldArr, "newSlice:", newSlice)
 // 修改新切片值
 newSlice[0] = 100
 fmt.Println("修改切片後-> oldArr:", oldArr, "newSlice:", newSlice)
}
/** 輸出
修改切片前-> oldArr: [1 2 3 4 5] newSlice: [1 2 3]
修改切片後-> oldArr: [100 2 3 4 5] newSlice: [100 2 3]
*/

3.2 使用字面量

當我們使用字面量 []int{1, 2, 3} 創建新的切片時，cmd/compile/internal/gc.slicelit 函數會在編譯期間將它展開成如下所示的代碼片段：

var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice := vauto[:]

對上述代碼分析:

1. 根據切片中的元素數量對底層數組的大小進行推斷並創建一個數組；

2. 將這些字面量元素存儲到初始化的數組中；

3. 創建一個同樣指向 [3]int 類型的數組指針；

4. 將靜態存儲區的數組 vstat 賦值給 vauto 指針所在的地址；

5. 通過 [:] 操作獲取一個底層使用 vauto 的切片；

第 5 步中的 [:] 就是使用下標創建切片的方法，從這一點我們也能看出 [:] 操作是創建切片最底層的一種方法。

3.3 使用 make

如果使用字面量的方式創建切片，大部分的工作都會在編譯期間完成。但是當我們使用 make 關鍵字創建切片時，很多工作都需要運行時的參與；調用方必須向 make 函數傳入切片的大小以及可選的容量，

類型檢查期間的 cmd/compile/internal/gc.typecheck1 函數會校驗入參:

func typecheck1(n *Node, top int) (res *Node) {
 switch n.Op {
 ...
 case OMAKE:
  args := n.List.Slice()

  i := 1
  switch t.Etype {
      // 類型是切片
  case TSLICE:
   if i >= len(args) {
    yyerror("missing len argument to make(%v)", t)
    return n
   }

   l = args[i]
   i++
   var r *Node
   if i < len(args) {
    r = args[i]
   }
   ...
      // 切片大小len,不能超過容量cap
   if Isconst(l, CTINT) && r != nil && Isconst(r, CTINT) && l.Val().U.(*Mpint).Cmp(r.Val().U.(*Mpint)) > 0 {
    yyerror("len larger than cap in make(%v)", t)
    return n
   }

   n.Left = l
   n.Right = r
   n.Op = OMAKESLICE
  }
 ...
 }
}

上述函數不僅會檢查 len 是否傳入，還會保證傳入的容量 cap 一定大於或者等於 len。除了校驗參數之外，當前函數會將 OMAKE 節點轉換成 OMAKESLICE，中間代碼生成的 cmd/compile/internal/gc.walkexpr 函數會依據下面兩個條件轉換 OMAKESLICE 類型的節點：

1. 切片的大小和容量是否足夠小；

2. 切片是否發生了逃逸，最終在堆上初始化;

當切片發生逃逸或者非常大時，運行時需要 runtime.makeslice 在堆上初始化切片，如果當前的切片不會發生逃逸並且切片非常小的時候, 那麼切片運行時最終會被分配在棧中。

此臨界值定義在cmd/compile/internal/ir.MaxImplicitStackVarSize變量中，默認爲64KB，可以通過指定編譯時smallframes標識進行更新，因此，make（[]int64，1023）與make（[]int64，1024）實現的細節是截然不同的。

4. 擴容原理

4.1 擴容觸發

關鍵字append是觸發切片擴容的主要方式，但不是每次使用append函數就一定會擴容，看下面代碼示例：

func main() {
  // --------- 不會擴容 ---------
 // 定義切片a,容量爲4
 a := make([]int, 3, 4)
 fmt.Printf("append前,a-> len:%v cap:%v value:%v \n", len(a), cap(a), a)
 a = append(a, 1)
 fmt.Printf("append後,a-> len:%v cap:%v value:%v \n", len(a), cap(a), a)

  // --------- 會擴容 ---------
 // 定義切片b，容量爲3
 b := make([]int, 3, 3)
 fmt.Printf("append前,b-> len:%v cap:%v value:%v \n", len(b), cap(b), b)
 b = append(b, 1)
 fmt.Printf("append後,b-> len:%v cap:%v value:%v \n", len(b), cap(b), b)
}
/** 輸出
append前,a-> len:3 cap:4 value:[0 0 0] 
append後,a-> len:4 cap:4 value:[0 0 0 1] 
append前,b-> len:3 cap:3 value:[0 0 0] 
append後,b-> len:4 cap:6 value:[0 0 0 1] 
*/

代碼分析:

• 切片a容量爲 4，目前長度爲 3(初始化3個0)，所以還能再容納一個元素，在執行append時，不會執行擴容，所以cap還是 4；

• 切片b容量爲 3，目前長度也爲 3(初始化3個0)，如果再append, 切片容量會不足，便會進行擴容。所以cap爲 6，至於爲什麼是 6，看後續源碼分析；

4.2 容量判定

當切片的容量不足時，append函數在運行時會調用 runtime.growslice 函數爲切片擴容；

擴容是爲切片分配新的內存空間, 並拷貝原切片中元素到新空間的過程。

runtime.growslice 源碼如下:

func growslice(et *_type, old slice, cap int) slice {
 newcap := old.cap
 doublecap := newcap + newcap
 if cap > doublecap {
    // 如果新申請容量cap大於2倍的舊容量old.cap，則最終容量newcap是新申請的容量cap
  newcap = cap
 } else {
  if old.len < 1024 {
      // 如果舊切片的長度小於1024，則最終容量是舊容量的2倍
   newcap = doublecap
  } else {
      // 如果舊切片長度大於或等於1024,
   for 0 < newcap && newcap < cap {
        // 則最終容量從舊容量開始循環增加原來的1/4,直到最終容量大於或等於新申請的容量爲止
    newcap += newcap / 4
   }
      // 容量計算值溢出,則最終容量就是新申請容量
   if newcap <= 0 {
    newcap = cap
   }
  }
 }

上面的代碼顯示了擴容的核心邏輯，Go語言中切片擴容的策略整理如下：

• 如果新申請容量（cap）大於 2 倍的舊容量（old.cap），則最終容量（newcap）是新申請的容量（cap）。

• 如果舊切片的長度小於1024，則最終容量是舊容量的 2 倍，即newcap=doublecap。

• 如果舊切片長度大於或等於 1024，則最終容量從舊容量開始循環增加原來的1/4, 直到最終容量大於或等於新申請的容量爲止, 即newcap ≥ cap。

• 如果最終容量計算值溢出，即超過了 int 的最大範圍，則最終容量就是新申請容量。

growslice函數會根據切片的類型，分配不同大小的內存。爲了對齊內存，申請的內存可能大於實際的類型大小×容量大小。

5. 切片複製

5.1 代碼示例

先看一段代碼，試着分析會輸出什麼？

func TestCopySlice(t *testing.T) {
 // 定義切片
 oldSli := []int{100, 200, 300}
 // 複製切片
 copySli := oldSli
 fmt.Println("修改前->copySli:", copySli, "oldSli:", oldSli)
 // 修改複製後的切片
 copySli[0] = 99
 fmt.Println("修改後->copySli:", copySli, "oldSli:", oldSli)
}

輸出:

// 修改前->copySli: [100 200 300] oldSli: [100 200 300]
// 修改後->copySli: [99 200 300] oldSli: [99 200 300]

切片的複製其實也是值複製，但這裏的值複製指對於運行時SliceHeader結構的複製, 但底層指針仍然指向相同的底層數據的數組地址，因此可以理解爲數據進行了引用傳遞。如下圖所示:

切片的這一特性使得即便切片中有大量數據，在複製時的成本也比較小，這與數組有顯著的不同。

5.2 使用 Copy

複製的切片不會改變指向底層的數據源，但有些時候我們希望建一個新的數組，並且與舊數組不共享相同的數據源, 這時可以使用copy函數。

還是上面的示例, 修改使用copy：

func TestCopySlice(t *testing.T) {
 // 定義切片
 oldSli := []int{100, 200, 300}
 // 使用copy複製切片
 copySli := make([]int, len(oldSli), cap(oldSli))
 copy(copySli, oldSli)
 fmt.Println("修改前->copySli:", copySli, "oldSli:", oldSli)
 // 修改複製後的切片
 copySli[0] = 99
 fmt.Println("修改後->copySli:", copySli, "oldSli:", oldSli)
}

輸出:

// 修改前->copySli: [100 200 300] oldSli: [100 200 300]
// 修改後->copySli: [99 200 300] oldSli: [100 200 300]

copy函數在運行時主要調用了memmove函數，用於實現內存的複製。如果採用協程調用的方式go copy（numbers1，numbers）或者加入了race檢測，則會轉而調用運行時runtime.slicecopy函數；無論是編譯期間拷貝還是運行時拷貝，兩種拷貝方式都會通過 runtime.memmove 將整塊內存的內容拷貝到目標的內存區域中

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OvYoZ-3TdJluLP6MwdGeoQ