golang切片原理詳細解析

2022-06-29 14:03:00

切片的解析

當我們的程式碼敲下[]時，便會被go編譯器解析為抽象語法樹上的切片節點, 被初始化為切片表示式SliceType:

// go/src/cmd/compile/internal/syntax/parser.go
// TypeSpec = identifier [ TypeParams ] [ "=" ] Type .
func (p *parser) typeDecl(group *Group) Decl {
    ...
    if p.tok == _Lbrack {
        // d.Name "[" ...
        // array/slice type or type parameter list
        pos := p.pos()
        p.next()
        switch p.tok {
        ...
        case _Rbrack:
            // d.Name "[" "]" ...
            p.next()
            d.Type = p.sliceType(pos)
        ...
        }
    } 
    ...
}
func (p *parser) sliceType(pos Pos) Expr {
    t := new(SliceType)
    t.pos = pos
    t.Elem = p.type_()
    return t
}
// go/src/cmd/compile/internal/syntax/nodes.go
type (
    ...
  // []Elem
    SliceType struct {
        Elem Expr
        expr
    }
  ...
)

編譯時切片定義為Slice結構體，屬性只包含同一型別的元素Elem，編譯時通過NewSlice()函數進行建立：

// go/src/cmd/compile/internal/types/type.go
type Slice struct {
    Elem *Type // element type
}
func NewSlice(elem *Type) *Type {
    if t := elem.cache.slice; t != nil {
        if t.Elem() != elem {
            base.Fatalf("elem mismatch")
        }
        if elem.HasTParam() != t.HasTParam() || elem.HasShape() != t.HasShape() {
            base.Fatalf("Incorrect HasTParam/HasShape flag for cached slice type")
        }
        return t
    }
    t := newType(TSLICE)
    t.extra = Slice{Elem: elem}
    elem.cache.slice = t
    if elem.HasTParam() {
        t.SetHasTParam(true)
    }
    if elem.HasShape() {
        t.SetHasShape(true)
    }
    return t
}

切片的初始化

切片有兩種初始化方式，一種宣告即初始化稱為字面量初始化，一種稱為make初始化，

例如:

litSlic := []int{1,2,3,4}  // 字面量初始化
makeSlic := make([]int,0)  // make初始化

字面量初始化

切片字面量的初始化是在生成抽象語法樹後進行遍歷的walk階段完成的。通過walkComplit方法，首先會進行型別檢查，此時會計算出切片元素的個數length，然後通過slicelit方法完成具體的初始化工作。整個過程會先建立一個陣列儲存於靜態區(static array)，並在堆區建立一個新的切片(auto array)，然後將靜態區的資料複製到堆區(copy the static array to the auto array)，對於切片中的元素會按索引位置一個一個的進行賦值。在程式啟動時這一過程會加快切片的初始化。

// go/src/cmd/compile/internal/walk/complit.go
// walkCompLit walks a composite literal node:
// OARRAYLIT, OSLICELIT, OMAPLIT, OSTRUCTLIT (all CompLitExpr), or OPTRLIT (AddrExpr).
func walkCompLit(n ir.Node, init *ir.Nodes) ir.Node {
    if isStaticCompositeLiteral(n) && !ssagen.TypeOK(n.Type()) {
        n := n.(*ir.CompLitExpr) // not OPTRLIT
        // n can be directly represented in the read-only data section.
        // Make direct reference to the static data. See issue 12841.
        vstat := readonlystaticname(n.Type())
        fixedlit(inInitFunction, initKindStatic, n, vstat, init)
        return typecheck.Expr(vstat)
    }
    var_ := typecheck.Temp(n.Type())
    anylit(n, var_, init)
    return var_
}

型別檢查時，計算出切片長度的過程為:

