Go

【原创】golang快速入门[9.3]-精深奥妙的切片功夫

2020-04-19  本文已影响0人  唯识相链2

前言

下面这段程序会输出什么？

package mainimport "fmt"func f(s []string, level int) {        if level > 5 {               return        }        s = append(s, fmt.Sprint(level))        f(s, level+1)        fmt.Println("level:", level, "slice:", s)}func main() {        f(nil, 0)}

level: 5 slice: [0 1 2 3 4 5]level: 4 slice: [0 1 2 3 4]level: 3 slice: [0 1 2 3]level: 2 slice: [0 1 2]level: 1 slice: [0 1]level: 0 slice: [0]

切片基本操作

type SliceHeader struct {    Data uintptr    Len  int    Cap  int}

切片的声明

//切片的声明1  //nilvar slice1 []int//切片的声明2var slice2 []int = make([]int,5)var slice3 []int = make([]int,5,7)numbers:= []int{1,2,3,4,5,6,7,8}

切片的截取

numbers:= []int{1,2,3,4,5,6,7,8}//从下标1一直到下标4，但是不包括下标4numbers1 :=numbers[1:4]//从下标0一直到下标3，但是不包括下标3numbers2 :=numbers[:3]//从下标3一直到结束numbers3 :=numbers[3:]

切片的长度与容量

    slice6 := make([]int,0)    fmt.Printf("len=%d,cap=%d,slice=%v\n",len(slice4),cap(slice4),slice4)

切片与数组的拷贝对比

    //数组是值类型    a := [4]int{1, 2, 3, 4}    //切片是引用类型    b := []int{100, 200, 300}    c := a    d := b    c[1] = 200    d[0] = 1    //output: c[1 200 3 4] a[1 2 3 4]    fmt.Println("a=", a, "c=", c)    //output: d[1 200 300]  b[1 200 300]    fmt.Println("b=", b, "d=", d)

切片追加元素：append

numbers := make([]int, 0, 20)//append一个元素numbers = append(numbers, 0)//append多个元素numbers = append(numbers, 1, 2, 3, 4, 5, 6, 7)//append添加切片s1 := []int{100, 200, 300, 400, 500, 600, 700}numbers = append(numbers, s1...)//now:[0 1 2 3 4 5 6 7 100 200 300 400 500 600 700]

经典案例: 切片删除

//    删除第一个元素numbers = numbers[1:]// 删除最后一个元素numbers = numbers[:len(numbers)-1]// 删除中间一个元素a := int(len(numbers) / 2)numbers = append(numbers[:a], numbers[a+1:]...)

经典案例：切片反转

// reverse reverses a slice of ints in place.func reverse(s []int) {    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {        s[i], s[j] = s[j], s[i]    }}

切片在编译时的特性

func NewSlice(elem *Type) *Type {    if t := elem.Cache.slice; t != nil {        if t.Elem() != elem {            Fatalf("elem mismatch")        }        return t    }    t := New(TSLICE)    t.Extra = Slice{Elem: elem}    elem.Cache.slice = t    return t}

// Slice contains Type fields specific to slice types.type Slice struct {    Elem *Type // element type}

编译时：字面量初始化

当我们使用字面量 []int{1, 2, 3} 创建新的切片时，会创建一个array数组([3]int{1,2,3})存储于静态区中。同时会创建一个变量。

// go/src/cmd/compile/internal/gc/sinit.gofunc slicelit(ctxt initContext, n *Node, var_ *Node, init *Nodes)

其抽象的过程如下:

var vstat [3]intvstat[0] = 1vstat[1] = 2vstat[2] = 3var vauto *[3]int = new([3]int)*vauto = vstatslice := vauto[:]

// 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[:]

编译时：make 初始化

