一、結(jié)構(gòu)介紹

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

切片是一種引用類型，它有三個(gè)屬性：指針，長(zhǎng)度和容量。

底層源碼定義：

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

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

2.長(zhǎng)度： slice 中元素個(gè)數(shù)。

3.容量： slice 起始元素到底層數(shù)組最后一個(gè)元素間的元素個(gè)數(shù)。

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

二、擴(kuò)容時(shí)機(jī)與過程

Go 中切片的擴(kuò)容機(jī)制是基于動(dòng)態(tài)數(shù)組的，這意味著切片的底層數(shù)組會(huì)動(dòng)態(tài)調(diào)整大小以適應(yīng)元素的增加。下面是 Go 切片擴(kuò)容的一般過程：

1.初始分配：

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

2.追加元素：

當(dāng)你使用 append 向切片追加元素時(shí)，Go 會(huì)檢查是否有足夠的容量來容納新的元素。如果有足夠的容量，新元素會(huì)被添加到底層數(shù)組的末尾，切片的長(zhǎng)度會(huì)增加。如果沒有足夠的容量，就需要進(jìn)行擴(kuò)容。

3.擴(kuò)容：

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

三、擴(kuò)容原理

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

Go 1.18版本 之前擴(kuò)容原理

在分配內(nèi)存空間之前需要先確定新的切片容量，運(yùn)行時(shí)根據(jù)切片的當(dāng)前容量選擇不同的策略進(jìn)行擴(kuò)容：

1. 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量；

2. 如果當(dāng)前切片的長(zhǎng)度小于 1024 就會(huì)將容量翻倍；

3. 如果當(dāng)前切片的長(zhǎng)度大于等于 1024 就會(huì)每次增加 25% 的容量，直到新容量大于期望容量；

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

記錄容量變化如下：

[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版本 之后擴(kuò)容原理

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

在分配內(nèi)存空間之前需要先確定新的切片容量，運(yùn)行時(shí)根據(jù)切片的當(dāng)前容量選擇不同的策略進(jìn)行擴(kuò)容：

1. 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量；

2. 如果當(dāng)前切片的長(zhǎng)度小于閾值（默認(rèn) 256）就會(huì)將容量翻倍；

3. 如果當(dāng)前切片的長(zhǎng)度大于等于閾值（默認(rèn) 256），就會(huì)每次增加 25% 的容量，基準(zhǔn)是 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ī)則如下：

其中,當(dāng)擴(kuò)容前容量 >= 256時(shí)，會(huì)按照公式進(jìn)行擴(kuò)容

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

這樣得到的預(yù)估容量并不是最終結(jié)果，還有內(nèi)存對(duì)齊，進(jìn)一步調(diào)整newcap

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

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

可以試著求一個(gè)極限，當(dāng)oldcap遠(yuǎn)大于256的時(shí)候，擴(kuò)容系數(shù)將會(huì)變成1.25。

四、內(nèi)存對(duì)齊

擴(kuò)容之后的容量并不是嚴(yán)格按照這個(gè)策略的。那是為什么呢？

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

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))

按照上述策略的結(jié)果，應(yīng)該是 len:5，cap:5。但是最終結(jié)果為 len:5，cap:6
解釋：容量計(jì)算完了后還要考慮到內(nèi)存的高效利用，進(jìn)行內(nèi)存對(duì)齊，則會(huì)調(diào)用這個(gè)函數(shù) 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 表示新切片需要的內(nèi)存大小 我們傳入的 int 類型，每個(gè)占用 8 字節(jié) (可以調(diào)用 unsafe.Sizeof() 函數(shù)查看占用的大小)，一共 5 個(gè) 所以是 40，size 小于_MaxSmallSize 并且小于 smallSizeMax-8 ，那么使用通用公式 (size+smallSizeDiv-1)/smallSizeDiv 計(jì)算得到 5，然后到 size_to_class8 找到第五號(hào)元素 為 4，再從 class_to_size 找到 第四號(hào)元素 為 48，這就是新切片占用的內(nèi)存大小，每個(gè) int 占用 8 字節(jié)，所以最終切片的容量為 6 。所以說切片的擴(kuò)容有它基本的擴(kuò)容規(guī)則，在規(guī)則之后還要考慮內(nèi)存對(duì)齊，這就代表不同數(shù)據(jù)類型的切片擴(kuò)容的容量大小是會(huì)不一致。

五、總結(jié)

切片擴(kuò)容通常是在進(jìn)行切片的 append? 操作時(shí)觸發(fā)的。在進(jìn)行 append? 操作時(shí)，如果切片容量不足以容納新的元素，就需要對(duì)切片進(jìn)行擴(kuò)容，此時(shí)就會(huì)調(diào)用 growslice 函數(shù)進(jìn)行擴(kuò)容。
切片擴(kuò)容分兩個(gè)階段，分為 go1.18 之前和之后：

一、go1.18 之前：

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

二、go1.18 之后：

1.如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量；

2.如果當(dāng)前切片的長(zhǎng)度小于閾值（默認(rèn) 256）就會(huì)將容量翻倍；

3.如果當(dāng)前切片的長(zhǎng)度大于等于閾值（默認(rèn) 256），就會(huì)每次增加 25% 的容量，基準(zhǔn)是 newcap + 3*threshold，直到新容量大于期望容量；

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

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

以上就是Go語言切片擴(kuò)容原理和過程的詳細(xì)內(nèi)容，更多關(guān)于Go切片擴(kuò)容的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論