// go/src/cmd/compile/internal/typecheck/expr.go
func tcCompLit(n *ir.CompLitExpr) (res ir.Node) {
    ...
    t := n.Type()
    base.AssertfAt(t != nil, n.Pos(), "missing type in composite literal")

    switch t.Kind() {
    ...
    case types.TSLICE:
        length := typecheckarraylit(t.Elem(), -1, n.List, "slice literal")
        n.SetOp(ir.OSLICELIT)
        n.Len = length
    ...
  }
    return n
}

切片的具體初始化過程為:

在靜態儲存區建立一個陣列；
將陣列賦值給一個常數部分；
建立一個自動指標即切片分配到堆區，並指向陣列；
將陣列中的資料從靜態區拷貝到切片的堆區；
對每一個切片元素按索引位置分別進行賦值；
最後將分配到堆區的切片賦值給定義的變數；

原始碼通過註釋也寫明瞭整個過程。

// go/src/cmd/compile/internal/walk/complit.go
func anylit(n ir.Node, var_ ir.Node, init *ir.Nodes) {
    t := n.Type()
    switch n.Op() {
  ...
  case ir.OSLICELIT:
        n := n.(*ir.CompLitExpr)
        slicelit(inInitFunction, n, var_, init)
  ...
  }
}
func slicelit(ctxt initContext, n *ir.CompLitExpr, var_ ir.Node, init *ir.Nodes) {
    // make an array type corresponding the number of elements we have
    t := types.NewArray(n.Type().Elem(), n.Len)
    types.CalcSize(t)

    if ctxt == inNonInitFunction {
        // put everything into static array
        vstat := staticinit.StaticName(t)

        fixedlit(ctxt, initKindStatic, n, vstat, init)
        fixedlit(ctxt, initKindDynamic, n, vstat, init)

        // copy static to slice
        var_ = typecheck.AssignExpr(var_)
        name, offset, ok := staticinit.StaticLoc(var_)
        if !ok || name.Class != ir.PEXTERN {
            base.Fatalf("slicelit: %v", var_)
        }
        staticdata.InitSlice(name, offset, vstat.Linksym(), t.NumElem())
        return
    }

    // recipe for var = []t{...}
    // 1. make a static array
    //  var vstat [...]t
    // 2. assign (data statements) the constant part
    //  vstat = constpart{}
    // 3. make an auto pointer to array and allocate heap to it
    //  var vauto *[...]t = new([...]t)
    // 4. copy the static array to the auto array
    //  *vauto = vstat
    // 5. for each dynamic part assign to the array
    //  vauto[i] = dynamic part
    // 6. assign slice of allocated heap to var
    //  var = vauto[:]
    //
    // an optimization is done if there is no constant part
    //  3. var vauto *[...]t = new([...]t)
    //  5. vauto[i] = dynamic part
    //  6. var = vauto[:]

    // if the literal contains constants,
    // make static initialized array (1),(2)
    var vstat ir.Node

    mode := getdyn(n, true)
    if mode&initConst != 0 && !isSmallSliceLit(n) {
        if ctxt == inInitFunction {
            vstat = readonlystaticname(t)
        } else {
            vstat = staticinit.StaticName(t)
        }
        fixedlit(ctxt, initKindStatic, n, vstat, init)
    }

    // make new auto *array (3 declare)
    vauto := typecheck.Temp(types.NewPtr(t))

    // set auto to point at new temp or heap (3 assign)
    var a ir.Node
    if x := n.Prealloc; x != nil {
        // temp allocated during order.go for dddarg
        if !types.Identical(t, x.Type()) {
            panic("dotdotdot base type does not match order's assigned type")
        }
        a = initStackTemp(init, x, vstat)
    } else if n.Esc() == ir.EscNone {
        a = initStackTemp(init, typecheck.Temp(t), vstat)
    } else {
        a = ir.NewUnaryExpr(base.Pos, ir.ONEW, ir.TypeNode(t))
    }
    appendWalkStmt(init, ir.NewAssignStmt(base.Pos, vauto, a))

    if vstat != nil && n.Prealloc == nil && n.Esc() != ir.EscNone {
        // If we allocated on the heap with ONEW, copy the static to the
        // heap (4). We skip this for stack temporaries, because
        // initStackTemp already handled the copy.
        a = ir.NewStarExpr(base.Pos, vauto)
        appendWalkStmt(init, ir.NewAssignStmt(base.Pos, a, vstat))
    }

    // put dynamics into array (5)
    var index int64
    for _, value := range n.List {
        if value.Op() == ir.OKEY {
            kv := value.(*ir.KeyExpr)
            index = typecheck.IndexConst(kv.Key)
            if index < 0 {
                base.Fatalf("slicelit: invalid index %v", kv.Key)
            }
            value = kv.Value
        }
        a := ir.NewIndexExpr(base.Pos, vauto, ir.NewInt(index))
        a.SetBounded(true)
        index++
        // TODO need to check bounds?
        switch value.Op() {
        case ir.OSLICELIT:
            break
        case ir.OARRAYLIT, ir.OSTRUCTLIT:
            value := value.(*ir.CompLitExpr)
            k := initKindDynamic
            if vstat == nil {
                // Generate both static and dynamic initializations.
                // See issue #31987.
                k = initKindLocalCode
            }
            fixedlit(ctxt, k, value, a, init)
            continue
        }
        if vstat != nil && ir.IsConstNode(value) { // already set by copy from static value
            continue
        }
        // build list of vauto[c] = expr
        ir.SetPos(value)
        as := ir.NewAssignStmt(base.Pos, a, value)
        appendWalkStmt(init, orderStmtInPlace(typecheck.Stmt(as), map[string][]*ir.Name{}))
    }
    // make slice out of heap (6)
    a = ir.NewAssignStmt(base.Pos, var_, ir.NewSliceExpr(base.Pos, ir.OSLICE, vauto, nil, nil, nil))
    appendWalkStmt(init, orderStmtInPlace(typecheck.Stmt(a), map[string][]*ir.Name{}))
}

