Golang 切片（slice）源碼分析（一、定義與基礎操作實現）

注意當前go版本代碼為1.23

一、定義

slice 的底層數據是數組，slice 是對數組的封裝，它描述一個數組的片段。兩者都可以通過下標來訪問單個元素。

數組是定長的，長度定義好之后，不能再更改。在 Go 中，數組是不常見的，因為其長度是類型的一部分，限制了它的表達能力，比如 [3]int 和 [4]int 就是不同的類型。

而切片則非常靈活，它可以動態地擴容。切片的類型和長度無關。

數組就是一片連續的內存， slice 實際上是一個結構體，包含三個字段：長度、容量、底層數組。

type slice struct {array unsafe.Pointerlen   intcap   int
}

數據結構如下：

注意，底層數組是可以被多個 slice 同時指向的，因此對一個 slice 的元素進行操作是有可能影響到其他 slice 的。

二、操作

2.1創建

src/runtime/slice.go 主要邏輯就是基于容量申請內存。

func makeslice(et *_type, len, cap int) unsafe.Pointer {// 計算切片所需的內存大小，cap 為切片容量，et.Size_ 為每個元素的大小// math.MulUintptr 執行無符號整數乘法，并返回結果和一個表示是否發生溢出的布爾值mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))// 檢查以下幾種錯誤情況：// 1. overflow：容量計算時發生溢出// 2. mem > maxAlloc：所需的內存超過最大可分配內存// 3. len < 0：切片長度為負數// 4. len > cap：切片長度大于容量if overflow || mem > maxAlloc || len < 0 || len > cap {// 注意：當用戶執行 make([]T, bignumber) 時，產生 "len out of range" 錯誤，而不是 "cap out of range" 錯誤。// 雖然 "cap out of range" 也是對的，但由于容量是隱式提供的，因此提示長度錯誤更清晰。// 參考：golang.org/issue/4085// 重新計算基于長度的內存大小，以便在容量溢出時提供更準確的錯誤信息（例如 len 也溢出）mem, overflow := math.MulUintptr(et.Size_, uintptr(len))// 再次檢查溢出、內存超出限制以及長度為負數的情況if overflow || mem > maxAlloc || len < 0 {panicmakeslicelen() // 長度錯誤，觸發 panic}panicmakeslicecap() // 容量錯誤，觸發 panic}// 調用 mallocgc 分配內存。// mallocgc 是 Go 運行時中的函數，用于分配內存并在垃圾回收器中注冊該內存。// 參數：//   mem: 要分配的內存大小//   et: 切片元素的類型//   true: 指示分配的內存應該被清零return mallocgc(mem, et, true)
}

2.2擴容

核心源碼 growslice-》nextslicecap&&roundupsize

首先通過nextslicecap計算出一個初步的擴容值，通過roundupsize內存對齊得出最終的擴容值，并不是網上的簡單公式。

在1.18版本之前，slice源碼中nextslicecap擴容主要邏輯為：

當原 slice 容量小于 1024 的時候，新 slice 容量變成原來的 2 倍；原 slice 容量超過 1024，新 slice 容量變成原來的1.25倍。

在1.18版本更新之后，slice源碼中nextslicecap的擴容主要邏輯變為了：

當原slice容量(oldcap)小于256的時候，新slice(newcap)容量為原來的2倍；原slice容量超過256，新slice容量newcap = oldcap+(oldcap+3*256)/4

下述為go1.23源碼邏輯src/runtime/slice.go ：

