【1-2 Golang】Go語言快速入門—陣列與切片

語言: CN / TW / HK

  陣列和切片是Go語言提供的兩種基本資料結構,陣列的概念大家應該都很熟悉,相同型別元素的集合,且元素在記憶體中連續儲存,可以非常方便的通過下標訪問陣列元素;那麼什麼是切片呢?切片可以理解為動態陣列,也就是說陣列長度(最大可以儲存的元素數目)可以動態調整。切片是我們日常開發最常用的資料結構之一,應該重點學習。

陣列

  陣列的定義與使用非常簡單,如下面例項所示:

package main

import "fmt"

func main() {
  var arr [3]int
  //陣列訪問
  arr[0] = 100
  arr[1] = 200
  arr[2] = 300

  //arr最大可以儲存三個整數,下標從0開始,最大為2
  //Invalid array index 3 (out of bounds for 3-element array);訪問越界,無法編譯通過
  //arr[3] = 400

  fmt.Println(len(arr), arr) //len返回陣列長度

  var arr1 [5]int
  //陣列的型別包括:元素型別 + 陣列長度,任意一項不等,說明陣列型別不同,無法相互賦值
  //Cannot use 'arr' (type [3]int) as type [5]int
  //arr1 = arr
  fmt.Println(arr1)
}

  在使用陣列過程中,需要重點注意下標最大值為len - 1,不要出現訪問越界情況。Go語言陣列和C語言陣列使用非常類似,但是在陣列作為函式引數使用時候,還是有些許不同的。

  首先要明確一點的是,Go語言函式傳參都是傳值的(輸入引數會拷貝一份),而不是傳遞引用(輸入引數的地址),因此雖然你在函式內部修改了輸入引數,但是呼叫方變數並沒有改變,如下面事例:

package main

import "fmt"

func main() {
  arr := [6]int{1,2,3,4,5,6}
  testArray(arr)
  fmt.Println(arr)  //原陣列未發生修改:[1 2 3 4 5 6]
}

func testArray(arr [6]int) {
  arr[0] = 0
  arr[5] = 500
  fmt.Println(arr) //修改陣列元素:[0 2 3 4 5 500]
}

  學習過C語言陣列的夥伴可能會比較納悶,C語言在這種情況下,呼叫方陣列元素是會同步發生改變的。Go語言是怎麼做到的呢?上面說過,Go語言函式傳參都是傳值的,所以Go語言會把陣列所有元素全部拷貝一份,這樣函式內部修改的陣列就和原陣列沒有任何關係了。

  我們可以簡單看看Go語言彙編程式碼,Go語言本身提供有編譯工具:

//-N 禁止優化 -l 禁止內聯 -S 輸出彙編
go tool compile -S -N -l test.go

"".main STEXT size=125 
  //MOVQ 拷貝8位元組資料
  0x0026 00038 (test.go:6)  MOVQ  $1, "".arr+48(SP)
  0x002f 00047 (test.go:6)  MOVQ  $2, "".arr+56(SP)
  0x0038 00056 (test.go:6)  MOVQ  $3, "".arr+64(SP)
  0x0041 00065 (test.go:6)  MOVQ  $4, "".arr+72(SP)
  0x004a 00074 (test.go:6)  MOVQ  $5, "".arr+80(SP)
  0x0053 00083 (test.go:6)  MOVQ  $6, "".arr+88(SP)
  //MOVUPS 拷貝16位元組陣列,陣列6個元素拷貝三次
  0x005c 00092 (test.go:7)  MOVUPS  "".arr+48(SP), X0
  0x0061 00097 (test.go:7)  MOVUPS  X0, (SP)
  0x0065 00101 (test.go:7)  MOVUPS  "".arr+64(SP), X0
  0x006a 00106 (test.go:7)  MOVUPS  X0, 16(SP)
  0x006f 00111 (test.go:7)  MOVUPS  "".arr+80(SP), X0
  0x0074 00116 (test.go:7)  MOVUPS  X0, 32(SP)
  0x0079 00121 (test.go:7)  CALL  "".testArray(SB)
  ……

"".testArray STEXT nosplit 
  0x000f 00015 (test.go:11) SUBQ  $136, SP

  0x0026 00038 (test.go:12) MOVQ  $0, "".arr+144(SP)
  0x0032 00050 (test.go:13) MOVQ  $500, "".arr+184(SP)

  不要被彙編兩個字嚇到,只要瞭解虛擬記憶體結構(重點函式棧楨結構),瞭解暫存器概念,瞭解一些常見指令含義,上面邏輯就非常清楚了。"CALL testArray"就是函式呼叫,其上面幾條指令就是引數準備,可以很明顯看到引數是對原陣列的一個拷貝。上述事例棧楨結構如下圖所示:

切片

  切片可以理解為動態陣列,基本使用和陣列比較類似,都是連續儲存,可以按下標訪問;動態的含義是,切片的容量是可以調整的,往切片追加元素時,Go語言底層判斷陣列容量是否足夠,如果不夠則觸發擴容操作。

基本操作

  我們先看一個小事例,以此瞭解切片的初始化、訪問、追加元素等基本操作,以及切片的長度以及容量:

package main

import "fmt"

func main() {
  //宣告並初始化切片
  slice := []int{1,2,3}
  slice[0] = 100
  //len:切片長度,即切片儲存了幾個元素;cap:切片容量,即切片底層陣列最多能儲存元素數目
  fmt.Println(len(slice), cap(slice), slice) //上述宣告方式,切片長度/容量都等於3: 3 3 [100 2 3]

  //往切片追加元素,注意切片slice容量是3,此時追加元素會觸發擴容操作
  slice = append(slice, 4)
  fmt.Println(len(slice), cap(slice), slice) //切片已經擴容,此時容量是6(一般按雙倍容量擴容): 4 6 [100 2 3 4]

  //切片的容量雖然是6,但長度是4,訪問下標5越界
  //slice[5] = 5 //panic: runtime error: index out of range [5] with length 4

  //也可以基於make函式宣告切片;第二個引數為切片長度,第三個引數為切片容量(可以省略,預設容量等於長度)
  slice1 := make([]int, 4, 8)
  slice1[1] = 1
  slice1[2] = 2
  fmt.Println(len(slice1), cap(slice1), slice1) //4 8 [0 1 2 0]

  //切片遍歷訪問
  for idx, v := range slice {
    printSliceValue(idx, v)  //printSliceValue自己隨便定義就行
  }
}

  函式len用於獲取切片長度,cap用於獲取切片容量;切片長度指切片元素數目,訪問下標最大為len - 1,切片容量指切片底層陣列最多能儲存的元素數目;append函式用於往切片追加元素,該函式會判斷切片容量,如果容量不夠則觸發擴容操作,一般按照容量兩倍擴容。make是Go語言提供的變數初始化函式,可用於初始化一些內建型別變數,如切片,map,管道chan等。

  我們可以通過for range方式遍歷切片,range可以獲取當前遍歷元素的索引以及元素值,那麼問題來了,遍歷過程中修改元素值,切片的元素會修改嗎?如下面的事例:

package main

import "fmt"

func main() {
  slice := make([]int, 10, 10)
  for i := 0; i < 10; i ++ {
    slice[i] = i
  }

  for idx, v := range slice {
    v += 100
    printSliceValue(idx, v)
  }

  fmt.Println(slice)   //輸出 [0 1 2 3 4 5 6 7 8 9]
}

func printSliceValue(idx, val int) {
  fmt.Println(idx, val)
}

  顯而易見,這麼修改元素v的值,切片slice的元素不會改變。為什麼呢?因為這裡索引值v只是切片元素的一個拷貝,修改副本值,原值肯定是不會改變的。那麼想在遍歷中修改切片的值怎麼辦?可以通過slice[idx]形式修改,這樣訪問到的才是切片原值。

  切片還有一個常見操作:擷取,即擷取該切片的一部分生成一個新的切片,語法格式為"slice[start:end]",start與end均表示下標,左開又閉(新切片包括下標start元素,不包含下標end元素),新切片長度為end - start。

package main

import "fmt"

