Stories

Detail Return Return

Go源碼學習(基於1.24.1)-slice擴容機制-實踐才是真理 - Stories Detail

本文起於一次驗證slice擴容機制的測試,搜索引擎和AI給我們關於slice擴容機制的解釋大多是“低於1024翻倍,超過則乘1.25倍”(以下用“1024機制”代指),但是在我基於go1.24.1的結果卻完全不是這麼回事,難道是營銷號太多誤導我們了嗎?以下將結合源碼學習,實踐是檢驗真理的唯一標準。

一. 驗證我們隨手搜到的“1024機制”

    a := make([]int, 0, 512)
    for i := 0; i < 513; i++ {
        a = append(a, i)
    }
    fmt.Println(cap(a))    
    // 848

結果並不是預想中的1024,而是848

二. 擴容的過程是怎麼樣的?

1. 擴容的函數簽名

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice

參數:
oldPtr:原切片的數據指針(指向底層數組的起始地址)。
newLen:擴容後的新長度(原長度 + 新增元素數量num)。
oldCap:原切片的容量。
num:本次需要新增的元素數量(newLen = 原長度 + num)。
et:切片元素的類型信息(包含大小、是否含指針等元數據)。
返回值:擴容後的新切片(slice結構體,包含新數據指針、新長度、新容量)。

2. 核心邏輯:

oldLen := newLen - num  // 計算原切片的長度(新長度 = 原長度 + 新增元素數)
if raceenabled {
    callerpc := sys.GetCallerPC()
    racereadrangepc(oldPtr, uintptr(oldLen*int(et.Size_)), callerpc, abi.FuncPCABIInternal(growslice))
}
if msanenabled {
    msanread(oldPtr, uintptr(oldLen*int(et.Size_)))
}
if asanenabled {
    asanread(oldPtr, uintptr(oldLen*int(et.Size_)))
}
if newLen < 0 {
    panic(errorString("growslice: len out of range"))
}
if et.Size_ == 0 {
    // append should not create a slice with nil pointer but non-zero len.
    // We assume that append doesn't need to preserve oldPtr in this case.
    return slice{unsafe.Pointer(&zerobase), newLen, newLen}
}

擴容前先進行了一波校驗和處理,主要是獲取舊切片容量和特殊處理。

newcap := nextslicecap(newLen, oldCap)
然後看看關鍵的nextslicecap函數內部:
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 {
        // Transition from growing 2x for small slices
        // to growing 1.25x for large slices. This formula
        // gives a smooth-ish transition between the two.
        newcap += (newcap + 3*threshold) >> 2

        // We need to check `newcap >= newLen` and whether `newcap` overflowed.
        // newLen is guaranteed to be larger than zero, hence
        // when newcap overflows then `uint(newcap) > uint(newLen)`.
        // This allows to check for both with the same comparison.
        if uint(newcap) >= uint(newLen) {
            break
        }
    }

    // Set newcap to the requested cap when
    // the newcap calculation overflowed.
    if newcap <= 0 {
        return newLen
    }
    return newcap
}
很明顯並不是“1024機制”

這裏分三種情況:

首先計算 “2 倍舊容量”(doublecap)。
a. 如果需要的新長度(newLen)比 2 倍舊容量還大,説明 2 倍擴容都不夠,直接返回newLen(必須至少容納這麼多元素)。

b. 定義閾值threshold=256,對於容量小於 256 的 “小切片”,直接返回 2 倍舊容量,簡單高效。

c. 對於容量 ≥256 的切片進入循環計算新容量:
(newcap + 3 * threshold) >> 2 等價於 (newcap + 768) / 4
簡單點就是:newcap=(newcap * 1.25 + 192),不夠用就循環計算擴容
作用是讓切片擴容倍率從2無限趨近於1.25,避免大切片一下擴容太多浪費內存。

3. 看到這裏是不是以為結束了?並不是!

按上邊的邏輯,這段代碼打印的結果應該是(512 * 1.25 + 192) = 832,但為什麼是848呢?

    a := make([]int, 0, 512)
    for i := 0; i < 513; i++ {
        a = append(a, i)
    }
    fmt.Println(cap(a))    
    // 848