// growslice 為一個切片分配新的底層存儲。
//
// 參數:
// oldPtr = 指向切片底層數組的指針
// newLen = 新的長度（= oldLen + num）
// oldCap = 原始切片的容量
// num = 正在添加的元素數量
// et = 元素類型
// 返回值:
// newPtr = 指向新底層存儲的指針
// newLen = 新的長度與傳參相同
// newCap = 新底層存儲的容量
//
// 要求 uint(newLen) > uint(oldCap)。
// 假設原始切片的長度為 newLen - num
//
// 分配一個至少能容納 newLen 個元素的新底層存儲。
// 已存在的條目 [0, oldLen) 被復制到新的底層存儲中。
// 添加的條目 [oldLen, newLen) 不會被 growslice 初始化
// （雖然對于包含指針的元素類型，它們會被清零）。調用者必須初始化這些條目。
// 尾隨條目 [newLen, newCap) 被清零。
//
// growslice 的特殊調用約定使得調用此函數的生成代碼更簡單。特別是，它接受并返回
// 新的長度，這樣舊的長度不需要被保留/恢復，而新的長度返回時也不需要被保留/恢復。
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {oldLen := newLen - num// ... 函數非核心部分省略if newLen < 0 {panic(errorString("growslice: len out of range"))}if et.Size_ == 0 {// append不應該創建一個指針為nil但長度非零的切片。// 我們假設在這種情況下，append不需要保留oldPtr。return slice{unsafe.Pointer(&zerobase), newLen, newLen}}// 1.計算新容量newcap := nextslicecap(newLen, oldCap)var overflow boolvar lenmem, newlenmem, capmem uintptr// 針對常見的 et.Size 進行優化// 對于1我們不需要任何除法/乘法。// 對于 goarch.PtrSize, 編譯器會優化除法/乘法為一個常量移位。// 對于2的冪，使用變量移位。noscan := !et.Pointers()// 2.內存對齊switch {case et.Size_ == 1:lenmem = uintptr(oldLen)newlenmem = uintptr(newLen)capmem = roundupsize(uintptr(newcap), noscan)overflow = uintptr(newcap) > maxAllocnewcap = int(capmem)case et.Size_ == goarch.PtrSize:lenmem = uintptr(oldLen) * goarch.PtrSizenewlenmem = uintptr(newLen) * goarch.PtrSizecapmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)overflow = uintptr(newcap) > maxAlloc/goarch.PtrSizenewcap = int(capmem / goarch.PtrSize)case isPowerOfTwo(et.Size_):var shift uintptrif goarch.PtrSize == 8 {shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63} else {shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31}lenmem = uintptr(oldLen) << shiftnewlenmem = uintptr(newLen) << shiftcapmem = roundupsize(uintptr(newcap)<<shift, noscan)overflow = uintptr(newcap) > (maxAlloc >> shift)newcap = int(capmem >> shift)capmem = uintptr(newcap) << shiftdefault:lenmem = uintptr(oldLen) * et.Size_newlenmem = uintptr(newLen) * et.Size_capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))capmem = roundupsize(capmem, noscan)newcap = int(capmem / et.Size_)capmem = uintptr(newcap) * et.Size_}// ... 函數非核心部分省略
}核心代碼:
// nextslicecap 計算下一個合適的切片容量。
// 該函數用于在切片需要擴容時，確定新的容量大小。
//  newLen: 切片的新長度（所需容量）。
//  oldCap: 切片的舊容量。
// 返回值: 新的切片容量。
func nextslicecap(newLen, oldCap int) int {newcap := oldCap // 將新的容量初始化為舊的容量doublecap := newcap + newcap // 計算舊容量的兩倍// 如果新長度大于舊容量的兩倍，則直接使用新長度作為新容量// 這是為了避免頻繁的擴容操作，當所需長度遠大于當前容量時，直接分配所需的空間if newLen > doublecap {return newLen}// 設置一個閾值，用于區分小切片和大切片const threshold = 256// 對于容量小于閾值的小切片，新容量直接設置為舊容量的兩倍// 這是因為小切片的擴容成本相對較低if oldCap < threshold {return doublecap}// 對于容量大于等于閾值的大切片，采用更保守的擴容策略for {//  從2倍增長（小切片）過渡到1.25倍增長（大切片）。//  該公式在兩者之間提供平滑的過渡。//  (newcap + 3*threshold) >> 2 等價于 (newcap + 3*threshold) / 4//  這使得新容量的增長比例在1.25到2之間，并隨著切片容量的增大而逐漸接近1.25newcap += (newcap + 3*threshold) >> 2// 需要檢查 `newcap >= newLen` 以及 `newcap` 是否溢出。// newLen 保證大于零，因此當 newcap 溢出時，`uint(newcap) > uint(newLen)` 不成立。// 這允許使用相同的比較來檢查兩者。// 使用uint類型進行比較是為了處理溢出情況。如果newcap溢出變成負數，轉換為uint類型后會變成一個很大的正數，從而使得比較仍然有效。if uint(newcap) >= uint(newLen) {break // 如果新容量足夠大，則退出循環}}//  當 newcap 計算溢出時，將 newcap 設置為請求的容量。//  如果 newcap 小于等于 0，說明發生了溢出if newcap <= 0 {return newLen}return newcap // 返回計算出的新容量
}// roundupsize 返回 mallocgc 為指定大小分配的內存塊的大小，減去任何用于元數據的內聯空間。
//  size: 請求分配的內存大小。
//  noscan:  如果為 true，則表示該內存塊不需要垃圾回收掃描。
// 返回值: mallocgc 實際分配的內存塊大小。
func roundupsize(size uintptr, noscan bool) (reqSize uintptr) {reqSize = size // 初始化請求大小// 處理小對象（小于等于 maxSmallSize-mallocHeaderSize）if reqSize <= maxSmallSize-mallocHeaderSize {// 小對象。// 如果需要垃圾回收掃描 (noscan 為 false) 并且大小大于 minSizeForMallocHeader，則添加 mallocHeaderSize 用于存儲元數據。// heapBitsInSpan(reqSize) 用于檢查對象是否足夠小到可以存儲在堆的位圖中，如果可以，則不需要 mallocHeader。if !noscan && reqSize > minSizeForMallocHeader { // !noscan && !heapBitsInSpan(reqSize)reqSize += mallocHeaderSize}// (reqSize - size) 為 mallocHeaderSize 或 0。如果添加了 mallocHeaderSize，我們需要從結果中減去它，因為 mallocgc 會再次添加它。// 這里是為了確保返回的大小是 mallocgc 實際分配的大小，而不是包含了頭部之后的大小。// 進一步區分更小的對象和中等大小的對象，使用不同的查找表進行向上取整if reqSize <= smallSizeMax-8 {// 對于非常小的對象，使用 size_to_class8 和 class_to_size 查找表進行向上取整，以 8 字節為粒度。// divRoundUp(reqSize, smallSizeDiv) 計算 reqSize 在 smallSizeDiv 粒度下的向上取整值。// class_to_size[...] 獲取對應大小類的實際分配大小。// 最后減去 (reqSize - size) 移除之前可能添加的 mallocHeaderSize。return uintptr(class_to_size[size_to_class8[divRoundUp(reqSize, smallSizeDiv)]]) - (reqSize - size)}// 對于中等大小的對象，使用 size_to_class128 和 class_to_size 查找表進行向上取整，以 128 字節為粒度。return uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size)}// 處理大對象（大于 maxSmallSize-mallocHeaderSize）// 大對象。將 reqSize 向上對齊到下一頁。檢查溢出。reqSize += pageSize - 1 // 將 reqSize 增加到下一頁邊界之前// 檢查溢出。如果 reqSize 加上 pageSize - 1 后反而變小了，說明發生了溢出。if reqSize < size {return size // 返回原始大小，避免分配過大的內存}// 通過按位與運算將 reqSize 對齊到下一頁邊界。return reqSize &^ (pageSize - 1)
}

