Golang Slice 介紹、使用方式和 growslice 擴容

定義

Array 是 Golang 的原生型別，其長度固定。

Slice 是 Golang 中長度可以變動的資料型別，也就是可以隨意修改長度的 Array。

其中，Slice 會包含 Pointer、Capacity、Length，Pointer 負責指向實際底層的 Array 位址；Capacity 則是目前 Slice 的容量；Length 則是目前 Slice 內有多少元素在裏頭的長度。

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

宣告方式

[]T
make([]T, len, cap)

1. 普遍使用 make([]type, len, cap)，cap 通常會在宣告的時候被忽略。
2. 直接定義明確資料，[]string{"Alice", "Bob"}。
3. 宣告一個空 Slice，var member []string。

如果 Capacity 沒有被定義，那麼它會與 Length 一樣，並且會先給定初始值。
可以使用 len() 來查看 Slice 內的長度，cap() 則是查看 Slice 內的容量。

// 法一 make([]type, len, cap)
// 宣告一個存放 string 的 Slice，長度和容量都會是 4
s := make([]string, 4) // len=4, cap=4, value=["", "", "", ""]
fmt.Printf("slice s: len=%v, cap=%v, value=%v\n", len(s), cap(s), s)

// 長度 0，容量是 8
s1 := make([]string, 0, 8) // len=0, cap=8, value=[]
fmt.Printf("slice s1: len=%v, cap=%v, value=%v\n", len(s1), cap(s1), s1)

// 法二 定義明確資料
s2 := []string{"Alice", "Bob"}  // len=2, cap=2, value=["Alice" "Bob"]
fmt.Printf("slice s2: len=%v, cap=%v, value=%v\n", len(s2), cap(s2), s2)

// 法三 宣告空 Slice
var s3 []string  // len=0, cap=0, value=[]
fmt.Printf("slice s3: len=%v, cap=%v, value=%v\n", len(s3), cap(s3), s3)

基本操作

長度調整

使用 slice[start:end:max] 的方式來去對 Slice 長度進行修改，範圍將會是 [start,end)，end 則不會被納入範圍內，並且通常不會用到 max ，除非你想對 Capacity 進行調整。

一旦 Slice 被修改，底層的 Array 元素也會一同被修改。

arr := [4]string{"a","b","c","d"} // len=4, cap=4, value=[a b f d]
s := arr[2:3] // len=1, cap=2, value=[c]
s[0] = "f" // len=1, cap=2, value=[f]，此時底層 array 已經變成 [a b f d]

// 忽略 start 或 end，代表從頭取 或是 取至尾端
s2 := arr[:2] // len=2, cap=4, value=[a b]
s3 := arr[2:] // len=2, cap=2, value=[f d]

// 如果再使用 Slice 長度調整時，想要去調整容量，才會使用到 max
s4 := arr[:2:3] // len=2, cap=3, value=[a b]

上述的 s2、s3 變數可以看到為什麼明明都是取一樣的長度，可是容量卻不一樣呢?

因為 Slice 是以 start 開始到 原陣列長度 作為其容量大小的預留記憶體，也就是說如果今天有一個 [8]int 要取 array[4:6] 那麼到最後，len 會是 2，則 cap 會是 4。

Append

func append(s []T, x ...T) []T

對 Slice 進行元素的向後新增，一旦 容量小於 append 後整體的長度，Slice 就會自行擴容，重新宣告一個原本 2 倍 容量大小，將原本的空間 copy 至新的 Slice。

s := make([]int, 0, 1) // [] len=0 cap=1
s = append(s, 1) // [1] len=1 cap=1
s = append(s, 1) // [1 1] len=2 cap=2
s = append(s, 1) // [1 1 1] len=3 cap=4

Copy

func copy(dst, src []T) int

將原本 Slice 的值，深拷貝到另外一個 Slice，return 為已被複製的數量。

如果當 cloneScores 容量大於 scores 複製過來的元素長度，剩下多的空間則是會以 0 來補。
如果當 cloneScores 容量小於 scores 複製過來的元素長度，最多就是當前容量 而 不會擴容，多的元素會被忽略。

func main() {
  scores := []int{1, 2, 3, 4, 5}

  // cloneScores 容量大於 scores 複製過來的元素長度
  cloneScores := make([]int, 4)
  copy(cloneScores, scores[:len(scores)-2])
  fmt.Println(cloneScores) // [1,2,3,0]

  // cloneScores 容量小於 scores 複製過來的元素長度
  cloneScores2 := make([]int, 3)
  copy(cloneScores2, scores)
  fmt.Println(cloneScores2) // [1,2,3]
}

Range

