jasper的技术小窝

关注DevOps、运维监控、Python、Golang、开源、大数据、web开发、互联网

深入Golang之slice

作者:jasper | 分类:Golang | 标签:   | 阅读 216 次 | 发布:2017-09-09 11:47 p.m.

虽然现在网上已经有了很多对Golang的深入的分析什么的,但是为了加深自己的理解,我还是打算自己看看源码,研究一下Golang的一些内部实现,并记录下来。首先就从slice这个类型开始吧。

slice的初始化

Golang中的slice的数据结构如下:

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

第一个字段array是指向指针,其指向一个底层数组,len表示slice中元素的个数,cap是slice的容量,具体就是允许slice中元素增长的最大个数。

例如x := []int{1,2,4,7,9},对于x这个slice的结构是这样的:

slice的创建过程如下:

func makeslice(et *_type, len, cap int) slice {
   // 根据类型获取最长的长度,len和cap都必须小于这个值 
    maxElements := maxSliceCap(et.size)
    if len < 0 || uintptr(len) > maxElements {
        panic(errorString("makeslice: len out of range"))
    }

    // 其中len必须小于等于cap
    if cap < len || uintptr(cap) > maxElements {
        panic(errorString("makeslice: cap out of range"))
    }

    // 申请内存
    p := mallocgc(et.size*uintptr(cap), et, true)

    // 返回一个slice
    return slice{p, len, cap}
}

slice的切割

下面我们来看看对slice做一个切割,例如:y := x[1:3],其过程可以描述为:

slice并不是复制一份数据,而是新建了一个slice的数据结构来存放数组的指针和长度和容量。并且其指针指向数组里面的第二个元素,长度由[1:3]决定,所以为2,而容量是数组允许的最大容量为4,在这个例子中,y[0]和y[1]是有效的,但是分割y[0:4]也是有效的:

func main()  {
    x := []int{1,2,4,7,9}
    y := x[1:3]

    fmt.Println(x)
    fmt.Println(y)

    x[1] = 99
    y[1] = 100

    fmt.Println(x)
    fmt.Println(y)

    fmt.Println(y[0:4])
}

运行结果:

[1 2 4 7 9]
[2 4]
[1 99 100 7 9]
[99 100]
[99 100 7 9]

slice的切割并不需要分配内存,这样的实现可以让slice的操作非常轻量级。

slice的扩容

在对slice执行append的时候,可能是使slice自动扩容,具体的代码实现为:

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 newcap < cap {
                newcap += newcap / 4
            }
        }
    }

    // 省略部分代码
    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        p = mallocgc(capmem, nil, false)
        memmove(p, old.array, lenmem)
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        p = mallocgc(capmem, et, true)
        if !writeBarrier.enabled {
            memmove(p, old.array, lenmem)
        } else {
            for i := uintptr(0); i < lenmem; i += et.size {
                typedmemmove(et, add(p, i), add(old.array, i))
            }
        }
    }

    return slice{p, old.len, newcap}
}

slice的扩容规则是:如果新的大小是当前大小的2倍以上,则增长为新的大小;否则,如果当前大小小于1024,则新的大小为当前的2倍,不然就按每次按当前大小的1/4增长,直到新的大小大于等于新大小。

slice在append的时候如果有额外的容量可用,append将可用的元素合并到切片的长度,然后对他进行赋值,如果没有可用的容量,append会创建新的底层数组,将现有的值复制到新的数组里再追加新的值。

简单看个例子:

func main()  {
    x := []int{1,2,4,7,9}
    fmt.Println(cap(x))
    fmt.Println(unsafe.Pointer(&x[0]))

    x = append(x, 10)
    fmt.Println(cap(x))
    fmt.Println(unsafe.Pointer(&x[0]))

    x = append(x, 20)
    fmt.Println(cap(x))
    fmt.Println(unsafe.Pointer(&x[0]))
}

结果:

5
0xc420014180
10
0xc420018190
10
0xc420018190

ok,可以看到,第一次append的时候cap扩大了一倍,而且指针地址也变化了(因为产生了新的底层数组),而第二次append的时候,cap没有变化,地址也没有变化。

再来看些例子

下面这段程序的输出,你认为是什么:

func main(){
    s := []int{5}
    s = append(s, 7)
    s = append(s, 9)
    x := append(s, 11)
    y := append(s, 12)
   fmt.Println(s, x, y)
}

结果是:

[5 7 9] [5 7 9 12] [5 7 9 12]

OK,那我们再来看这样呢:

func main(){
    s := []int{5, 7, 9}
    x := append(s, 11)
    y := append(s, 12)
    fmt.Println(s,x,y)
}

结果就正常了:

[5 7 9] [5 7 9 11] [5 7 9 12]

解释:

先来看看第一个例子:

  1. 创建s时,cap(s) == 1,内存中数据[5]
  2. append(s, 7) 时,按slice扩容机制,cap(s)翻倍 == 2,内存中数据[5,7]
  3. append(s, 9) 时,按slice扩容机制,cap(s)再翻倍 == 4,内存中数据[5,7,9],但是实际内存块容量4
  4. x := append(s, 11) 时,容量足够不需要扩容,内存中数据[5,7,9,11]
  5. y := append(s, 12) 时,容量足够不需要扩容,内存中数据[5,7,9,12]

所以后一次的操作会覆盖前一次的,因为s,x,y其指向的是同一个底层数组。

再来看看第二个例子:

  1. 创建s时,cap(s) == 3,内存中数据[5,7,9]
  2. x := append(s, 11)时,按照slice扩容机制,cap(s)翻倍 == 6,内存数据为[5,7,9,11],此时x指向一个新的数组;
  3. y := append(s, 12)时,同样按照slice扩容机制,cap(s)翻倍 == 6,内存数据为[5,7,9,12],此时y指向一个新的数组;

所以这里的s,x,y指向的底层数组是不一样的,得到的结果也就没有覆盖的关系。

一般在golang中要求在slice的append过后的结果需要assign回原来的slice变量,不建议append赋值给其他变量,这样可能会遇到意想不到的问题。这和其他的语言是不太一样的,一般的设计是append是slice对象的一个方法,这样更能直观表达,但是在golang中这样的表达却又不符合底层实现了。

写在最后

对于slice的运用和原理,大体就是这么些,需要再次强调的是,由于slice的底层结构的原因,在对slice在函数之间传递时,其实底层的数组是不变的,所以有些文档会说slice为引用类型,然而我并不这么任何,slice只是展示出了和引用类型部分同样的效果,看这个例子你就应该清楚:

func main()  {
    x := []int{1,2,4,7,9}
    fmt.Println(x)
    change(x)
    fmt.Println(x)
}

func change(c []int)  {
    c[0]=100
    c = append(c, 10)
}

结果为:

[1 2 4 7 9]
[100 2 4 7 9]

另外,在将slice赋值给其他变量时候,请要copy,这样让底层的数组也是不同的地址,不然会增加祸患!


转载请注明出处:http://www.opscoder.info/goalng_slice.html

【上一篇】 做一个会提问的程序猿
【下一篇】 深入Golang之map
其他分类: