@注:以下内容来自《Go语言底层原理剖析》、《Go语言设计与实现》书中的摘要信息,本人使用版本(Go1.19)与书中不一致,源码路径可能会有出入。

1.介绍

切片是Go语言中常用的数据类型之一,使用方式和数组一样,但是其长度不固定,我们可以向切片中追加元素,它会在容量不足时自动扩容。

1.1 声明

Go语言中,切片类型的声明方式和数组类似,不过由于切片的长度是动态的,所以声明时只需要指定切片中的元素类型。

1
2
[]int
[]interface{}

从切片的定义,我们可以推测出,切片在编译期间生成的类型只会包含切片中的元素类型,即intinterface{}等,cmd/compile/internal/types.NewSlice就是编译期间用于创建切片类型的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func NewSlice(elem *Type) *Type {
if t := elem.cache.slice; t != nil {
if t.Elem() != elem {
base.Fatalf("elem mismatch")
}
if elem.HasTParam() != t.HasTParam() || elem.HasShape() != t.HasShape() {
base.Fatalf("Incorrect HasTParam/HasShape flag for cached slice type")
}
return t
}

t := newType(TSLICE)
t.extra = Slice{Elem: elem}
elem.cache.slice = t
if elem.HasTParam() {
t.SetHasTParam(true)
}
if elem.HasShape() {
t.SetHasShape(true)
}
return t
}

上述方法返回结构体中的Extra字段是一个只包含切片内元素类型的结构,也就是说切片内元素的类型是在编译期间确定的,编译器确定了类型之后,会将类型存储在Extra字段中帮助程序在运行时动态获取。

2.数据结构

编译期间的切片cmd/compile/internal/types.Slice类型,但是在运行时切片会转换成reflect.SliceHeader结构体,如下:

1
2
3
4
5
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
  • Data:指向数组的指针
  • Len:当前切片的长度
  • Cap:当前切片的容量,即Data数组的大小

2.1 存储原理

Data是一片连续的内存空间,这片内存空间可以用于存储切片中的全部元素,数组中的元素只是逻辑上的概念,底层存储其实都是连续的,所以我们可以将切片理解成一片连续的内存空间加上长度和容量的标识,如下图所示:
golang-slice-struct

从上图中,我们会发现,切片和数组的关系非常密切,切片引入了一个抽象层,提供了对数组中部分连续片段的引用,而作为数组的引用,我们在运行期间可以修改其长度的范围,当切片底层的数组长度不足时就会触发扩容,切片指向的数组可能会发生变化,不过在上层来看切片是没有变化的,上层只需要和切片打交道,不需要关心数组的变化。

3.初始化

Go语言包含三种初始化切片的方式:

  • 通过下标的方式获取数组或者切片的一部分
  • 使用字面量初始化新的切片
  • 使用关键字make创建切片

3.1 使用下标

使用下标创建切片是最原始也是最接近汇编语言的方式,它是所有方法中最为底层的一种,编译器会将arr[0:3]slice[0:3]等语句转换成OpSliceMake操作,我们可以通过下面的代码进行验证:

1
2
3
4
5
6
7
8
9
10
11
import "fmt"

func main() {
arr := [3]int{1, 2, 3}
slice := arr[0:1]
fmt.Println(slice)
}
/** 生成SSA
➜ GOSSAFUNC=main go tool compile main.go
dumped SSA to /Users/shershon/ProjectItem/GoItem/test/ssa.html
*/

通过GOSSAFUNC变量编译上述代码可以得到一系列SSA中间代码,其中slice := arr[0:1]语句在decompose builtin阶段对应的代码如下图所示:

SliceMake操作会接收四个参数来创建新的切片:元素类型、数组指针、切片大小和容量,这也是我们在数据结构一节中提到的切片的几个字段,需要注意的是使用下标初始化不会拷贝原数组或者原切片中的数据,它只会创建一个指向原数组或者原切片的切片结构体,所以修改新切片的数据也会修改原数组或者原切片。