用來遍歷 Slice 所使用的關鍵字，提供 key 和 value，如果某一個值不需要使用到，可以使用 _ 來代替。

func main() {
  pow := []int {1, 2, 4, 8}

  for key, value := range pow {
    fmt.Printf("2**%d = %d\n", key , value)
  }

  // for _, value := range pow {...}

  // for key, _:= range pow {...}
}
// 結果
// 2**0 = 1
// 2**1 = 2
// 2**2 = 4
// 2**3 = 8

growslice 擴容

為了更好地去了解 Slice 的擴容原理，我寫了一個 for 迴圈在 Go Playground ，來看看到底是不是原始碼所寫的那樣，測試程式碼邏輯是每次只要 Slice 長度等於容量時，就會去打印當前的長度與容量。

func main() {
  s := make([]int, 0, 1) // [] len=0 cap=1

  for i := 0; i < 2048; i++ {
    s = append(s, 1)
    if len(s) == cap(s) {
      fmt.Printf("slice s: len=%v, cap=%v\n", len(s), cap(s))
    }
  }
}
// len=1, cap=1
// len=2, cap=2
// len=4, cap=4
// len=8, cap=8
// len=16, cap=16
// len=32, cap=32
// len=64, cap=64
// len=128, cap=128
// len=256, cap=256
// len=512, cap=512
// len=848, cap=848
// len=1280, cap=1280
// len=1792, cap=1792

結果非常出乎意料，竟然在容量 512 要進行擴容時，擴充成 848，於是我去翻找了原始碼中的 runtime.growslice 函數做了什麼：

//  oldPtr = array 的指標位址
//  newLen = 新的 Slice 長度 (= oldLen + num)
//  oldCap = 原始的 Slice 容量
//     num = 被 append 的數量
//      et = Slice 內的型別
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice { ... }

發現在進行擴容時會有三大步驟：

1. 初步確認擴容大小
2. 記憶體對齊
3. 重新分配新的記憶體，並將新舊 Slice 資料複製

初步確認擴容大小

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
  oldLen := newLen - num

  // 略...

  // 如果資料型別的大小是 0，那就會進入此邏輯
  // 這邊會返回一個 Slice 指針會指向一個全域的 zerobase 位址
  if et.Size_ == 0 {
    // append should not create a slice with nil pointer but non-zero len.
    // We assume that append doesn't need to preserve oldPtr in this case.
    return slice{unsafe.Pointer(&zerobase), newLen, newLen}
  }

  // 計算新的 Slice 長度
  newcap := nextslicecap(newLen, oldCap)

  // 略...
}

這邊我舉出兩個資料型別大小為 0 範例，空 Slice 和 struct 型別的 Slice：

type empty struct{}

func main() {
  slice1 := []empty{empty{}, empty{}}
  slice2 := []empty{}
  slice3 := []int{}
  slice4 := []int{10}
  fmt.Println(slice1, len(slice1), cap(slice1))
  fmt.Println(slice2, len(slice2), cap(slice2))
  fmt.Println(slice3, len(slice3), cap(slice3))
  fmt.Println(slice4, len(slice4), cap(slice4))

  fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice1)).Data)
  fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice2)).Data)
  fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice3)).Data)
  fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice4)).Data)
}
// [{} {}] 2 2
// [] 0 0
// [] 0 0
// [10] 1 1
// 54e3a0
// 54e3a0
// 54e3a0
// c000012028

根據 1.22 版本的 runtime.nextslicecap：

// newLen = 新的 Slice 長度 (= oldLen + num)
// oldCap = 原始的 Slice 容量
func nextslicecap(newLen, oldCap int) int {
  // 如果新的 Slice 長度 (newLen) > 兩倍的容量 (2 * oldCap)，新的容量就會是 newLen
  newcap := oldCap
  doublecap := newcap + newcap
  if newLen > doublecap {
    return newLen
  }

  // 常數閥值
  const threshold = 256
  // 在原始的 Slice 容量 < 256 時，就會返回兩倍的容量
  if oldCap < threshold {
    return doublecap
  }
  for {
    // 每次增加 25% 的原始容量 + 額外的 192
    newcap += (newcap + 3*threshold) >> 2

    // 確保新的容量 >= 新的長度，否則就會在累加一次
    if uint(newcap) >= uint(newLen) {
      break
    }
  }

  // 因為 newcap 會重複被累加，如果 newcap overflow 就直接返回與長度一樣的容量
  if newcap <= 0 {
    return newLen
  }
  return newcap
}

而在 1.18 版本以前計算方式則不太一樣：

