亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

go slice 擴容實現(xiàn)原理源碼解析

 更新時間:2023年01月03日 11:29:03   作者:eleven26  
這篇文章主要為大家介紹了go slice 擴容實現(xiàn)原理源碼解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

正文

基于 Go 1.19。

go 的切片我們都知道可以自動地進行擴容,具體來說就是在切片的容量容納不下新的元素的時候, 底層會幫我們?yōu)榍衅牡讓訑?shù)組分配更大的內(nèi)存空間,然后把舊的切片的底層數(shù)組指針指向新的內(nèi)存中:

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

擴容的示例

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

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(容量不指定的時候默認(rèn)等于長度)。 因此切片已經(jīng)容納不下新的元素了,在我們往 slice 中追加一個新的元素的時候, 我們發(fā)現(xiàn),slice 的長度和容量都變了, 長度增加了 1,而容量變成了原來的 2 倍。

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

實際擴容倍數(shù)

其實最新的擴容規(guī)則在 1.18 版本中就已經(jīng)發(fā)生改變了,具體可以參考一下這個 commitruntime: make slice growth formula a bit smoother

大概意思是:

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

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

starting capgrowth factor
2562.0
5121.63
10241.44
20481.35
40961.30

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

growslice 實現(xiàn)

在 go 中,切片擴容的實現(xiàn)是 growslice 函數(shù),位于 runtime/slice.go 中。

growslice 有如下參數(shù):

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

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

growslice 實現(xiàn)步驟

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

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

growslice 源碼剖析

說明:

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

總結(jié)

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

以上就是go slice 擴容實現(xiàn)原理源碼解析的詳細(xì)內(nèi)容,更多關(guān)于go slice 擴容原理的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • Go語言常見哈希函數(shù)的使用

    Go語言常見哈希函數(shù)的使用

    哈希表(Hash table,也叫散列表),是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說,它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄,以加快查找的速度。具體的介紹網(wǎng)上有很詳細(xì)的描述,如閑聊哈希表 ,這里就不再累述了;
    2015-03-03
  • Golang發(fā)送Get和Post請求的實現(xiàn)

    Golang發(fā)送Get和Post請求的實現(xiàn)

    做第三方接口有時需要用Get或者Post請求訪問,本文主要介紹了Golang發(fā)送Get和Post請求的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2024-05-05
  • golang 數(shù)組隨機排序的實現(xiàn)

    golang 數(shù)組隨機排序的實現(xiàn)

    本文主要介紹了golang 數(shù)組隨機排序的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-12-12
  • goLand Delve版本太老的問題及解決

    goLand Delve版本太老的問題及解決

    這篇文章主要介紹了goLand Delve版本太老的問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-09-09
  • go-micro微服務(wù)JWT跨域認(rèn)證問題

    go-micro微服務(wù)JWT跨域認(rèn)證問題

    JWT 以 JSON 對象的形式安全傳遞信息。因為存在數(shù)字簽名,因此所傳遞的信息是安全的,這篇文章主要介紹了go-micro微服務(wù)JWT跨域認(rèn)證,需要的朋友可以參考下
    2023-01-01
  • 簡介Go語言中的select語句的用法

    簡介Go語言中的select語句的用法

    這篇文章主要介紹了簡介Go語言中的select語句的用法,是golang入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下
    2015-10-10
  • Go垃圾回收提升內(nèi)存管理效率優(yōu)化最佳實踐

    Go垃圾回收提升內(nèi)存管理效率優(yōu)化最佳實踐

    這篇文章主要為大家介紹了Go垃圾回收提升內(nèi)存管理效率優(yōu)化最佳實踐,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-12-12
  • 詳解Go中g(shù)in框架如何實現(xiàn)帶顏色日志

    詳解Go中g(shù)in框架如何實現(xiàn)帶顏色日志

    當(dāng)我們在終端上(比如Goland)運行g(shù)in框架搭建的服務(wù)時,會發(fā)現(xiàn)輸出的日志是可以帶顏色的,那這是如何實現(xiàn)的呢?本文就來和大家簡單講講
    2023-04-04
  • Golang信號處理及如何實現(xiàn)進程的優(yōu)雅退出詳解

    Golang信號處理及如何實現(xiàn)進程的優(yōu)雅退出詳解

    這篇文章主要給大家介紹了關(guān)于Golang信號處理及如何實現(xiàn)進程的優(yōu)雅退出的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2018-03-03
  • go語言map字典刪除操作的方法

    go語言map字典刪除操作的方法

    這篇文章主要介紹了go語言map字典刪除操作的方法,實例分析了map字典操作的技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-02-02

最新評論