三、問題

【引申1】 [3]int 和 [4]int 是同一個類型嗎？

不是。因為數組的長度是類型的一部分，這是與 slice 不同的一點。

【引申2】 下面的代碼輸出是什么？

說明：例子來自雨痕大佬《Go學習筆記》第四版，P43頁。這里我會進行擴展，并會作圖詳細分析。

package mainimport "fmt"func main() {slice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}s1 := slice[2:5]s2 := s1[2:6:7]s2 = append(s2, 100)s2 = append(s2, 200)s1[2] = 20fmt.Println(s1)fmt.Println(s2)fmt.Println(slice)
}

結果：

[2 3 20]
[4 5 6 7 100 200]
[0 1 2 3 20 5 6 7 100 9]

s1 從 slice 索引2（閉區間）到索引5（開區間，元素真正取到索引4），長度為3，容量默認到數組結尾，為8。 s2 從 s1 的索引2（閉區間）到索引6（開區間，元素真正取到索引5），容量到索引7（開區間，真正到索引6），為5。

接著，向 s2 尾部追加一個元素 100：

s2 = append(s2, 100) 

s2 容量剛好夠，直接追加。不過，這會修改原始數組對應位置的元素。這一改動，數組和 s1 都可以看得到。

再次向 s2 追加元素200：

s2 = append(s2, 200) 

這時，s2 的容量不夠用，該擴容了。于是，s2 另起爐灶，將原來的元素復制新的位置，擴大自己的容量。并且為了應對未來可能的 append 帶來的再一次擴容，s2 會在此次擴容的時候多留一些 buffer，將新的容量將擴大為原始容量的2倍，也就是10了。

最后，修改 s1 索引為2位置的元素：

s1[2] = 20

這次只會影響原始數組相應位置的元素。它影響不到 s2 了，人家已經遠走高飛了。

再提一點，打印 s1 的時候，只會打印出 s1 長度以內的元素。所以，只會打印出3個元素，雖然它的底層數組不止3個元素。

參考鏈接

1.Go 程序員面試筆試寶典

2.《Go學習筆記》

3.golangSlice的擴容規則