newcap := old.cap
doublecap := newcap + newcap
// 如果期望容量 (cap) > 兩倍的容量 (2 * oldCap)，新的容量就會是 cap
// 這邊 cap 其實等於 1.22 版本的 newLen
if cap > doublecap {
  newcap = cap
} else { // 如果期望容量沒有超過 2 倍
  if old.len < 1024 { // 如果原始容量 < 1024，新容量就是 2 倍
    newcap = doublecap
  } else { // 如果原始容量 >= 1024，新容量就會累加 25%，直到 >= 期望容量
    for newcap < cap {
      newcap += newcap / 4
    }
  }
}

1.18 版本以前 的邏輯：

1. 新增元素後的長度 > 2 倍原始容量，那麼就會 使用該長度。
2. 擴容在 少量元素 的情況下，會以 2 倍大小 作為新的容量，但是為了避免後續 容量增加而未使用 造成的空間浪費，所以只要是容量大小 >= 1024 的情況，就只會 每次增加原本容量的 25%。

1.18 版本以後 的邏輯，則是 修改閥值大小 把 1024 降低到 256，並且每次新增除了 25% 的容量，還會新增 192 的空間，會這樣更動的原因可以查看當時的 Commit 紀錄，其實就是想要讓 擴容曲線更加圓滑。

starting cap	growth factor
256	2.0
512	1.63
1024	1.44
2048	1.35
4096	1.30

那麼根據 1.22 版本的規則 for 迴圈的範例，從容量 512 擴容時，newcap 應該要是 512 * 1.25 + 192 = 832，為什麼打印出來的容量是 848 呢？那是因為還要對 記憶體空間 進行 對齊。

記憶體對齊

關於記憶體對齊，jserv 在 你所不知道的 C 語言 的講座有講到，大概意思就是每次 CPU 都會抓固定的大小 (32 位元就是 4 bytes、64 位元就是 8 bytes) 進行運算。

假定我現在是 64 位元的系統，我每次以 8 bytes 為單位的方式抓資料，如果我現在要抓的資料位址在第 1~8 byte，那麼就要抓兩次分別是：

1. 取 0-7 byte，把第 0 byte 的資料清除，留下 1-7 byte
2. 取 8-15 byte，把 9-15 byte 的資料清除，留下第 8 byte
3. 再把抓出來的兩個記憶體位址進行拼接

同樣是取資料，但是由於 記憶體的資料不對齊，所以操作更加複雜導致 效率低落

所以我們在擴容的時候，當然也要根據 Slice 的型別佔用的空間 去申請 相對應大小的空間。

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
  // 略...

  var overflow bool
  var lenmem, newlenmem, capmem uintptr
  // 對元素大小為 1、goarch.PtrSize、2^n 進行優化
  noscan := et.PtrBytes == 0
  switch {
  case et.Size_ == 1:
    ...
  case et.Size_ == goarch.PtrSize:
    lenmem = uintptr(oldLen) * goarch.PtrSize
    newlenmem = uintptr(newLen) * goarch.PtrSize
    capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
    overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
    newcap = int(capmem / goarch.PtrSize)
  case isPowerOfTwo(et.Size_):
    ...
  default:
    ...
  }

因為範例中是使用 int 型別，在 64 位元下佔用 8 bytes，且 goarch.PtrSize 也是 8 bytes。如果將數字帶入的話：

lenmem = uintptr(512) * 8                       // = 4096
newlenmem = uintptr(513) * 8                    // = 4104
capmem = roundupsize(uintptr(832)*8, false)     // = roundupsize(6656, false)
overflow = uintptr(832) > maxAlloc/8
newcap = int(capmem / 8)                        // = int(roundupsize(6656, false)/8)

後面計算到一半使用 roundupsize()，那麼我們再去看runtime.roundupsize做了什麼運算：

// _MaxSmallSize = 32 << 10 = 32768
// smallSizeDiv  = 8
// largeSizeDiv  = 128
// smallSizeMax  = 1024
// _PageShift    = 13
func roundupsize(size uintptr, noscan bool) uintptr {
  if size < _MaxSmallSize { // 小於 32768
    if size <= smallSizeMax-8 { // 小於等於 1024 - 8 = 1016
      return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
    } else { // 大於 1016
      return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]]) // class_to_size[size_to_class128[divRoundUp(6656 - 1024, 128)]]
    }
  }
  if size+_PageSize < size {
    return size
  }
  return alignUp(size, _PageSize)
}

我們因為會使用到 6656 bytes 的空間，所以要被 divRoundUp() 運算，runtime.divRoundUp：

// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
	return (n + a - 1) / a // (5632 + 128 - 1) / 128 = 44
}

運算結果為 (5632 + 128 - 1) / 128 = 44，就會變成 class_to_size[size_to_class128[44]]，找出runtime.size_to_class8 和 runtime.size_to_class128：

• size_to_class128：代表要多少 128 bytes 來對齊記憶體
• class_to_size：代表對應記憶體對其的字節大小

var class_to_size = [0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768]
var size_to_class128 = [32, 33, 34, 35, 36, 37, 37, 38, 38, 39, 39, 40, 40, 40, 41, 41, 41, 42, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 48, 48, 48, 49, 49, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67]

所以 size_to_class128[44] = 49，接續 class_to_size[49] = 6784。最後得知要申請的新記憶體空間大小就會是 6784 bytes，而容量就會是 6784 / 8 = 848。

newcap = int(capmem / 8) // = int(6784/8) = 848

重新分配新的記憶體，並將新舊 Slice 資料複製

最後一步，也就是根據需要的空間大小去 申請記憶體空間，根據把舊資料 移植 到新的記憶體位址，返回新的 Slice。

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
  // 略...

  if overflow || capmem > maxAlloc {
    panic(errorString("growslice: len out of range"))
  }

  var p unsafe.Pointer // 擴容後新的指針起始位址
  if et.PtrBytes == 0 {
    p = mallocgc(capmem, nil, false)
    memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
  } else {
    // 重新分配新的記憶體
    p = mallocgc(capmem, et, true)
    if lenmem > 0 && writeBarrier.enabled {
      bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
    }
  }
  // 這個函數由組語寫成，目的是將舊 Slice data 轉移至新 Slice
  memmove(p, oldPtr, lenmem)

  // 返回新的 Slice
  return slice{p, newLen, newcap}
}

小試身手

請都以 1.18 以後的版本邏輯，回答以下會輸出什麼！

問題一

func main() {
  var array [20]int
  var slice = array[10:11]
  fmt.Println("lenth: ", len(slice))
  fmt.Println("capacity: ", cap(slice))
  fmt.Println(&slice[0] == &array[10])
}

答案一

lenth:  1
capacity:  10
true

問題二

func main() {
  orderLen := 5
  order := make([]uint16, 2 * orderLen)

  pollorder := order[:orderLen:orderLen]
  lockorder := order[orderLen:][:orderLen:orderLen]

  fmt.Println("len(pollorder) = ", len(pollorder))
  fmt.Println("cap(pollorder) = ", cap(pollorder))
  fmt.Println("len(lockorder) = ", len(lockorder))
  fmt.Println("cap(lockorder) = ", cap(lockorder))
}

答案二

len(pollorder) =  5
cap(pollorder) =  5
len(lockorder) =  5
cap(lockorder) =  5

問題三

func main() {
  s1 := []int{1, 2}
  s1 = append(s1, 3, 4, 5)
  fmt.Printf("cap of s1:%d\n", cap(s1))

  s2 := make([]int, 255, 255)
  s2 = append(s2, 1)
  fmt.Printf("cap of s2:%d\n", cap(s2))

  s3 := make([]int, 257, 257)
  s3 = append(s3, 1)
  fmt.Printf("cap of s3:%d\n", cap(s3))

  s4 := make([]int, 512, 512)
  s4 = append(s4, 1)
  fmt.Printf("cap of s4:%d\n", cap(s4))
}

答案三

cap of s1:6
cap of s2:512
cap of s3:608
cap of s4:848

結論

• Slice 使用
  • 建立 Slice 可以根據實際需求預先劃分好 需要的容量 以及 初始值。
  • Slice 在進行 copy 時，要判斷是否目的 Slice 是否為需求所要。
  • Slice 指向同一個 Array，請避免多次操作同一個 Slice。
  • 使用 len()、cap() 可以獲取 Slice 的長度和容量。
  • Slice 在賦值時不會複製整個 Slice，而是獲取其 Array 位址、長度 和 容量。
  • 使用 append 可能會觸發擴容，若是想要避免，可以提前宣告足夠的容量。
• growslice
  • 1.18 前後版本的擴容閥值不同，原本由 1024 降至 256。
  • 如果 新增元素後長度 > 原本容量 2 倍，就會 使用該長度。
  • 如果要 原本容量 < 閥值，就會以 2 倍 進行擴容。
  • 如果 原本容量 >= 閥值，則是根據 原本容量的 25% 進行擴容，新版本還會 增加 192。
  • 計算好預期容量後，還要讓 記憶體對齊，才能夠申請新的 Slice。

本篇文章的程式碼範例。

參考資料

• https://juejin.cn/post/6997212552241348616
• https://pjchender.dev/golang/slice-and-array/
• https://www.joxrays.com/go-slice/
• https://golang.design/go-questions/slice/grow/
• https://github.com/golang/go