关于go:Go切片Silce底层实现和扩容

Go 切片 Silce 底层实现和扩容

一 切片的数据结构

切片（slice）是对数组一个间断片段的援用，所以切片是一个援用类型（因而更相似于 C/C++ 中的数组类型，或者 Python 中的 list 类型）。这个片段能够是整个数组，或者是由起始和终止索引标识的一些项的子集。须要留神的是，终止索引标识的项不包含在切片内。切片提供了一个与指向数组的动静窗口。
给定项的切片索引可能比相干数组的雷同元素的索引小。和数组不同的是，切片的长度能够在运行时批改，最小为 0 最大为相干数组的长度：切片是一个长度可变的数组。
Slice 的数据结构定义如下:

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

复制代码

切片的构造体由 3 局部形成，Pointer 是指向一个数组的指针，len 代表以后切片的长度，cap 是以后切片的容量。cap 总是大于等于 len 的。

二 创立切片

make 函数容许在运行期动静指定数组长度，绕开了数组类型必须应用编译期常量的限度。
创立切片有两种模式，make 创立切片，空切片。
make 和切片字面量

func makeslice(et *_type, len, cap int) slice {
    // 依据切片的数据类型，获取切片的最大容量
    maxElements := maxSliceCap(et.size)
    // 比拟切片的长度，长度值域应该在 [0,maxElements] 之间
    if len < 0 || uintptr(len) > maxElements {panic(errorString("makeslice: len out of range"))
    }
    // 比拟切片的容量，容量值域应该在 [len,maxElements] 之间
    if cap < len || uintptr(cap) > maxElements {panic(errorString("makeslice: cap out of range"))
    }
    // 依据切片的容量申请内存
    p := mallocgc(et.size*uintptr(cap), et, true)
    // 返回申请好内存的切片的首地址
    return slice{p, len, cap}
}

复制代码
还有一个 int64 的版本：

func makeslice64(et *_type, len64, cap64 int64) slice {len := int(len64)
    if int64(len) != len64 {panic(errorString("makeslice: len out of range"))
    }

    cap := int(cap64)
    if int64(cap) != cap64 {panic(errorString("makeslice: cap out of range"))
    }

    return makeslice(et, len, cap)
}

复制代码
实现原理和下面的是一样的，只不过多了把 int64 转换成 int 这一步罢了。

上图是用 make 函数创立的一个 len = 4，cap = 6 的切片。内存空间申请了 6 个 int 类型的内存大小。因为 len = 4，所以前面 2 个临时拜访不到，然而容量还是在的。这时候数组外面每个变量都是 0。

nil 和空切片
nil 切片和空切片也是罕用的。var slice []int

复制代码

nil 切片被用在很多规范库和内置函数中，形容一个不存在的切片的时候，就须要用到 nil 切片。比方函数在产生异样的时候，返回的切片就是 nil 切片。nil 切片的指针指向 nil。
空切片个别会用来示意一个空的汇合。比方数据库查问，一条后果也没有查到，那么就能够返回一个空切片。

 silce := make([]int , 0 )
 slice := []int{}

复制代码
空切片和 nil 切片的区别在于，空切片指向的地址不是 nil，指向的是一个内存地址，然而它没有调配任何内存空间，即底层元素蕴含 0 个元素。
最初须要阐明的一点是。不论是应用 nil 切片还是空切片，对其调用内置函数 append，len 和 cap 的成果都是一样的。

三 切片扩容

当一个切片的容量满了，就须要扩容了。怎么扩，策略是什么？

func growslice(et *_type, old slice, cap int) slice {
    if raceenabled {callerpc := getcallerpc(unsafe.Pointer(&et))
        racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
    }
    if msanenabled {msanread(old.array, uintptr(old.len*int(et.size)))
    }

    if et.size == 0 {
        // 如果新要扩容的容量比原来的容量还要小，这代表要缩容了，那么能够间接报 panic 了。if cap < old.cap {panic(errorString("growslice: cap out of range"))
        }

        // 如果以后切片的大小为 0，还调用了扩容办法，那么就新生成一个新的容量的切片返回。return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }

  // 这里就是扩容的策略
    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 lenmem, newlenmem, capmem uintptr
    const ptrSize = unsafe.Sizeof((*byte)(nil))
    switch et.size {
    case 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        newcap = int(capmem)
    case ptrSize:
        lenmem = uintptr(old.len) * ptrSize
        newlenmem = uintptr(cap) * ptrSize
        capmem = roundupsize(uintptr(newcap) * ptrSize)
        newcap = int(capmem / ptrSize)
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem = roundupsize(uintptr(newcap) * et.size)
        newcap = int(capmem / et.size)
    }

    // 判断非法的值，保障容量是在减少，并且容量不超过最大容量
    if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {panic(errorString("growslice: cap out of range"))
    }

    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        // 在老的切片前面持续裁减容量
        p = mallocgc(capmem, nil, false)
        // 将 lenmem 这个多个 bytes 从 old.array 地址 拷贝到 p 的地址处
        memmove(p, old.array, lenmem)
        // 先将 P 地址加上新的容量失去新切片容量的地址，而后将新切片容量地址前面的 capmem-newlenmem 个 bytes 这块内存初始化。为之后持续 append() 操作腾出空间。memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        // 从新申请新的数组给新切片
        // 从新申请 capmen 这个大的内存地址，并且初始化为 0 值
        p = mallocgc(capmem, et, true)
        if !writeBarrier.enabled {
            // 如果还不能关上写锁，那么只能把 lenmem 大小的 bytes 字节从 old.array 拷贝到 p 的地址处
            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}
}

复制代码
上述就是扩容的实现。次要须要关注的有两点，一个是扩容时候的策略，还有一个就是扩容是生成全新的内存地址还是在原来的地址后追加。
扩容策略

func main() {slice := []int{10, 20, 30, 40}
    newSlice := append(slice, 50)
    fmt.Printf("Before slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, &slice, len(slice), cap(slice))
    fmt.Printf("Before newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, &newSlice, len(newSlice), cap(newSlice))
    newSlice[1] += 10
    fmt.Printf("After slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, &slice, len(slice), cap(slice))
    fmt.Printf("After newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, &newSlice, len(newSlice), cap(newSlice))
}

复制代码
输入后果：

 Before slice = [10 20 30 40], Pointer = 0xc4200b0140, len = 4, cap = 4
 Before newSlice = [10 20 30 40 50], Pointer = 0xc4200b0180, len = 5, cap = 8
 After slice = [10 20 30 40], Pointer = 0xc4200b0140, len = 4, cap = 4
 After newSlice = [10 30 30 40 50], Pointer = 0xc4200b0180, len = 5, cap = 8

复制代码

从图上咱们能够很容易的看出，新的切片和之前的切片曾经不同了，因为新的切片更改了一个值，并没有影响到原来的数组，新切片指向的数组是一个全新的数组。并且 cap 容量也产生了变动。这之间到底产生了什么呢？
Go 中切片扩容的策略是这样的：
如果切片的容量小于 1024 个元素，于是扩容的时候就翻倍减少容量。下面那个例子也验证了这一状况，总容量从原来的 4 个翻倍到当初的 8 个。
一旦元素个数超过 1024 个元素，那么增长因子就变成 1.25，即每次减少原来容量的四分之一。
留神：扩容扩充的容量都是针对原来的容量而言的，而不是针对原来数组的长度而言的。