網站首頁 編程語言 正文
正文
基于 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
相關推薦
- 2022-07-31 C++?容器?Vector?的使用方法_C 語言
- 2022-12-04 Flutter狀態管理Provider的使用示例詳解_Android
- 2024-07-15 linux系統管理高級命令(練習)(six day)
- 2022-10-05 Android開發Activity毛玻璃背景效果_Android
- 2022-12-04 pyecharts?X軸標簽太長被截斷的問題及解決_python
- 2022-11-14 C++設計與聲明超詳細講解_C 語言
- 2022-09-20 android原生實現多線程斷點續傳功能_Android
- 2022-06-17 Ruby信號處理詳解_ruby專題
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支