順着nextslicecap方法返回到growslice方法內,發現還有後續:

var overflow bool
var lenmem, newlenmem, capmem uintptr
noscan := !et.Pointers()  // 元素是否不包含指針(影響GC處理方式)

switch {
case et.Size_ == 1:  // 元素類型大小為1字節(如[]byte)
    lenmem = uintptr(oldLen)  // 原數據內存大小 = 原長度 * 1
    newlenmem = uintptr(newLen)  // 新長度內存大小 = 新長度 * 1
    capmem = roundupsize(uintptr(newcap), noscan)  // 新容量內存大小(向上對齊到內存頁)
    overflow = uintptr(newcap) > maxAlloc  // 檢查是否超過最大可分配內存
    newcap = int(capmem)  // 對齊後更新新容量

case et.Size_ == goarch.PtrSize:  // 元素類型大小等於指針大小(如[]*int)
    lenmem = uintptr(oldLen) * goarch.PtrSize
    newlenmem = uintptr(newLen) * goarch.PtrSize
    capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
    overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize  // 防止溢出
    newcap = int(capmem / goarch.PtrSize)  // 對齊後更新新容量

case isPowerOfTwo(et.Size_):  // 元素類型大小是2的冪(如2、4、8字節)
    var shift uintptr
    // 判斷32位和64位架構
    if goarch.PtrSize == 8 {
        // Mask shift for better code generation.
        shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
    } else {
        shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
    }
    // 用移位代替乘法(如8字節元素,8 = 2 ^ 3 x<<3)
    shift := uintptr(sys.TrailingZeros64(uint64(et.Size_)))  // 計算2的冪
    // 計算原切片數據佔用的內存大小:oldLen * et.Size_
    lenmem = uintptr(oldLen) << shift // oldLen=5,元素大小8字節(shift=3),lenmen = 5*8 = 5<<3 = 40
    // 計算新長度(newLen)對應的內存大小:newLen * et.Size_
    newlenmem = uintptr(newLen) << shift
    // 計算新容量(newcap)對應的內存大小,並向上對齊到內存頁大小
    // 先通過左移計算newcap*et.Size_,再調用roundupsize完成對齊
    capmem = roundupsize(uintptr(newcap)<<shift, noscan)
    // 檢查是否溢出:新容量對應的內存是否超過最大可分配內存maxAlloc
    overflow = uintptr(newcap) > (maxAlloc >> shift)
    // 根據對齊後的內存大小,反推新的容量(對齊後可能比原newcap大)
    // capmem是對齊後的總內存,除以元素大小(右移shift位)得到新容量
    newcap = int(capmem >> shift)
    // 重新計算對齊後新容量對應的準確內存大小(確保無偏差)
    capmem = uintptr(newcap) << shift

default:  // 其他元素類型大小(非2的冪)
    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_
}

按照原本的擴容newcap = 832,因為元素類型是int,在64位機器上佔8字節,這裏case到了isPowerOfTwo(et.Size_),經過一頓操作,來到了“848非832”的“罪魁禍首”:roundupsize內存對齊

4. 大火收汁:內存對齊

roundupsize函數簽名

func roundupsize(size uintptr, noscan bool) (reqSize uintptr) 

參數:
size:用户實際需要的內存大小(例如,切片擴容時 “元素數量 × 元素大小” 的理論值)。
noscan:布爾值,標記對象是否不包含指針(true 表示無需 GC 掃描,如 int 切片;false 表示包含指針,如 string 切片,因為 string 內部有指向字節數組的指針)。
返回值:reqSize,即對齊後的內存塊大小(分配器實際會分配的內存大小)。

roundupsize 函數是 Go 內存分配器中實現 “內存塊大小對齊” 的核心邏輯,它決定了最終分配的內存塊具體多大。其核心目標是:將用户請求的內存大小(如切片擴容時計算的理論內存)轉換為內存分配器預定義的 “標準塊大小”,以優化內存分配效率、減少碎片。