1
2
3
4
5
6
7
8
9
10
11
12
13
func TestRun(t *testing.T) {
oldArr := [5]int{1, 2, 3, 4, 5}
// 使用下标创建切片
newSlice := oldArr[0:3]
fmt.Println("修改切片前,oldArr:", oldArr, " newSlice:", newSlice)
// 修改新切片值
newSlice[0] = 100
fmt.Println("修改切片后,oldArr:", oldArr, " newSlice:", newSlice)
}
/** 输出
修改切片前,oldArr: [1 2 3 4 5] newSlice: [1 2 3]
修改切片后,oldArr: [100 2 3 4 5] newSlice: [100 2 3]
*/

3.2 使用字面量

当我们使用字面量[]int{1,2,3}创建新切片时,cmd/compile/internal/gc.slicelit函数会在编译期间将它展开成如下所示的代码片段:

1
2
3
4
5
6
7
var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice := vauto[:]

对上述代码的分析:

  1. 根据切片中的元素数量对底层数组的大小进行推断并创建一个数组
  2. 将这些字面量元素存储到初始化的数组中
  3. 创建一个同样指向[3]int类型的数组指针
  4. 将静态存储区的数组vstat赋值给指针所在的地址
  5. 通过[:]操作获取一个底层使用vstat的切片

第5步中的[:]就是使用下标创建切片的方法,从这一点我们也可以看出[:]操作时创建切片的最底层的方法。

3.3 使用make

如果使用字面量的方式创建切片,大部分的工作都是在编译期完成。但是我们使用make关键字创建切片时,很多工作都需要运行时的参与;调用方必须向make函数传入切片的大小以及可选的容量。

类型检查期间的cmd/compile/internal/gc.typecheck1函数会校验入参:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func typecheck1(n *Node, top int) (res *Node) {
switch n.Op {
...
case OMAKE:
args := n.List.Slice()

i := 1
switch t.Etype {
// 类型是切片
case TSLICE:
if i >= len(args) {
yyerror("missing len argument to make(%v)", t)
return n
}

l = args[i]
i++
var r *Node
if i < len(args) {
r = args[i]
}
...
// 切片大小len,不能超过容量cap
if Isconst(l, CTINT) && r != nil && Isconst(r, CTINT) && l.Val().U.(*Mpint).Cmp(r.Val().U.(*Mpint)) > 0 {
yyerror("len larger than cap in make(%v)", t)
return n
}

n.Left = l
n.Right = r
n.Op = OMAKESLICE
}
...
}
}

上述函数不仅会检查len是否传入,还会保证传入的容量cap一定大于或等于len。除了校验参数,当前函数会将OMAKE节点转换成OMAKESLICE,中间代码生成的cmd/compile/internal/gc.walkexpr函数会依据下面两个条件转换成OMAKESLICE类型的节点。

  1. 切片的大小和容量是否足够小
  2. 切片是否发生了逃逸,最终在堆上初始化

当切片发生逃逸或者非常大时,运行时需要runtime.makeslice在堆上初始化切片,如果当前的切片不会发生逃逸并且切片非常小的时候,那么切片运行时最终会被分配在栈区。

此临界值定义在cmd/compile/internal/ir.MaxImplicitStackVarSize变量中,默认为64KB,可以通过指定编译时smallframes标识进行更新,因此,make([]int64,1023)make([]int64,1024)实现的细节是截然不同的。

4.扩容原理

4.1 扩容触发

关键字append是触发扩容的主要方式,但不是每次使用append函数就一定会扩容,看下面的代码实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
// --------- 不会扩容 ---------
// 定义切片a,容量为4
a := make([]int, 3, 4)
fmt.Printf("append前,a-> len:%v cap:%v value:%v \n", len(a), cap(a), a)
a = append(a, 1)
fmt.Printf("append后,a-> len:%v cap:%v value:%v \n", len(a), cap(a), a)

// --------- 会扩容 ---------
// 定义切片a,容量为4
b := make([]int, 3, 3)
fmt.Printf("append前,b-> len:%v cap:%v value:%v \n", len(b), cap(b), b)
b = append(b, 1)
fmt.Printf("append后,b-> len:%v cap:%v value:%v \n", len(b), cap(b), b)
}

