日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后,達者為師

網站首頁 編程語言 正文

go?slice?擴容實現原理源碼解析_Golang

作者:eleven26 ? 更新時間: 2023-02-09 編程語言

正文

基于 Go 1.19。

go 的切片我們都知道可以自動地進行擴容,具體來說就是在切片的容量容納不下新的元素的時候, 底層會幫我們為切片的底層數組分配更大的內存空間,然后把舊的切片的底層數組指針指向新的內存中:

目前網上一些關于擴容倍數的文章都是基于相對舊版本的 Go 的,新版本中,現在切片擴容的時候并不是那種準確的小于多少容量的時候就 2 倍擴容, 大于多少容量的時候就 1.25 倍擴容,其實這個數值多少不是非常關鍵的,我們只需要知道的是: 在容量較小的時候,擴容的因子更大,容量大的時候,擴容的因子相對來說比較小。

擴容的示例

我們先通過一個簡單的示例來感受一下切片擴容是什么時候發生的:

var slice = []int{1, 2, 3}
fmt.Println(slice, len(slice), cap(slice))
slice = append(slice, 4)
fmt.Println(slice, len(slice), cap(slice))

在這個例子中,slice 切片初始化的時候,長度和容量都是 3(容量不指定的時候默認等于長度)。 因此切片已經容納不下新的元素了,在我們往 slice 中追加一個新的元素的時候, 我們發現,slice 的長度和容量都變了, 長度增加了 1,而容量變成了原來的 2 倍。

在 1.18 版本以后,舊的切片容量小于 256 的時候,會進行 2 倍擴容。

實際擴容倍數

其實最新的擴容規則在 1.18 版本中就已經發生改變了,具體可以參考一下這個 commit: runtime: make slice growth formula a bit smoother。

大概意思是:

在之前的版本中:對于 <1024 個元素,增加 2 倍,對于 >=1024 個元素,則增加 1.25 倍。 而現在,使用更平滑的增長因子公式。 在 256 個元素后開始降低增長因子,但要緩慢。

它還給了個表格,寫明了不同容量下的增長因子:

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

從這個表格中,我們可以看到,新版本的切片庫容,并不是在容量小于 1024 的時候嚴格按照 2 倍擴容,大于 1024 的時候也不是嚴格地按照 1.25 倍來擴容。

growslice 實現

在 go 中,切片擴容的實現是 growslice 函數,位于 runtime/slice.go 中。

growslice 有如下參數:

  • oldPtr: 舊的切片的底層數組指針。
  • newLen: 新的切片的長度(= oldLen + num)。
  • oldCap: 舊的切片的容量。
  • num: 添加的元素數。
  • et: 切片的元素類型(也即 element type)。

返回一個新的切片,這個返回的切片中,底層數組指針指向新分配的內存空間,長度等于 oldLen + num,容量就是底層數組的大小。

growslice 實現步驟

  • 一些特殊情況判斷:如 et.size == 0,切片元素不需要占用空間的情況下,直接返回。
  • 根據 newLen 計算新的容量,保證新的底層數組至少可以容納 newLen 個元素。
  • 計算所需要分配的新的容量所需的內存大小。
  • 分配新的切片底層數組所需要的內存。
  • 將舊切片上的底層數組的數據復制到新的底層數組中。

注意:這個函數只是實現擴容,新增的元素沒有在這個函數往切片中追加。

growslice 源碼剖析

說明:

  • 整數有可能會溢出,所以代碼里面會判斷 newLen < 0。
  • 如果切片的元素是空結構體或者空數組,那么 et.size == 0。
  • 在計算新切片的容量的時候,會根據切片的元素類型大小來做一些優化。
  • 新切片容量所占用的內存大小為 capmem
  • 新切片所需要的內存分配完成后,會將舊切片的數據復制到新切片中。
  • 最后返回指向新的底層數組的切片,其長度為 newLen,容量為 newcap。