func roundupsize(size uintptr, noscan bool) (reqSize uintptr) {
    reqSize = size
    // maxSmallSize=32768    mallocHeaderSize=8
    if reqSize <= maxSmallSize-mallocHeaderSize {    // 小對象,32760B
        // Small object.
        if !noscan && reqSize > minSizeForMallocHeader { // !noscan && !heapBitsInSpan(reqSize)
            reqSize += mallocHeaderSize    // // 為含指針的對象增加元數據頭
        }
        // (reqSize - size) is either mallocHeaderSize or 0. We need to subtract mallocHeaderSize
        // from the result if we have one, since mallocgc will add it back in.
        // smallSizeMax = 1024
        if reqSize <= smallSizeMax-8 {    // 較小的小對象,1016B
            // smallSizeDiv = 8    
            return uintptr(class_to_size[size_to_class8[divRoundUp(reqSize, smallSizeDiv)]]) - (reqSize - size)
        }
        return uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size)
    }
    // Large object. Align reqSize up to the next page. Check for overflow.
    reqSize += pageSize - 1
    if reqSize < size {
        return size
    }
    return reqSize &^ (pageSize - 1)
}

函數邏輯可分為 “小對象處理” 和 “大對象處理” 兩部分,核心差異在於對齊策略(小對象用預定義規格,大對象按頁對齊)。

a. 小對象處理(容量≤32760 字節,最常見,切片擴容多屬於此類)

若對象 包含指針(!noscan,如 string 切片),且大小超過 minSizeForMallocHeader(通常為 16 字節),則需要額外添加 mallocHeaderSize(8 字節)的元數據頭,用於 GC 跟蹤指針。
若對象 不包含指針(noscan,如 int 切片),則無需添加,節省內存。

看到這裏,第一反應就是string的切片在內存對齊後跟int不一定一樣,沒錯確實不一樣,具體可以自行測試。

Go 內存分配器預定義了一系列 “高效內存塊規格”(size classes),小對象必須對齊到這些規格。根據大小不同,分為兩類映射:

較小的小對象(矮個子裏的侏儒)(容量 ≤ 1016 字節):

return uintptr(class_to_size[size_to_class8[divRoundUp(reqSize, smallSizeDiv)]]) - (reqSize - size)

divRoundUp(a, b):a 按 b 向上取整,例如,divRoundUp(9, 8) = (9 + 8 - 1) / 8 = 2
size_to_class8:預定義數組,將 “8 字節步長取整後的索引” 映射到對應的 “內存塊類別”(每個類別對應一個標準大小)。
class_to_size:預定義數組,根據 “內存塊類別” 返回該類別的實際大小(標準塊大小)。

較大的小對象(矮個子裏挑高個)( 1016字節 < 容量 ≤ 32760字節):

return uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size)

邏輯類似侏儒對象,但按 128 字節步長(largeSizeDiv=128)計算,使用 size_to_class128 映射表。

b. 大對象處理(超過小對象閾值)

直接按操作系統頁大小對齊

// 向上對齊到下一個頁邊界
reqSize += pageSize - 1  // 例如,pageSize=4096,1000 → 1000+4095=5095
if reqSize < size {  // 檢查溢出(防止數值超過 uintptr 最大值)
    return size
}
return reqSize &^ (pageSize - 1)  // 按頁對齊(5095 &^ 4095 = 4096)

大對象通常直接從操作系統申請內存,按頁對齊可最大化內存訪問效率(與 CPU 緩存、內存頁管理匹配)。

三. 回到開頭

還記得文章開頭的測試嗎?我們測試的是一個int元素的切片,內存對齊前計算得到newcap=832,內存對齊的時候計算832 * 8 = 6656字節,屬於“較大的小對象”,所以最終計算得到內存對齊結果為6784,最終容量為6784/8=848

四. 為什麼很多文章説的是“1024機制”呢?

經過簡單的查詢得知,在go1.18版本之前都是符合“1024機制”,1.18後就更新成現在這樣了,所以如果在go1.18版本發佈後,也就是2022年3月15日之後,再不基於版本直接鎖死"1024機制"的文章,可以放心避雷了,因為大概率是不經過求證而複製粘貼或者直接AI生成不經過人腦思考的。

Add a new Comments

Some HTML is okay.