登录
首页 >  Golang >  Go教程

golang切片原理详细解析

来源:脚本之家

时间:2023-02-24 19:34:20 280浏览 收藏

本篇文章向大家介绍《golang切片原理详细解析》,主要包括原理、切片,具有一定的参考价值,需要的朋友可以参考一下。

切片的解析

当我们的代码敲下[]时,便会被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 

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]赋予切片。
  • 如果发生了内存逃逸,切片会调用运行时函数makeslicemakeslice64在堆中完成对切片的初始化。
// 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 

切片在栈中初始化还是在堆中初始化,存在一个临界值进行判断。临界值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  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 

根据切片的运行时结构定义,运行时切片结构底层维护着切片的长度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: %v\n", slic1)
slic[0] = 0
fmt.Printf("slic: %v\n", slic)
fmt.Printf("slic1: %v\n", 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): %v\n", len(slic))
fmt.Printf("cap(slic): %v\n", cap(slic))
fmt.Printf("len(slic1): %v\n", len(slic1))
fmt.Printf("cap(slic1): %v\n", cap(slic1))
fmt.Printf("len(slic2): %v\n", len(slic2))
fmt.Printf("cap(slic2): %v\n", 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: %p\n", slic)
fmt.Printf("slic1: %p\n", 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 

切片的扩容

切片元素个数可以动态变化,切片初始化后会确定一个初始化容量,当容量不足时会在运行时通过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 

从growslice的代码可以看出:

  • 当新申请的容量(cap)大于二倍旧容量(old.cap)时,最终容量(newcap)是新申请的容量;
  • 当新申请的容量(cap)小于二倍旧容量(old.cap)时,
    • 如果旧容量小于256,最终容量为旧容量的2倍;
    • 如果旧容量大于等于256,则会按照公式newcap += (newcap + 3*threshold) / 4来确定最终容量。实际的表现为:
  1. 当切片长度小于等于1024时,最终容量是旧容量的2倍;
  2. 当切片长度大于1024时,最终容量是旧容量的1.25倍,随着长度的增长,大于1.25倍;
  3. 扩容后,会通过memmove()函数将旧的数组移动到新的地址,因此扩容后新的切片一般和原来的地址不同。

示例:

var slic []int
oldCap := cap(slic)
for i := 0; i 

总结

切片在编译时定义为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学习网公众号,给大家分享更多Golang知识!

声明:本文转载于:脚本之家 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表