make初始化

當使用make初始化一個切片時，會被編譯器解析為一個OMAKESLICE操作:

// go/src/cmd/compile/internal/walk/expr.go
func walkExpr1(n ir.Node, init *ir.Nodes) ir.Node {
    switch n.Op() {
    ...
    case ir.OMAKESLICE:
        n := n.(*ir.MakeExpr)
        return walkMakeSlice(n, init)
    ...
}

如果make初始化一個較大的切片則會逃逸到堆中，如果分配了一個較小的切片則直接在棧中分配。

在walkMakeSlice函數中，如果未指定切片的容量Cap，則初始容量等於切片的長度。
如果切片的初始化未發生記憶體逃逸n.Esc() == ir.EscNone，則會先在記憶體中建立一個同樣容量大小的陣列NewArray(), 然後按切片長度將陣列中的值arr[:l]賦予切片。
如果發生了記憶體逃逸，切片會呼叫執行時函數makeslice和makeslice64在堆中完成對切片的初始化。

// go/src/cmd/compile/internal/walk/builtin.go
func walkMakeSlice(n *ir.MakeExpr, init *ir.Nodes) ir.Node {
    l := n.Len
    r := n.Cap
    if r == nil {
        r = safeExpr(l, init)
        l = r
    }
    ...
    if n.Esc() == ir.EscNone {
        if why := escape.HeapAllocReason(n); why != "" {
            base.Fatalf("%v has EscNone, but %v", n, why)
        }
        // var arr [r]T
        // n = arr[:l]
        i := typecheck.IndexConst(r)
        if i < 0 {
            base.Fatalf("walkExpr: invalid index %v", r)
        }
        ...
        t = types.NewArray(t.Elem(), i) // [r]T
        var_ := typecheck.Temp(t)
        appendWalkStmt(init, ir.NewAssignStmt(base.Pos, var_, nil))  // zero temp
        r := ir.NewSliceExpr(base.Pos, ir.OSLICE, var_, nil, l, nil) // arr[:l]
        // The conv is necessary in case n.Type is named.
        return walkExpr(typecheck.Expr(typecheck.Conv(r, n.Type())), init)
    }
    // n escapes; set up a call to makeslice.
    // When len and cap can fit into int, use makeslice instead of
    // makeslice64, which is faster and shorter on 32 bit platforms.
    len, cap := l, r
    fnname := "makeslice64"
    argtype := types.Types[types.TINT64]
    // Type checking guarantees that TIDEAL len/cap are positive and fit in an int.
    // The case of len or cap overflow when converting TUINT or TUINTPTR to TINT
    // will be handled by the negative range checks in makeslice during runtime.
    if (len.Type().IsKind(types.TIDEAL) || len.Type().Size() <= types.Types[types.TUINT].Size()) &&
        (cap.Type().IsKind(types.TIDEAL) || cap.Type().Size() <= types.Types[types.TUINT].Size()) {
        fnname = "makeslice"
        argtype = types.Types[types.TINT]
    }
    fn := typecheck.LookupRuntime(fnname)
    ptr := mkcall1(fn, types.Types[types.TUNSAFEPTR], init, reflectdata.TypePtr(t.Elem()), typecheck.Conv(len, argtype), typecheck.Conv(cap, argtype))
    ptr.MarkNonNil()
    len = typecheck.Conv(len, types.Types[types.TINT])
    cap = typecheck.Conv(cap, types.Types[types.TINT])
    sh := ir.NewSliceHeaderExpr(base.Pos, t, ptr, len, cap)
    return walkExpr(typecheck.Expr(sh), init)
}

切片在棧中初始化還是在堆中初始化，存在一個臨界值進行判斷。臨界值maxImplicitStackVarSize預設為64kb。從下面的原始碼可以看到，顯式變數宣告explicit variable declarations 和隱式變數implicit variables逃逸的臨界值並不一樣。

當我們使用var變數宣告以及:=賦值操作時，記憶體逃逸的臨界值為10M, 小於該值的物件會分配在棧中。
當我們使用如下操作時，記憶體逃逸的臨界值為64kb，小於該值的物件會分配在棧中。

p := new(T)          
p := &T{}           
s := make([]T, n)    
s := []byte("...")

// go/src/cmd/compile/internal/ir/cfg.go
var (
    // maximum size variable which we will allocate on the stack.
    // This limit is for explicit variable declarations like "var x T" or "x := ...".
    // Note: the flag smallframes can update this value.
    MaxStackVarSize = int64(10 * 1024 * 1024)
    // maximum size of implicit variables that we will allocate on the stack.
    //   p := new(T)          allocating T on the stack
    //   p := &T{}            allocating T on the stack
    //   s := make([]T, n)    allocating [n]T on the stack
    //   s := []byte("...")   allocating [n]byte on the stack
    // Note: the flag smallframes can update this value.
    MaxImplicitStackVarSize = int64(64 * 1024)
    // MaxSmallArraySize is the maximum size of an array which is considered small.
    // Small arrays will be initialized directly with a sequence of constant stores.
    // Large arrays will be initialized by copying from a static temp.
    // 256 bytes was chosen to minimize generated code + statictmp size.
    MaxSmallArraySize = int64(256)
)

切片的make初始化就屬於s := make([]T, n)操作，當切片元素分配的記憶體大小大於64kb時, 切片會逃逸到堆中進行初始化。此時會呼叫執行時函數makeslice來完成這一個過程:

// go/src/runtime/slice.go
func makeslice(et *_type, len, cap int) unsafe.Pointer {
    mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    if overflow || mem > maxAlloc || len < 0 || len > cap {
        // NOTE: Produce a 'len out of range' error instead of a
        // 'cap out of range' error when someone does make([]T, bignumber).
        // 'cap out of range' is true too, but since the cap is only being
        // supplied implicitly, saying len is clearer.
        // See golang.org/issue/4085.
        mem, overflow := math.MulUintptr(et.size, uintptr(len))
        if overflow || mem > maxAlloc || len < 0 {
            panicmakeslicelen()
        }
        panicmakeslicecap()
    }
    return mallocgc(mem, et, true)
}

根據切片的執行時結構定義，執行時切片結構底層維護著切片的長度len、容量cap以及指向陣列資料的指標array:

// go/src/runtime/slice.go
type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}
// 或者
// go/src/reflect/value.go
// SliceHeader is the runtime representation of a slice.
type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