func typecheck1(n *Node, top int) (res *Node) {switch t.Etype {case TSLICE:    if i >= len(args) {        yyerror("missing len argument to make(%v)", t)        n.Type = nil        return n    }    l = args[i]    i++    l = typecheck(l, ctxExpr)    var r *Node    if i < len(args) {        r = args[i]        i++        r = typecheck(r, ctxExpr)    }    if l.Type == nil || (r != nil && r.Type == nil) {        n.Type = nil        return n    }    if !checkmake(t, "len", l) || r != nil && !checkmake(t, "cap", r) {        n.Type = nil        return n    }    n.Left = l    n.Right = r    n.Op = OMAKESLICE

// 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)

func walkexpr(n *Node, init *Nodes) *Node{case OMAKESLICE:    ...    if n.Esc == EscNone {        // var arr [r]T        // n = arr[:l]        i := indexconst(r)        if i < 0 {            Fatalf("walkexpr: invalid index %v", r)        }        t = types.NewArray(t.Elem(), i) // [r]T        var_ := temp(t)        a := nod(OAS, var_, nil) // zero temp        a = typecheck(a, ctxStmt)        init.Append(a)        r := nod(OSLICE, var_, nil) // arr[:l]        r.SetSliceBounds(nil, l, nil)        r = conv(r, n.Type) // in case n.Type is named.        r = typecheck(r, ctxExpr)        r = walkexpr(r, init)        n = r    } else {        if t.Elem().NotInHeap() {            yyerror("%v is go:notinheap; heap allocation disallowed", t.Elem())        }        len, cap := l, r        fnname := "makeslice64"        argtype := types.Types[TINT64]        m := nod(OSLICEHEADER, nil, nil)        m.Type = t        fn := syslook(fnname)        m.Left = mkcall1(fn, types.Types[TUNSAFEPTR], init, typename(t.Elem()), conv(len, argtype), conv(cap, argtype))        m.Left.SetNonNil(true)        m.List.Set2(conv(len, types.Types[TINT]), conv(cap, types.Types[TINT]))        m = typecheck(m, ctxExpr)        m = walkexpr(m, init)        n = m    }

arr := [r]Tss := arr[:l]

// go/src/runtime/slice.gofunc 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)}func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {    len := int(len64)    if int64(len) != len64 {        panicmakeslicelen()    }    cap := int(cap64)    if int64(cap) != cap64 {        panicmakeslicecap()    }    return makeslice(et, len, cap)}

切片的扩容

a:= make([]int,3,4)append(a,1)

a:= make([]int,3,3)append(a,1)

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 {            for 0 < newcap && newcap < cap {                newcap += newcap / 4            }            if newcap <= 0 {                newcap = cap            }        }    }    ...}

    switch {    case et.size == 1:        lenmem = uintptr(old.len)        newlenmem = uintptr(cap)        capmem = roundupsize(uintptr(newcap))        overflow = uintptr(newcap) > maxAlloc        newcap = int(capmem)    case et.size == sys.PtrSize:        lenmem = uintptr(old.len) * sys.PtrSize        newlenmem = uintptr(cap) * sys.PtrSize        capmem = roundupsize(uintptr(newcap) * sys.PtrSize)        overflow = uintptr(newcap) > maxAlloc/sys.PtrSize        newcap = int(capmem / sys.PtrSize)    case isPowerOfTwo(et.size):        var shift uintptr        if sys.PtrSize == 8 {            // Mask shift for better code generation.            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63        } else {            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31        }        lenmem = uintptr(old.len) << shift        newlenmem = uintptr(cap) << shift        capmem = roundupsize(uintptr(newcap) << shift)        overflow = uintptr(newcap) > (maxAlloc >> shift)        newcap = int(capmem >> shift)    default:        lenmem = uintptr(old.len) * et.size        newlenmem = uintptr(cap) * et.size        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))        capmem = roundupsize(capmem)        newcap = int(capmem / et.size)    }

    if et.ptrdata == 0 {        p = mallocgc(capmem, nil, false)        // The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).        // Only clear the part that will not be overwritten.        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)    } else {        // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.        p = mallocgc(capmem, et, true)        if lenmem > 0 && writeBarrier.enabled {            // Only shade the pointers in old.array since we know the destination slice p            // only contains nil pointers because it has been cleared during alloc.            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)        }    }    memmove(p, old.array, lenmem)    return slice{p, old.len, newcap}

old = make([]int,3,3)new = append(old,1) => new = malloc(newcap * sizeof(int))   a[4]  = 0new[1] = old[1]new[2] = old[2]new[3] = old[3]

切片的截取

    old := make([]int64,3,3)    new := old[1:3]    fmt.Printf("%p %p",arr,slice)

输出为:

0xc000018140 0xc000018148

二者的地址正好相差了8个字节，这不是偶然的,而是因为二者指向了相同的数据源，刚好相差int64的大小。
另外我们也可以从生成的汇编的过程查看到到一些端倪

GOSSAFUNC=main GOOS=linux GOARCH=amd64 go tool compile main.go
image

在ssa的初始阶段start,old := make([]int64,3,3)对应的是SliceMake <[]int> v10 v15 v15, SliceMake操作�需要传递数组的指针、长度、容量。
而 new := old[1:3] 对应SliceMake <[]int> v34 v28 v29。传递的指针v34正好的原始的Ptr + 8个字节后的位置

下面列出一张图比较形象的表示切片引用相同数据源的图：

image

切片的复制

// 创建目标切片numbers1 := make([]int, len(numbers), cap(numbers)*2)// 将numbers的元素拷贝到numbers1中count := copy(numbers1, numbers)

slice := []byte("abcdefgh")var arr [4]bytecopy(arr[:], slice[:4])//或者直接如下,这涉及到一个特性,即只会拷贝min(len(arr),len(slice)copy(arr[:], slice)

func copyany(n *Node, init *Nodes, runtimecall bool) *Node {    ...    if runtimecall {        if n.Right.Type.IsString() {            fn := syslook("slicestringcopy")            fn = substArgTypes(fn, n.Left.Type, n.Right.Type)            return mkcall1(fn, n.Type, init, n.Left, n.Right)        }        fn := syslook("slicecopy")        fn = substArgTypes(fn, n.Left.Type, n.Right.Type)        return mkcall1(fn, n.Type, init, n.Left, n.Right, nodintconst(n.Left.Type.Elem().Width))    }    ...    fn := syslook("memmove")    fn = substArgTypes(fn, nl.Type.Elem(), nl.Type.Elem())    nwid := temp(types.Types[TUINTPTR])    setwid := nod(OAS, nwid, conv(nlen, types.Types[TUINTPTR]))    ne.Nbody.Append(setwid)    nwid = nod(OMUL, nwid, nodintconst(nl.Type.Elem().Width))    call := mkcall1(fn, nil, init, nto, nfrm, nwid)}

 init {   n := len(a)   if n > len(b) { n = len(b) }   if a.ptr != b.ptr { memmove(a.ptr, b.ptr, n*sizeof(elem(a))) } }

case OCOPY:    n = copyany(n, init, instrumenting && !compiling_runtime)case OGO:    switch n.Left.Op {    case OCOPY:        n.Left = copyany(n.Left, &n.Ninit, true)

func slicecopy(to, fm slice, width uintptr) int {    ...    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)))    }    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}

总结

前文

参考资料

喜欢本文的朋友欢迎点赞分享~

image

唯识相链启用微信交流群（Go与区块链技术）

欢迎加微信：ywj2271840211

上一篇 下一篇

猜你喜欢

热点阅读