一、結構介紹

切片（Slice）在 Go 語言中，有一個很常用的數據結構，切片是一個擁有相同類型元素的可變長度的序列，它是基于數組類型做的一層封裝。它非常靈活，支持自動擴容。并發(fā)不安全。

切片是一種引用類型，它有三個屬性：指針，長度和容量。

底層源碼定義：

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

1.指針： 指向 slice 可以訪問到的第一個元素。

2.長度： slice 中元素個數。

3.容量： slice 起始元素到底層數組最后一個元素間的元素個數。

比如使用 make([]byte, 5) 創(chuàng)建一個切片，它看起來是這樣的：

二、擴容時機與過程

Go 中切片的擴容機制是基于動態(tài)數組的，這意味著切片的底層數組會動態(tài)調整大小以適應元素的增加。下面是 Go 切片擴容的一般過程：

1.初始分配：

當使用 make 創(chuàng)建一個切片時，Go 會為其分配一塊初始的底層數組，并將切片的長度和容量都設置為相同的值。

2.追加元素：

當你使用 append 向切片追加元素時，Go 會檢查是否有足夠的容量來容納新的元素。如果有足夠的容量，新元素會被添加到底層數組的末尾，切片的長度會增加。如果沒有足夠的容量，就需要進行擴容。

3.擴容：

當切片需要擴容時，Go 會創(chuàng)建一個新的更大的底層數組（具體的擴容策略看下面擴容原理）。然后，原數組的元素會被復制到新數組中，新元素會被添加到新數組的末尾。最后，切片的引用會指向新的底層數組，原數組會被垃圾回收。
這個擴容的過程保證了在大多數情況下，append 操作都是高效的。由于每次擴容都會涉及元素的復制，因此在涉及大量元素的情況下可能會導致一些性能開銷。如果你知道切片需要存儲的元素數量，可以使用 make 函數make([]T, length, capacity)的第三個參數顯式指定容量，以減少擴容的次數。

三、擴容原理

Go1.18之前切片的擴容是以容量1024為臨界點，當舊容量 < 1024個元素,擴容變成2倍；當舊容量 > 1024個元素，那么會進入一個循環(huán)，每次增加25%直到大于期望容量。
然而這個擴容機制已經被Go 1.18棄用了，官方說新的擴容機制能更平滑地過渡。
具體擴容原理分別如下：

Go 1.18版本 之前擴容原理

在分配內存空間之前需要先確定新的切片容量，運行時根據切片的當前容量選擇不同的策略進行擴容：

1. 如果期望容量大于當前容量的兩倍就會使用期望容量；

2. 如果當前切片的長度小于 1024 就會將容量翻倍；

3. 如果當前切片的長度大于等于 1024 就會每次增加 25% 的容量，直到新容量大于期望容量；

注：解釋一下第一條：
比如 nums := []int{1, 2} nums = append(nums, 2, 3, 4)，這樣期望容量為2+3 = 5，而5 > 2*2，故使用期望容量（這只是不考慮內存對齊的情況下）

記錄容量變化如下：

[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

Go 1.18版本 之后擴容原理

和之前版本的區(qū)別，主要在擴容閾值，以及這行源碼：newcap += (newcap + 3*threshold) / 4。

在分配內存空間之前需要先確定新的切片容量，運行時根據切片的當前容量選擇不同的策略進行擴容：

1. 如果期望容量大于當前容量的兩倍就會使用期望容量；

2. 如果當前切片的長度小于閾值（默認 256）就會將容量翻倍；

3. 如果當前切片的長度大于等于閾值（默認 256），就會每次增加 25% 的容量，基準是 newcap + 3*threshold，直到新容量大于期望容量；

記錄容量變化如下：

[0 ->   -1] cap = 0     |  after append 0     cap = 1
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 848 
[0 ->  847] cap = 848   |  after append 848   cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1792
[0 -> 1791] cap = 1792  |  after append 1792  cap = 2560

大致規(guī)則如下：

其中,當擴容前容量 >= 256時，會按照公式進行擴容

newcap += (newcap + 3*threshold) / 4

這樣得到的預估容量并不是最終結果，還有內存對齊，進一步調整newcap

在1.18中，優(yōu)化了切片擴容的策略，讓底層數組大小的增長更加平滑：通過減小閾值并固定增加一個常數，使得優(yōu)化后的擴容的系數在閾值前后不再會出現從2到1.25的突變，該commit作者給出了幾種原始容量下對應的“擴容系數”：

可以看到，Go1.18的擴容策略中，隨著容量的增大，其擴容系數是越來越小的，可以更好地節(jié)省內存。

可以試著求一個極限，當oldcap遠大于256的時候，擴容系數將會變成1.25。

四、內存對齊

擴容之后的容量并不是嚴格按照這個策略的。那是為什么呢？

實際上，growslice? 的后半部分還有更進一步的優(yōu)化（內存對齊等），靠的是 roundupsize? 函數，在計算完 newcap 值之后，還會有一個步驟計算最終的容量：

capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)

