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

weishixianglian · 2020年04月19日 · 962 次阅读

golang 快速入门 [9.2]-精深奥妙的切片功夫

前言

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

package main
import "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]
    
  • 如果对输出结果有一些疑惑,你需要了解这篇文章的内容

  • 如果你知道了结果,你仍然需要了解这篇文章的内容,因为本文完整介绍了

    • 切片的典型用法
    • 切片的陷阱
    • 切片的逃逸分析
    • 切片的扩容
    • 切片在编译与运行时的研究
  • 如果你啥都知道了,请直接滑动最下方,双击 666.

切片基本操作

  • 切片是某种程度上和其他语言 (例如 C 语言) 中的数组在使用中有许多相似之处,但是 go 语言中的切片有许多独特之处
  • Slice(切片)代表变长的序列,序列中每个元素都有相同的类型。
  • 一个 slice 类型一般写作[]T,其中 T 代表 slice 中元素的类型;slice 的语法和数组很像,但是没有固定长度。
  • 数组和 slice 之间有着紧密的联系。一个 slice 是一个轻量级的数据结构,提供了访问数组子序列(或者全部)元素的功能。一个 slice 在运行时由三个部分构成:指针、长度和容量。 type SliceHeader struct { Data uintptr Len int Cap int }
  • 指针指向第一个 slice 元素对应的底层数组元素的地址
  • 长度对应 slice 中元素的数目;长度不能超过容量
  • 容量一般是从 slice 的开始位置到底层数据的结尾位置的长度

切片的声明

//切片的声明1  //nil
var slice1 []int

//切片的声明2
var 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,但是不包括下标4
numbers1 :=numbers[1:4]
//从下标0一直到下标3,但是不包括下标3
numbers2 :=numbers[:3]
//从下标3一直到结束
numbers3 :=numbers[3:]

切片的长度与容量

  • 内置的 len 和 cap 函数分别返回 slice 的长度和容量 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}) 存储于静态区中。同时会创建一个变量。

  • 核心逻辑位于 slicelit 函数
// go/src/cmd/compile/internal/gc/sinit.go
func slicelit(ctxt initContext, n *Node, var_ *Node, init *Nodes)

其抽象的过程如下:

var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice := 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 初始化

  • 例如make([]int,3,4)
  • 使用make 关键字,在 typecheck1 类型检查阶段,节点 Node 的 op 操作变为OMAKESLICE,并且左节点存储长度 3, 右节点存储容量 4
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
  • 下面来分析一下编译时内存的逃逸问题,如果 make 初始化了一个太大的切片,这个空间会逃逸到堆中,由运行时分配。如果一个空间比较小,会在栈中分配。
  • 此临界值值定义在/usr/local/go/src/cmd/compile/internal/gc,可以被 flag smallframes 更新,默认为 64KB。
  • 所以make([]int64,1023)make([]int64,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)
  • 核心逻辑位于go/src/cmd/compile/internal/gc/walk.gon.Esc代表变量是否逃逸
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]T
ss := arr[:l]
  • 如果发生了逃逸,运行时调用 makeslice64 或 makeslice 分配在堆中,当切片的长度和容量小于 int 类型的最大值,会调用 makeslice,反之调用 makeslice64 创建切片。
  • makeslice64 最终也是调用了 makeslice,比较简单,最后调用 mallocgc 申请的内存大小为类型大小 * 容量cap
// 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)
}

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

切片的扩容

  • Go 中切片 append 表示添加元素,但不是使用了 append 就需要扩容,如下代码不需要扩容
a:= make([]int,3,4)
append(a,1)
  • 当 Go 中切片 append 当容量超过了现有容量,才需要进行扩容,例如:

    a:= make([]int,3,3)
    append(a,1)
    
  • 核心逻辑位于go/src/runtime/slice.go 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 {

            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }

            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    ...
}
  • 上面的代码显示了扩容的核心逻辑,Go 中切片扩容的策略是这样的:

    • 首先判断,如果新申请容量(cap)大于 2 倍的旧容量(old.cap),最终容量(newcap)就是新申请的容量(cap)
    • 否则判断,如果旧切片的长度小于 1024,则最终容量 (newcap) 就是旧容量 (old.cap) 的两倍,即(newcap=doublecap)
    • 否则判断,如果旧切片长度大于等于 1024,则最终容量(newcap)从旧容量(old.cap)开始循环增加原来的 1/4,即(newcap=old.cap,for {newcap += newcap/4})直到最终容量(newcap)大于等于新申请的容量 (cap),即(newcap >= cap)
    • 如果最终容量(cap)计算值溢出,则最终容量(cap)就是新申请容量(cap)
  • 接着根据切片类型的大小,确定不同的内存分配大小。其主要是用作内存的对齐。因此,申请的内存可能会大于实际的et.size * newcap

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

  • 最后核心是申请内存。要注意的是,新的切片不一定意味着新的地址。
  • 根据切片类型et.ptrdata是否为指针,需要执行不同的逻辑。
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}
  • 当切片类型不是指针,分配内存后只需要将内存的后面的值清空,memmove(p, old.array, lenmem) 函数用于将 old 切片的值赋值给新的切片
  • 整个过程的抽象抽象表示如下