切片的擷取

從切片的執行時結構已經知道，切片底層資料是一個陣列，切片本身只是持有一個指向改陣列資料的指標。因此，當我們對切片進行擷取操作時，新的切片仍然指向原切片的底層資料，當對原切片資料進行更新時，意味著新切片相同索引位置的資料也發生了變化:

slic := []int{1, 2, 3, 4, 5}
slic1 := slic[:2]
fmt.Printf("slic1: %vn", slic1)
slic[0] = 0
fmt.Printf("slic: %vn", slic)
fmt.Printf("slic1: %vn", slic1)
// slic1: [1 2]
// slic: [0 2 3 4 5]
// slic1: [0 2]

切片擷取後，雖然底層資料沒有發生變化，但指向的資料範圍發生了變化，表現為擷取後的切片長度、容量會相應發生變化:

長度為擷取的範圍
容量為擷取起始位置到原切片末尾的範圍

slic := []int{1, 2, 3, 4, 5}
slic1 := slic[:2]
slic2 := slic[2:]
fmt.Printf("len(slic): %vn", len(slic))
fmt.Printf("cap(slic): %vn", cap(slic))
fmt.Printf("len(slic1): %vn", len(slic1))
fmt.Printf("cap(slic1): %vn", cap(slic1))
fmt.Printf("len(slic2): %vn", len(slic2))
fmt.Printf("cap(slic2): %vn", cap(slic2))
// len(slic): 5
// cap(slic): 5

