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ā)生改變了,具體可以參考一下這個 commit
: runtime: make slice growth formula a bit smoother。
大概意思是:
在之前的版本中:對于 <1024
個元素,增加 2
倍,對于 >=1024
個元素,則增加 1.25
倍。 而現(xiàn)在,使用更平滑的增長因子公式。 在 256 個元素后開始降低增長因子,但要緩慢。
它還給了個表格,寫明了不同容量下的增長因子:
starting cap | growth factor |
---|---|
256 | 2.0 |
512 | 1.63 |
1024 | 1.44 |
2048 | 1.35 |
4096 | 1.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)文章
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-05Go垃圾回收提升內(nèi)存管理效率優(yōu)化最佳實踐
這篇文章主要為大家介紹了Go垃圾回收提升內(nèi)存管理效率優(yōu)化最佳實踐,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12詳解Go中g(shù)in框架如何實現(xiàn)帶顏色日志
當(dāng)我們在終端上(比如Goland)運行g(shù)in框架搭建的服務(wù)時,會發(fā)現(xiàn)輸出的日志是可以帶顏色的,那這是如何實現(xiàn)的呢?本文就來和大家簡單講講2023-04-04Golang信號處理及如何實現(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