/** 输出
append前,a-> len:3 cap:4 value:[0 0 0]
append后,a-> len:4 cap:4 value:[0 0 0 1]
append前,b-> len:3 cap:3 value:[0 0 0]
append后,b-> len:4 cap:6 value:[0 0 0 1]
*/

代码分析:

  • 切片a容量为4,目前长度为3(初始化3个0),所以还能在容纳1个元素,在执行append时,不会进行扩容,所以cap还是4
  • 切片b容量为3,目前长度也是3(初始化3个0),如果再append,切片容量会不足,便会进行扩容。所以cap为6,至于为什么是6,看后续源码分析

4.2 容量判定

当切片的容量不足时,append函数在运行时会调用runtime.growslice函数为切片扩容。

扩容是为切片分配新的内存空间,并拷贝原切片中的元素到新空间的过程。

runtime.growslice的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func growslice(et *_type, old slice, cap int) slice {
...
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
// 如果新申请的容量cap大于旧容量old.cap的2倍,则最终的容量newcap是新申请的容量cap
newcap = cap
} else {
if old.cap < 1024 {
// 如果旧切片的容量小于1024,则最终的容量是旧容量的2倍
newcap = doublecap
} else {
// 旧容量开始循环增加原来的1/4,到最终容量大于或等于新申请的容量为止
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// 容量计算值溢出,则最终的容量就是新申请的容量
if newcap <= 0 {
newcap = cap
}
}
}
...
}

上述代码显示了扩容的核心逻辑,Go语言中切片扩容的策略整理如下:

  • 如果新申请容量(cap)大于2倍的旧容量(old.cap),则最终容量(newcap)是新申请的容量(cap
  • 如果旧切片的容量小于1024,则最终容量是旧容量的2倍,即newcap=doublecap
  • 如果旧切片长度大于或等于1024,则最终容量从旧容量开始循环增加原来的1/4,直到最终容量大于或等于新申请的容量为止,即newcap ≥ cap
  • 如果最终容量计算值溢出,即超过了int的最大范围,则最终容量就是新申请容量

growslice函数会根据切片的类型,分配不同大小的内存,为了内存对齐,申请的内存可能大于实际的类型大小 * 容量大小

5.切片复制

5.1 示例代码

先看一段代码,试着分析会输出什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func TestCopySlice(t *testing.T) {
// 定义切片
oldSli := []int{100, 200, 300}
// 复制切片
copySli := oldSli
fmt.Printf("修改前, oldSli:%v copySli:%v \n", oldSli, copySli)
// 修改复制后的切片
copySli[0] = 99
fmt.Printf("修改后, oldSli:%v copySli:%v \n", oldSli, copySli)
}
/** 输出
修改前, oldSli:[100 200 300] copySli:[100 200 300]
修改后, oldSli:[99 200 300] copySli:[99 200 300]
*/

切片的复制其实也是值复制,但是这里的值复制指对于运行时SliceHeader结构的复制,但是底层指针指向的是相同的底层数组,因此可以理解为数据进行了引用传递。

切片的这一特性使得即使切片中有大量数据,在复制时的成本也比较小。数组也是如此。

5.2 使用copy

复制的切片不会改变指向底层的数组,但有时我们希望创建一个新切片,并且与旧切片不共享底层的数组,这时可以使用copy函数。示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func TestCopySlice2(t *testing.T) {
// 定义切片
oldSli := []int{100, 200, 300}
// 使用copy复制切片
copySli := make([]int, len(oldSli), cap(oldSli))
copy(copySli, oldSli)
fmt.Printf("修改前, oldSli:%v copySli:%v \n", oldSli, copySli)
// 修改复制后的切片
copySli[0] = 99
fmt.Printf("修改后, oldSli:%v copySli:%v \n", oldSli, copySli)
}
/** 输出
修改前, oldSli:[100 200 300] copySli:[100 200 300]
修改后, oldSli:[100 200 300] copySli:[99 200 300]
*/

copy函数在运行时主要调用了memmove函数,用于实现内存的复制。如果采用协程调用的方式go copy(numbers1, numbers)后者加入了race检测,则会调用运行时runtime.slicecopy函数,无论是编译期间拷贝还是运行时拷贝,两种拷贝方式都会通过runtime.memmove将整块内存的内容拷贝到目标的内存区域中