old = make([]int,3,3)
new = append(old,1) => new = malloc(newcap * sizeof(int))   a[4]  = 0
new[1] = old[1]
new[2] = old[2]
new[3] = old[3]
  • 当切片类型为指针,指针需要写入当前协程缓冲区中,这个地方涉及到 GC 回收机制中的写屏障,后面介绍。

切片的截取

  • 对于数组下标的截取,如下所示,可以从多个维度证明,切片的截取生成了一个新的切片,但是底层数据源却是使用的同一个。
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](../image/golang[10.2

在 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 个字节后的位置

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

切片的复制

  • 由于切片的复制不会改变指向的底层数据源。但是我们有些时候希望建一个新的数组,连底层数据源也是全新的。这个时候可以使用copy函数
  • 切片进行值拷贝:copy
// 创建目标切片
numbers1 := make([]int, len(numbers), cap(numbers)*2)
// 将numbers的元素拷贝到numbers1中
count := copy(numbers1, numbers)
  • 切片转数组
slice := []byte("abcdefgh")
var arr [4]byte
copy(arr[:], slice[:4])
//或者直接如下,这涉及到一个特性,即只会拷贝min(len(arr),len(slice)
copy(arr[:], slice)
  • copy 函数在编译时会决定使用哪一种方式,普通的方式会直接调用memmove
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))) }
}
  • 除非是协程调用的方式go copy(numbers1, numbers) 或者(加入了 race 等检测 && 不是在编译 go 运行时代码) 会转而调用运行时 slicestringcopy 或 slicecopy .
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)

  • slicestringcopy 或 slicecopy 本质上仍然是调用了memmove只是进行了额外的 race 冲突等判断。
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
}

总结

  • 切片是 go 语言中重要的数据结果,其和其他语言不同的是,其维护了底层的内存,以及长度和容量
  • 切片与数组的赋值拷贝有明显区别,切片在赋值拷贝与下标截断时引用了相同的底层数据
  • 如果要完全复制切片,使用copy函数。其逻辑是新建一个新的内存,并拷贝过去。在极端情况需要考虑其对性能的影响
  • 切片字面量的初始化,数组存储于静态区。 切片make的初始化方式时,如果 make 初始化了一个大于 64KB 的切片,这个空间会逃逸到堆中,在运行时调用makeslice创建。小于 64KB 的切片在栈中初始化
  • Go 中切片 append 当容量超过了现有容量,需要进行扩容,其策略是:
    • 首先判断,如果新申请容量(cap)大于 2 倍的旧容量(old.cap),最终容量(newcap)就是新申请的容量(cap)
    • 否则判断,如果旧切片的长度小于 1024,则最终容量 (newcap) 就是旧容量 (old.cap) 的两倍,即(newcap=doublecap)
    • 否则判断,如果旧切片长度大于等于 1024,则最终容量(newcap)从旧容量(old.cap)开始循环增加原来的 1/4,即(newcap=old.cap,for {newcap += newcap/4})直到最终容量(newcap)大于等于新申请的容量 (cap),即(newcap >= cap)
    • 如果最终容量(cap)计算值溢出,则最终容量(cap)就是新申请容量(cap)
  • Go 中切片 append 后返回的切片地址并不一定是原来的、也不一定是新的内存地址,因此必须小心其可能遇到的陷阱。一般会使用a = append(a,T)的方式保证安全。

前文

参考资料

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

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

欢迎加微信:ywj2271840211

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
EasyHacking GoCN 每日新闻 (2020-04-21) 中提及了此贴 04月21日 10:08
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册