2023-05-20：go語言的slice和rust語言的Vec的擴容流程是什么？
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.計算新切片的容量。如果新長度大于舊容量的兩倍，則將新容量設置為新長度。否則，如果舊容量小于 256，則將新容量設置為舊容量的兩倍，這是翻倍擴容。否則，使用一種算法計算新容量，該算法從將增長因子從 2 倍轉變?yōu)?1.25 倍的小切片開始，平滑地過渡到大切片，新容量=舊長度+(舊長度+3*256)/4，這比1.25倍略大，但很近似。近似1.25倍擴容不一定會大于等于新長度，所以必須循環(huán)多次擴容，一直到大于等于新長度。如果新容量計算溢出，則將則將新容量設置為新長度。
3.根據對象大小的67種規(guī)格，計算新切片的內存占用量，并且會重新調整新切片的容量，一般會改大。
以下描述可以不看：
3.1.根據元素類型的大小進行特化處理。對于大小為 1 的元素類型，不需要任何除法/乘法。
3.2.對于大小等于 goarch.PtrSize 的元素類型，編譯器會將除法/乘法優(yōu)化為一個常量的移位操作。
3.3.對于大小為 2 的冪的元素類型，使用可變移位量進行處理。
3.4.對于其他大小的元素類型，計算所需內存，并將其舍入到頁大小的倍數(shù)。
4.調用mallocgc函數(shù)，分配內存，產生新指針。
這段描述可以不看，根據元素類型的指針數(shù)據大?。丛仡愋椭兄赶蚨焉戏峙涞膬却娴闹羔樧侄蔚拇笮。?，使用?mallocgc()?分配新的后備存儲器。如果指針數(shù)據大小為零，則直接調用?mallocgc()?分配內存，并在分配的內存中清除將被覆蓋的部分。否則，使用 GC 兼容內存分配器?mallocgc()?分配內存，并根據需要啟用寫屏障。
5.調用memmove函數(shù)，舊指針數(shù)據填充到新指針數(shù)據里。
6.返回新切片，其中包含指向新指針、新長度和新容量。
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?是最小非零容量。該值表示在進行內存分配時，?Vec?最少需要分配的非零容量大小，以避免出現(xiàn)過多的內存浪費和碎片化。
具體來說，這個常量定義采用了一個簡單的策略，根據?T?類型元素的大小，分別設置不同的最小非零容量值：
??如果?
T?類型元素大小為 1 字節(jié)，則將最小非零容量設置為 8；??如果?
T?類型元素大小小于等于 1024 字節(jié)，則將最小非零容量設置為 4；??否則，將最小非零容量設置為 1。
其中，如果?T?類型元素大小為 1 字節(jié)，則將最小非零容量設置為 8 是因為大部分堆分配器（heap allocator）會將小于 8 字節(jié)的內存請求自動對齊到 8 字節(jié)邊界，因此設置最小容量為 8 可以避免出現(xiàn)內存浪費。
對于大小在 1 字節(jié)到 1024 字節(jié)之間的類型元素，將最小非零容量設置為 4，可以在保證一定的內存利用率的同時，避免出現(xiàn)過多的內存浪費和碎片化。
而對于大于 1024 字節(jié)的類型元素，將最小非零容量設置為 1，則可以避免出現(xiàn)過多的內存浪費，同時保證了內存分配時的性能和效率。
總之，這個常量定義是?Vec?在進行內存分配時所采用的一種策略，旨在盡可能地減少內存浪費和碎片化，同時保證了內存分配的性能和效率。
3.基于新的容量使用? Layout::array::<T>?方法創(chuàng)建一個新的布局?new_layout，new_layout 并不是已經分配了內存空間的對象，它只是一個描述所需內存塊大小和對齊方式的布局對象。
4.調用?finish_grow()?方法進行內存分配，會獲得一個新指針。這個方法是非泛型的，不依賴于?T?類型。
5.調用?set_ptr_and_cap?將分配得到的新指針和容量設置為?RawVec?實例的新值。
6.成功擴容，返回一個?Ok(())?值。
需要注意的是，在上述過程中，除了第一步和第三步涉及到具體的類型?T?外，其他過程都是非泛型的。這樣做是為了盡可能減小?grow_amortized()?方法的大小，同時提高其靜態(tài)計算能力，從而使生成的代碼運行更快。
福大大架構師每日一題
java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網絡，操作系統(tǒng)。
公眾號