func main() {
  slice := []int{1,2,3,4,5,6,7,8,9,10}
  //切片擷取
  slice1 := slice[2:5]
  //修改新切片slice1元素,slice元素會改變嗎?
  slice1[0] = 100
  fmt.Println(len(slice), cap(slice), slice)
  fmt.Println(len(slice1), cap(slice1), slice1)

  //slice1追加多個元素,超過其cap觸發擴容
  slice1 = append(slice1, 11,12,13,14,15,16,17,18,19,20,21,22)
  //再次修改slice1元素,slice元素會改變嗎?
  slice1[0] = 200
  fmt.Println(len(slice), cap(slice), slice)
  fmt.Println(len(slice1), cap(slice1), slice1)
}

/**
輸出:
10 10 [1 2 100 4 5 6 7 8 9 10]
3 8 [100 4 5]

10 10 [1 2 100 4 5 6 7 8 9 10]
15 16 [200 4 5 11 12 13 14 15 16 17 18 19 20 21 22]
**/

  分析輸出結構,通過擷取生成新切片slice1之後,修改slice1元素,slice元素竟然也被改變了!這是為什麼呢?因為切片底層也是基於陣列實現,擷取後兩個切片共用同一個底層陣列,所以修改元素才會互相影響。那為什麼append觸發擴容之後,又不影響了呢?因為擴容會申請新的陣列,也就是說slice1底層陣列變了,與slice底層陣列剝離了,此時修改元素肯定不會互相影響了。

  另外注意,slice1 := slice[2:5]擷取切片後,slice長度是3,但是容量是8;因為slice1與slice共用底層陣列,而底層陣列最大容量是10,但是slice1卻是從底層陣列索引2開始,所以slice1的容量就是10 - 2 = 8 了。

  最後我們再思考一個問題,前面我們介紹陣列在傳遞的時候是按值傳遞,函式內部修改陣列元素,呼叫方陣列並沒有改變?那麼切片呢?我們需要牢記一點,Go語言傳參都是按值傳遞的?那就是了,切片和陣列一樣,也不會改變。是這樣嗎?我們用一個小事例驗證下:

package main

import "fmt"

func main() {
  slice := make([]int, 2, 10)
  slice[0] = 1
  slice[1] = 2
  fmt.Println(len(slice), cap(slice), slice)   //初始切片長度2,容量10:2 10 [1 2]

  testSlice(slice)
  fmt.Println(len(slice), cap(slice), slice)   //切片長度容量都沒有改變,但是切片元素改變了:2 10 [100 200]
}

func testSlice(slice []int) {
  slice[0] = 100
  slice[1] = 200
  slice = append(slice, 300)
  fmt.Println(len(slice), cap(slice), slice) //修改切片元素,並追加一個元素,切片長度3,容量10:3 10 [100 200 300]
}

  貌似和猜想的不一樣啊,testSlice函式中修改了切片元素,main函式中slice切片元素也同步改變了;而testSlice函式追加元素,改變了切片長度,但是main函式中slice切片長度卻沒有改變。why?Go語言傳參到底是傳值還是傳引用呢?Go語言確實是按值傳參的。長度和容量都是切片的值,所以即使testSlice函式修改了main函式中也不會改變,但是底層陣列卻是共用的,testSlice函式修改了main函式中會同步修改。

  看到這裡可能你還是有些迷惑,不用擔心,學習下一小節切片實現原理之後,相信你會恍然大悟。

實現原理

  我們一直說切片就是動態陣列,這是怎麼做到動態的呢?都知道陣列是連續記憶體儲存的,所以想追加元素非常麻煩,需要申請更大的連續記憶體空間,拷貝所有陣列元素,效能非常大。切片也是基於陣列實現的,只不過採取預分配策略,一般切片的容量都比切片長度大,這樣再往切片追加元素時,就可以避免記憶體分配以及資料拷貝。這樣一來,切片也需要記錄更多的資訊:如陣列首地址,用於儲存元素;容量,記錄底層陣列最多可以儲存的元素數目;長度,記錄已經儲存的元素數目。容量減長度,就是陣列剩餘長度了,即該切片在觸發擴容之前,還能追加的元素數目。

  切片的定義在runtime/slice.go檔案,如下:

type slice struct {
  array unsafe.Pointer
  len   int
  cap   int
}

  和我們猜測的一樣,切片包含三個欄位,其實array是一個指標,指向底層陣列收地址。該檔案還定義了一些常用的切片操作函式:

//make建立切片底層實現
func makeslice(et *_type, len, cap int) unsafe.Pointer
//切片追加元素時,容量不足擴容實現方法
func growslice(et *_type, old slice, cap int) slice
//切片資料拷貝
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int

  當我們使用make函式建立切片型別時,底層就是呼叫makeslice函式分配陣列,其中第一個引數type表示切片儲存的元素型別,因此陣列所需記憶體大小應該是元素大小乘陣列容量。makeslice函式實現非常簡單,如下:

func makeslice(et *_type, len, cap int) unsafe.Pointer {
  //math.MulUintptr返回a * b,同時判斷是否發生溢位
  mem, overflow := math.MulUintptr(et.size, uintptr(cap))
  
  //省略了一些引數校驗邏輯

  return mallocgc(mem, et, true) //mallocgc函式用於分配記憶體,第三個引數表示是否初始化記憶體為全零
}

  函式makeslice好像只是申請了切片底層陣列記憶體,那麼結構體slice中的其他欄位呢?怎麼維護呢?函式引數傳遞切片時,傳遞的到底是什麼呢?這就需要我們分析彙編程式碼了。Go程式如下:

package main

import "fmt"

func main() {
  slice := make([]int, 4, 10)
  slice[0] = 100
  printInt(len(slice))
  printInt(cap(slice))

  testSlice(slice)
}

func printInt(a int) {
  fmt.Println(a)
}

func testSlice(slice []int) {
  fmt.Println(slice)
}

  編譯後的彙編程式碼如下:

"".main STEXT size=153
  //makeslice第一個引數是型別指標,這裡就是type.int
  0x0018 00024 (test.go:6)  LEAQ  type.int(SB), AX
  //準備第二個引數
  0x001f 00031 (test.go:6)  MOVL  $4, BX
  //準備第三個引數
  0x0024 00036 (test.go:6)  MOVL  $10, CX
  //函式呼叫;函式返回值即陣列首地址,在AX暫存器
  0x0029 00041 (test.go:6)  CALL  runtime.makeslice(SB)
  //下面三行彙編是構造slice結構:陣列首地址 + len + cap
  0x002e 00046 (test.go:6)  MOVQ  AX, "".slice+32(SP)
  0x0033 00051 (test.go:6)  MOVQ  $4, "".slice+40(SP)
  0x003c 00060 (test.go:6)  MOVQ  $10, "".slice+48(SP)

  //AX暫存器儲存陣列首地址,即賦值slice[0] = 100
  0x0047 00071 (test.go:7)  MOVQ  $100, (AX)

  //+40(SP)即切片的len,拷貝到AX暫存器作為引數傳遞
  0x004e 00078 (test.go:8)  MOVQ  "".slice+40(SP), AX
  0x0053 00083 (test.go:8)  MOVQ  AX, ""..autotmp_1+24(SP)
  0x0058 00088 (test.go:8)  CALL  "".printInt(SB)

  //+48(SP)即切片的cap,拷貝到AX暫存器作為引數傳遞
  0x005d 00093 (test.go:9)  MOVQ  "".slice+48(SP), AX
  0x0062 00098 (test.go:9)  MOVQ  AX, ""..autotmp_1+24(SP)
  0x0067 00103 (test.go:9)  CALL  "".printInt(SB)

  //拷貝slice結構:陣列首地址 + len + cap,建構函式testSlice輸入引數
  0x006c 00108 (test.go:11) MOVQ  "".slice+32(SP), AX
  0x0071 00113 (test.go:11) MOVQ  "".slice+40(SP), BX
  0x0076 00118 (test.go:11) MOVQ  "".slice+48(SP), CX
  0x0080 00128 (test.go:11) CALL  "".testSlice(SB)

  函式輸入引數可以在棧上,也可以使用暫存器傳遞輸入引數,比如上述程式碼,AX是第一個輸入引數,BX、CX依次是第二個、第三個輸入引數;函式返回值也是既可以在棧上,也可以使用暫存器,上面程式碼使用AX暫存器作為第一個返回值。

  畢竟slice結構非常簡單明瞭,三個8位元組,陣列首地址 + len + cap,所以可以很方便的通過彙編程式碼構造。而len(slice)獲取切片長度,cap(slice)獲取切片容量更是簡單,slice地址偏移8位元組、16位元組就是了。

  另外注意testSlice函式呼叫,拷貝了slice結構作為函式引數,底層陣列呢?肯定還是共用的,所以在函式testSlice內部修改了切片元素,呼叫方也會同步修改;而在函式testSlice內部append觸發的擴容,卻不回影響呼叫方切片的len以及cap。這也解決了我們上一小節留下的一些疑惑。

  上述事例示意圖如下所示:

