2023-05-20：go語言的slice和rust語言的Vec的擴容流程是什么？

答案2023-05-20：

go語言的slice擴容流程

go版本是1.20.4。

擴容流程見源碼見runtime/slice.go文件中的growslice 函數(shù)。

growslice 函數(shù)的大致過程如下：

1.如果元素類型的大小為零，則返回具有 nil 指針但非零長度的切片。否則，下一步。

2.計算新切片的容量。如果新長度大于舊容量的兩倍，則將新容量設(shè)置為新長度。否則，如果舊容量小于 256，則將新容量設(shè)置為舊容量的兩倍，這是翻倍擴容。否則，使用一種算法計算新容量，該算法從將增長因子從 2 倍轉(zhuǎn)變?yōu)?1.25 倍的小切片開始，平滑地過渡到大切片，新容量=舊長度+(舊長度+3*256)/4，這比1.25倍略大，但很近似。近似1.25倍擴容不一定會大于等于新長度，所以必須循環(huán)多次擴容，一直到大于等于新長度。如果新容量計算溢出，則將則將新容量設(shè)置為新長度。

3.根據(jù)對象大小的67種規(guī)格，計算新切片的內(nèi)存占用量，并且會重新調(diào)整新切片的容量，一般會改大。

以下描述可以不看：

3.1.根據(jù)元素類型的大小進行特化處理。對于大小為 1 的元素類型，不需要任何除法/乘法。

3.2.對于大小等于 goarch.PtrSize 的元素類型，編譯器會將除法/乘法優(yōu)化為一個常量的移位操作。

3.3.對于大小為 2 的冪的元素類型，使用可變移位量進行處理。

3.4.對于其他大小的元素類型，計算所需內(nèi)存，并將其舍入到頁大小的倍數(shù)。

4.調(diào)用mallocgc函數(shù)，分配內(nèi)存，產(chǎn)生新指針。

這段描述可以不看，根據(jù)元素類型的指針數(shù)據(jù)大?。丛仡愋椭兄赶蚨焉戏峙涞膬?nèi)存的指針字段的大?。褂?mallocgc() 分配新的后備存儲器。如果指針數(shù)據(jù)大小為零，則直接調(diào)用 mallocgc() 分配內(nèi)存，并在分配的內(nèi)存中清除將被覆蓋的部分。否則，使用 GC 兼容內(nèi)存分配器 mallocgc() 分配內(nèi)存，并根據(jù)需要啟用寫屏障。

5.調(diào)用memmove函數(shù)，舊指針數(shù)據(jù)填充到新指針數(shù)據(jù)里。

6.返回新切片，其中包含指向新指針、新長度和新容量。

[圖片上傳失敗...(image-40780f-1684592036844)]

rust語言的Vec的擴容流程

rust版本：cargo 1.71.0-nightly (09276c703 2023-05-16)

擴容流程見raw_vec.rs文件里的grow_amortized 方法。

grow_amortized 方法的大體過程如下：

1.如果 T 是零大小類型（ZST），則直接返回一個錯誤，因為對于 ZST 的 Vec 實例來說，它們的容量總是 usize::MAX，不能再增加更多的容量。

2.計算新容量 。新容量 = MAX（當前長度+新增元素的長度，2倍的舊容量， Self::MIN_NON_ZERO_CAP）。

以下是對 Self::MIN_NON_ZERO_CAP 的描述可以不看：

MIN_NON_ZERO_CAP 是最小非零容量。該值表示在進行內(nèi)存分配時， Vec 最少需要分配的非零容量大小，以避免出現(xiàn)過多的內(nèi)存浪費和碎片化。

具體來說，這個常量定義采用了一個簡單的策略，根據(jù) T 類型元素的大小，分別設(shè)置不同的最小非零容量值：

• 如果 T 類型元素大小為 1 字節(jié)，則將最小非零容量設(shè)置為 8；

• 如果 T 類型元素大小小于等于 1024 字節(jié)，則將最小非零容量設(shè)置為 4；

• 否則，將最小非零容量設(shè)置為 1。

其中，如果 T 類型元素大小為 1 字節(jié)，則將最小非零容量設(shè)置為 8 是因為大部分堆分配器（heap allocator）會將小于 8 字節(jié)的內(nèi)存請求自動對齊到 8 字節(jié)邊界，因此設(shè)置最小容量為 8 可以避免出現(xiàn)內(nèi)存浪費。

對于大小在 1 字節(jié)到 1024 字節(jié)之間的類型元素，將最小非零容量設(shè)置為 4，可以在保證一定的內(nèi)存利用率的同時，避免出現(xiàn)過多的內(nèi)存浪費和碎片化。

而對于大于 1024 字節(jié)的類型元素，將最小非零容量設(shè)置為 1，則可以避免出現(xiàn)過多的內(nèi)存浪費，同時保證了內(nèi)存分配時的性能和效率。

總之，這個常量定義是 Vec 在進行內(nèi)存分配時所采用的一種策略，旨在盡可能地減少內(nèi)存浪費和碎片化，同時保證了內(nèi)存分配的性能和效率。

3.基于新的容量使用 Layout::array::<T> 方法創(chuàng)建一個新的布局 new_layout，new_layout 并不是已經(jīng)分配了內(nèi)存空間的對象，它只是一個描述所需內(nèi)存塊大小和對齊方式的布局對象。

4.調(diào)用 finish_grow() 方法進行內(nèi)存分配，會獲得一個新指針。這個方法是非泛型的，不依賴于 T 類型。

5.調(diào)用 set_ptr_and_cap 將分配得到的新指針和容量設(shè)置為 RawVec 實例的新值。

6.成功擴容，返回一個 Ok(()) 值。

需要注意的是，在上述過程中，除了第一步和第三步涉及到具體的類型 T 外，其他過程都是非泛型的。這樣做是為了盡可能減小 grow_amortized() 方法的大小，同時提高其靜態(tài)計算能力，從而使生成的代碼運行更快。

[圖片上傳失敗...(image-aa5be5-1684592036844)]