舉例：

還是上面的例子：

nums := []int{1, 2}
nums = append(nums, 2, 3, 4)
fmt.Printf("len:%v  cap:%v", len(nums), cap(nums))

按照上述策略的結果，應該是 len:5，cap:5。但是最終結果為 len:5，cap:6
解釋：容量計算完了后還要考慮到內存的高效利用，進行內存對齊，則會調用這個函數 roundupsize 。

func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= smallSizeMax-8 {
            return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
        } else {
        return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
        }
    }
    if size+_PageSize < size {
        return size
    }
    return alignUp(size, _PageSize)
}

size 表示新切片需要的內存大小 我們傳入的 int 類型，每個占用 8 字節(jié) (可以調用 unsafe.Sizeof() 函數查看占用的大小)，一共 5 個 所以是 40，size 小于_MaxSmallSize 并且小于 smallSizeMax-8 ，那么使用通用公式 (size+smallSizeDiv-1)/smallSizeDiv 計算得到 5，然后到 size_to_class8 找到第五號元素 為 4，再從 class_to_size 找到 第四號元素 為 48，這就是新切片占用的內存大小，每個 int 占用 8 字節(jié)，所以最終切片的容量為 6 。所以說切片的擴容有它基本的擴容規(guī)則，在規(guī)則之后還要考慮內存對齊，這就代表不同數據類型的切片擴容的容量大小是會不一致。

五、總結

切片擴容通常是在進行切片的 append? 操作時觸發(fā)的。在進行 append? 操作時，如果切片容量不足以容納新的元素，就需要對切片進行擴容，此時就會調用 growslice 函數進行擴容。
切片擴容分兩個階段，分為 go1.18 之前和之后：

一、go1.18 之前：

1.如果期望容量大于當前容量的兩倍就會使用期望容量；
2.如果當前切片的長度小于 1024 就會將容量翻倍；
3.如果當前切片的長度大于 1024 就會每次增加 25% 的容量，直到新容量大于期望容量；

二、go1.18 之后：

1.如果期望容量大于當前容量的兩倍就會使用期望容量；

2.如果當前切片的長度小于閾值（默認 256）就會將容量翻倍；

3.如果當前切片的長度大于等于閾值（默認 256），就會每次增加 25% 的容量，基準是 newcap + 3*threshold，直到新容量大于期望容量；

總的來說，Go的設計者不斷優(yōu)化切片擴容的機制，其目的只有一個：就是控制讓小的切片容量增長速度快一點，減少內存分配次數，而讓大切片容量增長率小一點，更好地節(jié)省內存。

• 如果只選擇翻倍的擴容策略，那么對于較大的切片來說，現有的方法可以更好的節(jié)省內存。
• 如果只選擇每次系數為1.25的擴容策略，那么對于較小的切片來說擴容會很低效。
• 之所以選擇一個小于2的系數，在擴容時被釋放的內存塊會在下一次擴容時更容易被重新利用。

以上就是Go語言切片擴容原理和過程的詳細內容，更多關于Go切片擴容的資料請關注腳本之家其它相關文章！

最新評論