slice——切片

切片是什么?

​ 切片是底层能够自动扩容的动态数组。

那么slice所在的runtime的结构是什么样的呢？

//go1.13.4:runtime/slice.go
type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

slice的底层实现是由一根指针和其指针指向的数据大小以及申请的容器组成。

所以使用make创建的slice在实际中是如何被创建的呢？

在使用make来为slice分配内存的过程中，事实上会对该代码编译成一个函数调用，如下：

byteSlice := make([]byte,0,64)
//对应的函数调用如下
//go1.13.4:runtime/slice.go
1 func makeslice(et *_type, len, cap int) unsafe.Pointer {
2    mem, overflow := math.MulUintptr(et.size, uintptr(cap))
3    if overflow || mem > maxAlloc || len < 0 || len > cap {
4        mem, overflow := math.MulUintptr(et.size, uintptr(len))
5        if overflow || mem > maxAlloc || len < 0 {
6            panicmakeslicelen()
7        }
8        panicmakeslicecap()
9    }
10
11   return mallocgc(mem, et, true)
}

1. 第1行中是将参数et包含的数据为byte结构的一些信息，比如byte的容量，对齐方式等信息。而len这对应make的len的值，cap这对应make中slice的值。

2. 第2行则是为了确定需要分配的内存，et.size可以获取到byte的容量大小，其中math.MulUintptr函数是将et.size和cap进行相乘，并检查是否溢出，如果溢出这会执行第二行if中的语句，并panic。

3. 第11行是给byteSlice分配内存并赋值给byteSlice底层实现的array。

那么在slice是如何进行扩容的呢？

slice的底层扩容代码如下：

sliByte := make([]byte,0)
sliByte = append(sliByte, 'a')
//所对应的slice函数调用如下:
func makeslice(et *_type, len, cap int) unsafe.Pointer
func growslice(et *_type, old slice, cap int) slice

• makeslice函数对应的是对sliByte进行创建。
• growslice函数对应的是对sliByte进行扩容。

下面来看下slice是如何进行扩容的，由于代码量较多。直接在代码中进行分析：

//go1.13.4:runtime/slice.go
//et:对应slice切片类型的一些数据，包含类型的容量，对齐方式等信息
//old：对应之前创建的slice中的一些数据包含：指向数据的指针，长度，容量（注：对于make(type,0)这个操作实际上是不会调用makeslice这个函数的，因为makeslice这个函数主要是为了对切片分配内存，而make(type,0)实际上没有对切片分配内存）
//cap指的是最小的新容量大小
func growslice(et *_type, old slice, cap int) slice {
    if raceenabled {    //当编译包含-race则会启动该代码，检测数据竞争问题
        callerpc := getcallerpc()
        racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
    }
    if msanenabled {        //当编译包含-msan则会启动改代码，用于检测数据初始化问题
        msanread(old.array, uintptr(old.len*int(et.size)))
    }

    if cap < old.cap {      //确保新的容量不小于旧的容量
        panic(errorString("growslice: cap out of range"))
    }

    if et.size == 0 {       //slice的内部的数据类型为空类型，则返回一个{nil的数组，原有长度，新的容量}
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }
    //首先对旧的容量默认以2倍进行扩容
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {    //确保新扩容的容量要大于当前最小的容量
        newcap = cap
    } else {
        if old.len < 1024 { //如果旧的<1024个，则直接翻倍扩容
            newcap = doublecap
        } else {    //如果旧的容量>=1024个
            for 0 < newcap && newcap < cap {    //每次以1.25倍的方式进行扩容，直到能满足最小容量 
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    //以下是为了检测扩容长度是否超过最大分配的内存以及对扩容的内存的对齐等操作
    switch {
    case et.size == 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))   //该函数会对cap的容量大小进行对齐
        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.ptrdata == 0 {
        p = mallocgc(capmem, nil, false)
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        p = mallocgc(capmem, et, true)
        if lenmem > 0 && writeBarrier.enabled {
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
        }
    }
    memmove(p, old.array, lenmem)   //将旧数据赋值给新的slice

    return slice{p, old.len, newcap}    //返回slice切片
}

总结

1. slice的底层实现实际上是有3个部分组成，一个是存储数据的指针，以及存储数据的长度，和存储数据的容量
2. 对于1024以下的元素的切片进行扩容默认是以2倍的方式进行扩容。但超过1024个元素后会以1.25倍的方式进行扩容，知道能保存新加数据的容量为止。
3. 切片的扩容实际是重新分配一块内存，然后将旧的数据迁移至新的内存中。所以当切片很大时，每次扩容将会消耗大量的CPU性能