// len(slic1): 2
// cap(slic1): 5

// len(slic2): 3
// cap(slic2): 3

所以，切片擷取變化的是底層data指標、長度以及容量，data指標指向的陣列資料本身沒有變化。切片的賦值拷貝就等價于于全切片，底層data指標仍然指向相同的陣列地址，長度和容量保持不變:

slic := []int{1, 2, 3, 4, 5}
s := slic  // 等價於 s := slic[:]

當切片作為引數傳遞時，即使切片中包含大量的資料，也只是切片資料地址的拷貝，拷貝的成本是較低的。

切片的複製

當我們想要完整拷貝一個切片時，可以使用內建的copy函數，效果類似於"深拷貝"。

slic := []int{1, 2, 3, 4, 5}
var slic1 []int
copy(slic1, slic)
fmt.Printf("slic: %pn", slic)
fmt.Printf("slic1: %pn", slic1)
// slic: 0xc0000aa030
// slic1: 0x0

完整複製後，新的切片指向了新的記憶體地址。切片的複製在執行時會呼叫slicecopy()函數，通過memmove行動資料到新的記憶體地址:

// go/src/runtime/slice.go
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
    if fromLen == 0 || toLen == 0 {
        return 0
    }

    n := fromLen
    if toLen < n {
        n = toLen
    }
    ...
    if size == 1 { // common case worth about 2x to do here
        // TODO: is this still worth it with new memmove impl?
        *(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
    } else {
        memmove(toPtr, fromPtr, size)
    }
    return n
}

切片的擴容

切片元素個數可以動態變化，切片初始化後會確定一個初始化容量，當容量不足時會在執行時通過growslice進行擴容:

func growslice(et *_type, old slice, cap int) slice {
    ...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
        if old.cap < threshold {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                // 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) / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    ...
    memmove(p, old.array, lenmem)
    return slice{p, old.len, newcap}
}

從growslice的程式碼可以看出：

當新申請的容量(cap)大於二倍舊容量(old.cap)時，最終容量(newcap)是新申請的容量；
當新申請的容量(cap)小於二倍舊容量(old.cap)時，
- 如果舊容量小於256，最終容量為舊容量的2倍；
- 如果舊容量大於等於256，則會按照公式newcap += (newcap + 3*threshold) / 4來確定最終容量。實際的表現為:

當切片長度小於等於1024時，最終容量是舊容量的2倍；
當切片長度大於1024時，最終容量是舊容量的1.25倍，隨著長度的增長，大於1.25倍；
擴容後，會通過memmove()函數將舊的陣列移動到新的地址，因此擴容後新的切片一般和原來的地址不同。

範例:

var slic []int
oldCap := cap(slic)
for i := 0; i < 2048; i++ {
  slic = append(slic, i)
  newCap := cap(slic)
  grow := float32(newCap) / float32(oldCap)
  if newCap != oldCap {
    fmt.Printf("len(slic):%v cap(slic):%v grow:%v %pn", len(slic), cap(slic), grow, slic)
  }
  oldCap = newCap
}
// len(slic):1     cap(slic):1     grow:+Inf       0xc0000140c0
// len(slic):2     cap(slic):2     grow:2          0xc0000140e0
// len(slic):3     cap(slic):4     grow:2          0xc000020100
// len(slic):5     cap(slic):8     grow:2          0xc00001e340
// len(slic):9     cap(slic):16    grow:2          0xc000026080
// len(slic):17    cap(slic):32    grow:2          0xc00007e000
// len(slic):33    cap(slic):64    grow:2          0xc000100000
// len(slic):65    cap(slic):128   grow:2          0xc000102000
// len(slic):129   cap(slic):256   grow:2          0xc000104000
// len(slic):257   cap(slic):512   grow:2          0xc000106000
// len(slic):513   cap(slic):1024  grow:2          0xc000108000
// len(slic):1025  cap(slic):1280  grow:1.25       0xc00010a000
// len(slic):1281  cap(slic):1696  grow:1.325      0xc000114000
// len(slic):1697  cap(slic):2304  grow:1.3584906  0xc00011e000

總結

切片在編譯時定義為Slice結構體，並通過NewSlice()函數進行建立；

type Slice struct {
  Elem *Type // element type
}

切片的執行時定義為slice結構體, 底層維護著指向陣列資料的指標，切片長度以及容量；

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

切片字面量初始化時，會在編譯時的型別檢查階段計算出切片的長度，然後在walk遍歷語法樹時建立底層陣列，並將切片中的每個字面量元素按索引賦值給陣列，切片的資料指標指向該陣列；
切片make初始化時，會呼叫執行時makeslice函數進行記憶體分配，當記憶體佔用大於64kb時會逃逸到堆中；
切片擷取後，底層陣列資料沒有發生變化，但指向的資料範圍發生了變化，表現為擷取後的切片長度、容量會相應發生變化:
- 長度為擷取的範圍
- 容量為擷取起始位置到原切片末尾的範圍
使用copy複製切片時，會在執行時會呼叫slicecopy()函數，通過memmove行動資料到了新的記憶體地址；
切片擴容是通過執行時growslice函數完成的，一般表現為：
- 當切片長度小於等於1024時，最終容量是舊容量的2倍；
- 當切片長度大於1024時，最終容量是舊容量的1.25倍，並隨著長度的增長，緩慢大於1.25倍；
- 擴容時會通過memmove()函數將舊的陣列移動到新的地址，因此擴容後地址會發生變化。

到此這篇關於golang切片原理詳細解析的文章就介紹到這了,更多相關golang切片內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！