Golang Slice 源码分析

slice是golang使用频率最高的结构之一，如果不知道它的实现原理，很容易出现”莫名其妙”的bug。

一、定义

slice是一个结构体, 定义如下

type slice struct {
    array unsafe.Pointer //数组首地址指针
    len   int //长度
    cap   int //容量
}

slice可以看成是对数组的封装，底层数据结构是数组。slice结构体成员的含义分别为：
array:指向数组首地址的指针
len:数组中的元数个数
cap:数组总长度（容量）

二、扩容

通过append追加数据时，如果当前len==cap就会启动扩容，Go对扩容处理方式为:

重新申请一段更大连续空间(创建一个新数组)
把老slice.array中的数据拷贝到新数组中
创建一个新slice,把array指向新数组的首地址,设置cap值为新数组大小(容量)
把需要通过append添加的元素值加入到新slice.array中，并设置新slice的len为当前元数个数

源码(go1.12.7)

//runtime/slice.go
//cap，append触发扩容时参数1的len+参数2的len
func growslice(et *_type, old slice, cap int) slice {
    if raceenabled {
        callerpc := getcallerpc()
        racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
    }
    if msanenabled {
        msanread(old.array, uintptr(old.len*int(et.size)))
    }
    //如果扩容后的容量 < 扩容前的容量直接panic
    if cap < old.cap {
        panic(errorString("growslice: cap out of range"))
    }
    //如果当前slice大小为0还调用了扩容，则直接返回一个新slice(array指向nil)
    if et.size == 0 {
        //append是不会创建一个指针为空但容量>0的slice, 这里假设在这种情况下append不需要保留old.array
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }
    //新容量计算
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap { //如果指定容量>2倍当前slice容量,则直接使用指定容量
        newcap = cap
    } else {
        if old.len < 1024 {//当slice元素个数<1024，则直接扩容2倍
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap { //元素个数>=1024，则扩容为1.25倍,但<cap
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    //计算对应的内存块大小（span）
    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    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 {
            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 overflow || capmem > maxAlloc {
        panic(errorString("growslice: cap out of range"))
    }
    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {//如果不是指针类型
        //分配一段新内存,不需要置0[详情参考](https://lifan.tech/2019/10/22/memory/golang-memory/#more)
        p = mallocgc(capmem, nil, false)
        //把除老数据长度以外的地址段置0，后面会通过memmove把老数据拷贝到低地址，所以这里不用置0
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        //如果元素是指针类型，申请一段新内存时需要置0，不然会被GC扫描，指针类型要考虑GC写屏障
        p = mallocgc(capmem, et, true)
        if writeBarrier.enabled {
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
        }
    }
    memmove(p, old.array, lenmem)//把slice中的数据拷贝到新申请内存的低地址
    return slice{p, old.len, newcap}//新创建slice并设置cap为newcap
}

三、删除数据

和添加数据一样，删除数据也用append, 因为slice底层数据结构是数组，在数组中，删除中间元素后会把后面的数据全部往前面移，如果数组中的数据量很大，删除的数据很靠前(下标很小)，这会非常低效。
golang timer 是一个基于数组的时间堆算法，堆可能是一个巨大的数组，但每次都是删除堆顶元素(数组下标为0)，如果用t = append(t[:0],[t[1:]...)删除，效率必然低下。timer源码是这样做的：详情参考
1.把要删除的元素用最后一个元素覆盖
2.缩小slice的len(len-1)

last := len(tb.t) - 1
if last > 0 {
    tb.t[0] = tb.t[last]
    tb.t[0].i = 0
}
tb.t[last] = nil
tb.t = tb.t[:last] //拷贝slice的array(指针), cap, len=缩小前的len-1

这种做法最后一个元素并没有被真正删除,只是len-1(通过指针方式是可以访问到)。因为slice对数据的访问是由len决定的，只有下标 < len 的数据才是有效的。但不用担心这个无效数据，下次append时，新数据会覆盖它。

四、常见问题

把slice作为参数或返回值

1
2
3

func foo(arr []int){
    arr = append(arr, 10)
}

情况1 len(arr) == cap(arr)：在函数中append元素时，会重新创建一个slice，并复制数据。参数slice变量的指针指向新数组，故对原slice无影响
情况2 len(arr) < cap(arr)：append元素时，不会生成新的slice，数据会被追加到原slice中，但是，永远读取不到。因为不管是通过下标访问，还是for range 都是只能访问到前len个元素。这时候,虽然原slice数据中的数据被append了一个元素，但len是值传递，所以原slice的len依然没变，故不能访问。但通过指针是可以取到该值的(不提倡这样做，例子只为证明推理)，同理slice作为返回值也一样。如下：

func callen(arr []int) int {
    arr = append(arr, 10)
    return len(arr)
}
func main() {
    arr1 := []int{1, 2, 3, 4, 5}
    arr1 = append(arr1, 100) //cap变为5*2
    callen(arr1)
    p7 := unsafe.Pointer(&arr1[5]) //unsafe.Pointer 相当于void*
    q := uintptr(p7) + 8 //uintptr 语言内置类型，其实就是typedef uint64 uintptr
    t := (*int)(unsafe.Pointer(q))
    fmt.Println(*t)  //输出10
    fmt.Println(arr1)//输出1，2，3，4，5，100
}

多个切片共享底层数组

func main(){
    a1 := []int{1,2,3,4,5}
    a2 := a1[0:3]
    a2[0] = -1
    fmt.Printf("%v, ptr:%p, len:%d, cap:%d \n", a1, unsafe.Pointer(&a1[0]), len(a1), cap(a1))
    fmt.Printf("%v, ptr:%p, len:%d, cap:%d \n", a2, unsafe.Pointer(&a2[0]), len(a2), cap(a2))
    //输出结果
    //[-1 2 3 4 5], ptr:0xc00000c2d0, len:5, cap:5 
    //[-1 2 3],     ptr:0xc00000c2d0, len:3, cap:5 
}

从上面的例子中可以看出a1,a2它们底层数组的首地址是相同的，说明a1.array和a2.array指向同一个数组，所以在修改a2元素值时，a1,a2都变化了。

在for range中修改slice

func main(){
    array := [][]int{{10, 20},{30, 40}}
    for _, v := range array{
        v = append(v, -1)
    }
    fmt.Printf("arry:%v\n", array)//arry:[[10 20] [30 40]]
}

我们期待在for range中对每个slice尾部添加元素-1，但从输出结果来看，并没有达到预期。问题出在什么地方呢？
可能存在2个问题：

for range在遍历对象时，会把它的值拷贝一份，在上面的例子中 v 其实是array元素的拷贝，对它append时，可能发生了扩容。所以-1并没有append到元slice中。
v为array元素的拷贝，那么无论v的len如何变化，都不会影响原来的slice。

可以修改为：

1
2
3

for k, _ := range array{
    array[k] = append(array[k], -1)
}

这样如果array[k] = append(array[k], -1)等号右边的append触发了扩容，array[k]值也是扩容后的slice。