// growtslice 為切片分配新的存儲空間。
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
   // oldLen 為舊的切片底層數組的長度
   oldLen := newLen - num
   // 分配的新的長度不能小于 0(整數溢出的時候會是負數)
   if newLen < 0 {
      panic(errorString("growslice: len out of range"))
   }
   // 如果結構或數組類型不包含大小大于零的字段(或元素),則其大小為零。
   //(空數組、空結構體,type b [0]int、type zero struct{})
   // 兩個不同的零大小變量在內存中可能具有相同的地址。
   if et.size == 0 {
      // append 不應創建具有 nil 指針但長度非零的切片。
      // 在這種情況下,我們假設 append 不需要保留 oldPtr。
      return slice{unsafe.Pointer(&zerobase), newLen, newLen}
   }
   // newcap 是新切片底層數組的容量
   newcap := oldCap
   // 兩倍容量
   doublecap := newcap + newcap
   if newLen > doublecap {
      // 如果追加元素之后,新的切片長度比舊切片 2 倍容量還大,
      // 則將新的切片的容量設置為跟長度一樣
      newcap = newLen
   } else {
      const threshold = 256
      if oldCap < threshold {
         // 舊的切片容量小于 256 的時候,
         // 進行兩倍擴容。
         newcap = doublecap
      } else {
         // oldCap >= 256
         // 檢查 0<newcap 以檢測溢出并防止無限循環。
         for 0 < newcap && newcap < newLen {
            // 從小切片的增長 2 倍過渡到大切片的增長 1.25 倍。
            newcap += (newcap + 3*threshold) / 4
         }
         // 當 newcap 計算溢出時,將 newcap 設置為請求的上限。
         if newcap <= 0 {
            newcap = newLen
         }
      }
   }
   // 計算實際所需要的內存大小
   // 是否溢出
   var overflow bool
   // lenmem 表示舊的切片長度所需要的內存大小
   //(lenmem 就是將舊切片數據復制到新切片的時候指定需要復制的內存大小)
   // newlenmem 表示新的切片長度所需要的內存大小
   // capmem 表示新的切片容量所需要的內存大小
   var lenmem, newlenmem, capmem uintptr
   // 根據 et.size 做一些計算上的優化:
   // 對于 1,我們不需要任何除法/乘法。
   // 對于 goarch.PtrSize,編譯器會將除法/乘法優化為移位一個常數。
   // 對于 2 的冪,使用可變移位。
   switch {
   case et.size == 1: // 比如 []byte,所需內存大小 = size
      lenmem = uintptr(oldLen)
      newlenmem = uintptr(newLen)
      capmem = roundupsize(uintptr(newcap))
      overflow = uintptr(newcap) > maxAlloc
      newcap = int(capmem)
   case et.size == goarch.PtrSize: // 比如 []*int,所需內存大小 = size * ptrSize
      lenmem = uintptr(oldLen) * goarch.PtrSize
      newlenmem = uintptr(newLen) * goarch.PtrSize
      capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
      overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
      newcap = int(capmem / goarch.PtrSize)
   case isPowerOfTwo(et.size): // 比如 []int64,所需內存大小 = size << shift,也就是 size * 2^shift(2^shift 是 et.size)
      var shift uintptr
      if goarch.PtrSize == 8 {
         // Mask shift for better code generation.
         shift = uintptr(sys.TrailingZeros64(uint64(et.size))) & 63
      } else {
         shift = uintptr(sys.TrailingZeros32(uint32(et.size))) & 31
      }
      lenmem = uintptr(oldLen) << shift
      newlenmem = uintptr(newLen) << shift
      capmem = roundupsize(uintptr(newcap) << shift)
      overflow = uintptr(newcap) > (maxAlloc >> shift)
      newcap = int(capmem >> shift)
      capmem = uintptr(newcap) << shift
   default: // 沒得優化,直接使用乘法了
      lenmem = uintptr(oldLen) * et.size
      newlenmem = uintptr(newLen) * et.size
      capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
      capmem = roundupsize(capmem)
      newcap = int(capmem / et.size)
      capmem = uintptr(newcap) * et.size
   }
   // 檢查是否溢出,以及是否超過最大可分配內存
   if overflow || capmem > maxAlloc {
      panic(errorString("growslice: len out of range"))
   }
   // 分配實際所需要的內存
   var p unsafe.Pointer
   if et.ptrdata == 0 { // 不包含指針
      // 分配 capmem 大小的內存,不清零
      p = mallocgc(capmem, nil, false)
      // 這里只清空從 add(p, newlenmem) 開始大小為 capmem-newlenmem 的內存,
      // 也就是前面的 newlenmem 長度不清空。
      // 因為最后的 capmem-newlenmem 這塊內存,實際上是額外分配的容量。
      // 前面的那部分會被舊切片的數據以及新追加的數據覆蓋。
      memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
   } else {
      // 分配 capmem 大小的內存,需要進行清零
      p = mallocgc(capmem, et, true)
      if lenmem > 0 && writeBarrier.enabled {
         // Only shade the pointers in oldPtr since we know the destination slice p
         // only contains nil pointers because it has been cleared during alloc.
         bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.size+et.ptrdata)
      }
   }
   // 舊切片數據復制到新切片中,復制的內容大小為 lenmem
   //(從 oldPtr 復制到 p)
   memmove(p, oldPtr, lenmem)
   return slice{p, newLen, newcap}
}

總結

go 的切片在容量較小的情況下,確實會進行 2 倍擴容,但是隨著容量的增長,擴容的增長因子會逐漸降低。 新版本的 growslice 實現中,只有容量小于 256 的時候才會進行 2 倍擴容, 然后隨著容量的增長,擴容的因子會逐漸降低(但并不是直接降到 1.25,而是一個相對緩慢的下降)。

原文鏈接:https://juejin.cn/post/7179578237872242749

欄目分類
最近更新