擴容

  append用於往切片追加元素,其底層實現會判斷切片容量,如果容量不足,則觸發擴容。append通常有兩種寫法:1)追加一個切片到另一個切片;2)追加元素到一個切片。如下面事例所示:

package main

import "fmt"

func main() {
  slice := make([]int, 0, 100)
  slice = append(slice, 10, 20, 30)

  slice1 := []int{1, 2, 3}
  slice = append(slice, slice1...)
  
  fmt.Println(slice,slice1) //[10 20 30 1 2 3] [1 2 3]
}

  append函式實現在哪呢?如果你檢視runtime/slice.go檔案,會發現好像沒有appendslice函式,倒是有growslice切片擴容的實現。append函式其實是編譯階段生成的,並沒有原始碼,這裡直接給出兩種寫法下的核心邏輯:

//參考1:cmd/compile/internal/walk/assign.go:appendSlice
//參考2:cmd/compile/internal/walk/builtin.go:walkAppend

// expand append(l1, l2...) to
//   init {
//     s := l1
//     n := len(s) + len(l2)
//     // Compare as uint so growslice can panic on overflow.
//     if uint(n) > uint(cap(s)) {
//       s = growslice(s, n)
//     }
//     s = s[:n]
//     memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
//   }


// Rewrite append(src, x, y, z) 
//   init {
//     s := src
//     const argc = len(args) - 1
//     if cap(s) - len(s) < argc {
//      s = growslice(s, len(s)+argc)
//     }
//     n := len(s)
//     s = s[:n+argc]
//     s[n] = a
//     s[n+1] = b
//     ...
//   }

  可以看到,在容量不足時,都是通過growslice來擴容的。函式growslice在切片容量較小時,按照兩倍擴容;切片容量較大時,擴容25%。確定切片容量後,就是申請記憶體,同時拷貝切片資料到新陣列。有興趣的讀者可以研究下growslice函式的原始碼。

拷貝

  最後我們再探索一個問題:不管是切片的擷取,傳參等,底層陣列初始都是共用的,修改一個切片的元素必然影響另一個切片,有沒有辦法實現切片的完全拷貝呢?拷貝後兩個切片陣列也是隔離的,互不影響。這種完全拷貝可以基於Go語言內建函式copy實現:

package main

import "fmt"

func main() {
  slice := []int{1,2,3,4,5}
  slice1 := make([]int, len(slice), 10)
  copy(slice1, slice)

  slice1[0] = 100
  fmt.Println(slice, slice1)
}

/**
  [1 2 3 4 5] [100 2 3 4 5]
**/

  可以看到,修改切片slice1元素之後,slice切片元素沒有發生改變。這裡又有疑問了,copy函式的實現邏輯是怎樣的呢?是runtime/slice.go檔案中的slicecopy函式嗎?只能說不完全是,Go語言在編譯階段判斷,如果切片元素型別包括指標,則copy對應typedslicecopy函式;如果需要一些執行時變數,則copy對應slicecopy函式;否則編譯階段直接生成彙編程式碼,這裡直接給出該彙編程式碼的核心邏輯:

//參考:cmd/compile/internal/walk/builtin.go:walkCopy

// Lower copy(a, b) to a memmove call or a runtime call.
//
// init {
//   n := len(a)
//   if n > len(b) { n = len(b) }
//   if a.ptr != b.ptr { memmove(a.ptr, b.ptr, n*sizeof(elem(a))) }
// }

總結

  到這裡陣列和切片的基本上算是講解完畢了,是不是沒想到竟然有這麼多細節點需要注意。陣列的按值傳參一定要記得,切片的slice結構定義一定要清楚,結合該結構定義,思考切片的擷取,傳參,擴容等現象,應該就比較好理解了。