Go Data Structure Source Code: slice

引言

Slice切片可以说是最常见的数据结构, 本文将结合源码对slice进行解读. 假设读者熟悉slice的基本操作;

数据结构

源码: go/src/runtime/slice.go, 结构体: slice;

type slice struct {
	array unsafe.Pointer // 指向底层数组的指针, 64位 8字节, 32位 4字节
	len   int // 切片中实际的元素数量, 64位 8字节, 32位 4字节
	cap   int // 切片的容量, 64位 8字节, 32位 4字节
}

Go中Slice是对Array的抽象与封装, 使得本不支持扩展的Array转换为了灵活Slice; Slice结构体本身只占有24字节或12字节.下面是slice初始化后的图示:

当执行make([]int, 2, 4)时，创建了一个元素类型为int的切片，其长度为2，容量为4。这意味着：

切片有两个int类型的元素，它们的初始值都是int类型的零值，即0。
切片有足够的底层数组空间来存储总共四个int类型的元素，这允许你在不重新分配内存的情况下扩展切片的长度到最多4个元素。

这段代码的执行结果是创建了一个包含两个整数（都初始化为0）的切片，并且这个切片有足够的预留空间来增长到包含四个整数。

操作流程

本部分将介绍在go/src/runtime/slice.go文件内部的函数逻辑, 均为Go内部实现, 用户无法直接调用;

初始化

函数签名:func makeslice(et *_type, len, cap int) unsafe.Pointer {...},
流程:
解读: 此API为Go语言内部实现的一部分, 用户不直接调用. 用户通常在Go中使用内置make函数,创建切片.
1. 首先计算切片的总字节大小;
2. 其次判定切片申请内存是否合法, 如果不合法则视情况返回length不合法, capaticity不合法的报错, 具体情况有:
  1. overflow：如果乘法结果溢出，表示计算的内存大小超出了uintptr类型能表示的范围。
  2. mem > maxAlloc：如果计算出的内存大小超过了允许的最大分配大小（maxAlloc）。
  3. len < 0：如果提供的长度是负数，这是非法的。
  4. len > cap：如果提供的长度大于容量，这也是非法的。
3. 最后, 会调用mallocgc申请内存, 并返回指针;

扩容

函数签名: func growslice(et *_type, old slice, cap int) slice {...}

此函数是处理runtime切片扩容的逻辑, 根据需要的容量, 扩展一个已有的函数. 它接受三个参数：元素类型的指针et，原始切片old，以及新的容量cap。返回值是一个新的切片，它包含了新的内存地址、原始切片的长度和新的容量;
流程:
解读:

上图中, 虚线部分表示忽略了部分非核心逻辑, 整体逻辑图中展示的比较清晰, 下面针对三个点, 着重说明下其操作细节:
- 元素大小为0时, 会直接返回一个指向zerobase地址的新切片, 例如struct{}元素.
- **计算新的容量newcap**。如果新的容量大于原始容量的两倍，则直接使用新的容量；否则，根据一定的规则（例如，如果原始容量小于1024，则加倍；如果大于1024，则每次增加原始容量的1/4，直到超过所需容量或者溢出）来增加容量。
- 根据元素类型的大小，特化内存分配的计算。例如，如果元素大小为1，则不需要乘除运算；如果元素大小为指针大小，则编译器会优化乘除运算为位移操作；如果元素大小是2的幂，则使用变量位移。

拷贝

函数签名: func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int { ... }

Go语言运行时(runtime)中处理切片复制操作的一个函数。slicecopy函数用于将一个切片的内容复制到另一个切片中。

它接受五个参数：目标切片的指针toPtr，目标切片的长度toLen，源切片的指针fromPtr，源切片的长度fromLen，以及每个元素的大小width。返回值是实际复制的元素数量。
流程:
解读:
- 源或者目的Slice长度为0时, 不会进行复制操作;
- 元素struct{}大小为0字节时, 不会进行内存复制操作, 直接视为复制成功;
- 总复制Size为1个字节时, 直接采用了赋值操作*(*byte)(toPtr) = *(*byte)(fromPtr)替代内存复制操作, 这样是高效的;
  
  这里需要注意何时总复制Size == 1 Byte呢, 这是一种特殊的情况, 目前只有三种场景:
  - 1个bool
  - 1个byte(uint8)
  - 1个int8