Go切片(Slice)浅析

由于Go的Array创建之后长度就固定了，因此我们会更常用到Slice。
在本篇里我们将从Slice的创建，访问，增加，复制几个方面来简单了解下Slice的原理。

struct

下面是Slice在runtime的结构体

type slice struct {
    array unsafe.Pointer   // 指向切片头
    len   int   //  切片吧长度
    cap   int  // 切片容积
}

复制代码

创建

在编译时的Phase 6阶段，会进行逃逸分析，如果Slice发生逃逸或非常大时，会调用makeSlice64在堆上创建，否则就会在栈上或者静态存储区创建Slice。

walk

case OMAKESLICE:
  ...
  if n.Esc == EscNone {
    对于在栈上的将会转成以下类似代码
    // var arr [r]T
    // n = arr[:l]
    ...
  }else {
   对于在堆上创建的，将会调用makeslice64
   ...
    fnname := "makeslice64"
    ...
    m.Left = mkcall1(fn, types.Types[TUNSAFEPTR], init, typename(t.Elem()), conv(len, argtype), conv(cap, argtype))
    ...
  }

复制代码

makeslice

func makeslice(et *_type, len, cap int) unsafe.Pointer {
    校验cap长度
    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 < 0 {
            panicmakeslicelen()
        }
        panicmakeslicecap()
    }
    分配内存
    return mallocgc(mem, et, true)
}

复制代码

访问

Slice的访问在编译时就已经转化成了汇编代码，由于Slice的结构中的array指向的数组头的地址，而且Slice是一片连续的地址，访问就是从头往后数，具体逻辑在编译时的typecheck1的OINDEX中。

func typecheck1(n *Node, top int) (res *Node) {
    ...
    switch n.Op {
    case OINDEX:
    ...
    switch t.Etype {
        case TSTRING, TARRAY, TSLICE:
            n.Right = indexlit(n.Right)
            if t.IsString() {
                n.Type = types.Bytetype
            } else {
                n.Type = t.Elem()
            }
            why := "string"
            if t.IsArray() {
                why = "array"
            } else if t.IsSlice() {
                why = "slice"
            }
            ...
    }
}

复制代码

增加

Slice的插入，删除等操作其实都是通过append函数来进行的，在append中，会经过一系列转化之后，调用到runtime的growslice方法，growslice会通过容量的大小进行不同的扩容策略，最后在进行迁移。

func growslice(et *_type, old slice, cap int) slice {
    ...
    通过容量进行扩容选择，减少频繁扩容之后进行迁移
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 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}
}

复制代码

复制

切片的复制是Slice在运行时里有实现，在编译时里，会通过HasHeapPointer来判断Slice是否存在堆上，是就会进行slicecopy操作，不是的话就会调用memmove对内存进行复制。

walk

func copyany(n *Node, init *Nodes, runtimecall bool) *Node {
    判断是否实在堆上创建
    if n.Left.Type.Elem().HasHeapPointer() {
        Curfn.Func.setWBPos(n.Pos)
        fn := writebarrierfn("typedslicecopy", n.Left.Type, n.Right.Type)
        return mkcall1(fn, n.Type, init, typename(n.Left.Type.Elem()), n.Left, n.Right)
    }
    ....
    fn := syslook("memmove")
    fn = substArgTypes(fn, nl.Type.Elem(), nl.Type.Elem())
}
复制代码

slicecopy

func slicecopy(to, fm slice, width uintptr) int {
    if fm.len == 0 || to.len == 0 {
        return 0
    }

    n := fm.len
    if to.len < n {
        n = to.len
    }

    if width == 0 {
        return n
    }

    if raceenabled {
        callerpc := getcallerpc()
        pc := funcPC(slicecopy)
        racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
        racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
    }
    if msanenabled {
        msanwrite(to.array, uintptr(n*int(width)))
        msanread(fm.array, uintptr(n*int(width)))
    }
    通过一系列判断最后走下面的if进行复制
    size := uintptr(n) * width
    if size == 1 { // common case worth about 2x to do here
        // TODO: is this still worth it with new memmove impl?
        *(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
    } else {
        memmove(to.array, fm.array, size)
    }
    return n
}
复制代码

结语

• 减少Slice的逃逸，给GC减负
• 合理分配cap，减少append时的迁移