青梅梦呓

和世界交手的这许多年,你是否光彩依旧,兴致盎然

0%

理解Go语言数组和切片

数组和切片是Go语言中常见的数据结构,很多刚刚使用Go的开发者往往会混淆这两个概念,数组作为最常见的集合在编程语言中是非常重要的,除了数组之外,Go 语言引入了另一个概念 — 切片,切片与数组有一些类似,但是它们的不同之处导致使用上会产生巨大的差别。我个人对于算法专项使用Go语言来进行练习,因此只涉及Go语言的部分实现和原理。

数组

数组的概念

数组是由相同类型元素的集合组成的数据结构,计算机会为数组分配一块连续的内存来保存其中的元素,我们可以利用数组中元素的索引快速访问元素对应的存储地址,常见的数组大多都是一维的线性数组,而多维数组在数值和图形计算领域却有比较常见的应用1。

多维数组

数组作为一种基本的数据类型,通常都会从两个维度描述数组,首先需要描述数组中存储的元素类型,还需要描述数组最大能够存储的元素个数,在 Go 语言中我们往往会使用如下所示的方式来表示数组类型:

1
2
[10]string
[200]interface{}

与很多语言不同,Go 语言中数组在初始化之后大小就无法改变,存储元素类型相同、但是大小不同的数组类型在 Go 语言看来也是完全不同的,只有两个条件都相同才是同一个类型。

查看Go语言的源代码,在$GOROOT/src/cmd/compile/internal/types/type.go文件中可以看到新建一个数组的时候发生了什么事情:

1
2
3
4
5
6
7
8
9
10
// NewArray returns a new fixed-length array Type.
func NewArray(elem *Type, bound int64) *Type {
if bound < 0 {
Fatalf("NewArray: invalid bound %v", bound)
}
t := New(TARRAY)
t.Extra = &Array{Elem: elem, Bound: bound}
t.SetNotInHeap(elem.NotInHeap())
return t
}

在Go程序编译期间,数组的类型由上述NewArray函数生成,类型 Array 包含两个字段,一个是元素类型 Elem,另一个是数组的大小 Bound,这两个字段共同构成了数组类型,而当前数组是否应该在堆还是栈中初始化也在编译期就确定了。

数组初始化

Go 语言中的数组有两种不同的创建方式,一种是显式的指定数组的大小,另一种是使用 […]T 声明数组,Go 语言会在编译期间通过源代码对数组的大小进行推断:

1
2
arr1 := [4]int{1, 2, 3, 4}
arr2 := [...]int{1, 2, 3, 4}

上述两种声明方式在运行期间得到的结果是完全相同的,后面的那种方式会被『转换』成为前一种,这个就是编译器对数组大小的推导

数组大小推导过程

上述两种不同的声明方式会导致编译器做出完全不同的处理,如果我们使用第一种方式 [5]T,那么变量的类型在编译进行到类型检查阶段就会被提取出来,随后会使用cmd/compile/internal/types/type.go中的NewArrary函数创建包含数组大小的 Array 类型。

当我们使用 [...]T 的方式声明数组时,虽然在这一步也会创建一个 Array 类型 Array{Elem: elem, Bound: -1},但是其中的数组大小上限会是 -1,这里的 -1 只是一个占位符,编译器会在后面的 cmd/compile/internal/gc/typecheck.go文件中的 函数中对该数组的大小进行推导,具体的代码如下:

这个typecheckcomplit函数使用一个typecheckarraylit的函数来确定数组中元素的数量。我们继续往下追

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// The result of typecheckcomplit MUST be assigned back to n, e.g.
// n.Left = typecheckcomplit(n.Left)
func typecheckcomplit(n *Node) (res *Node) {
...

// Need to handle [...]T arrays specially.
if n.Right.Op == OTARRAY && n.Right.Left != nil && n.Right.Left.Op == ODDD {
n.Right.Right = typecheck(n.Right.Right, ctxType)
if n.Right.Right.Type == nil {
n.Type = nil
return n
}
elemType := n.Right.Right.Type

length := typecheckarraylit(elemType, -1, n.List.Slice(), "array literal")

n.Op = OARRAYLIT
n.Type = types.NewArray(elemType, length)
n.Right = nil
return n
}

...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// typecheckarraylit type-checks a sequence of slice/array literal elements.
func typecheckarraylit(elemType *types.Type, bound int64, elts []*Node, ctx string) int64 {
// If there are key/value pairs, create a map to keep seen
// keys so we can check for duplicate indices.
var indices map[int64]bool
for _, elt := range elts {

...

key++
if key > length {
length = key
}
}
return length
}

我们可以看到,Go1.14.2的代码中对于这种[...]T声明的数组,单独抽了一个方法,但是还是通过遍历每个元素的方式来确定数组的长度。 另外,因为声明这种数组时需要使用三个点(Dot),所以在编译器中就被称作 DDDArray。

所以我们可以看出 […]T{1, 2, 3} 和 [3]T{1, 2, 3} 在运行时是完全等价的,[…]T 这种初始化方式也只是 Go 语言为我们提供的一种语法糖,当我们不想计算数组中的元素个数时就可以通过这种方法较少一些工作。

语句转换

对于一个由字面量组成的数组,根据数组元素数量的不同,编译器会在负责初始化字面量的 cmd/compile/internal/gc/sinit.go文件中的anylit函数中做两种不同的优化:

  • 当元素数量小于或者等于 4 个时,会直接将数组中的元素放置在栈上;
  • 当元素数量大于 4 个时,会将数组中的元素放置到静态区并在运行时取出;
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
func anylit(n *Node, var_ *Node, init *Nodes) {
t := n.Type
switch n.Op {

...

case OSTRUCTLIT, OARRAYLIT:
if !t.IsStruct() && !t.IsArray() {
Fatalf("anylit: not struct/array")
}

if var_.isSimpleName() && n.List.Len() > 4 {
// lay out static data
vstat := staticname(t)
vstat.Name.SetReadonly(true)

ctxt := inInitFunction
if n.Op == OARRAYLIT {
ctxt = inNonInitFunction
}
fixedlit(ctxt, initKindStatic, n, vstat, init)

// copy static to var
a := nod(OAS, var_, vstat)

...

当数组的元素小于或者等于四个时,cmd/compile/internal/gc/sinit.go的文件中的fixedlit函数 会负责在函数编译之前将 [3]{1, 2, 3} 转换成更加原始的语句:

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
36
37
38
39
40
41
42
43
44
45
/ fixedlit handles struct, array, and slice literals.
// TODO: expand documentation.
func fixedlit(ctxt initContext, kind initKind, n *Node, var_ *Node, init *Nodes) {
var splitnode func(*Node) (a *Node, value *Node)

...

for _, r := range n.List.Slice() {
a, value := splitnode(r)

switch value.Op {
case OSLICELIT:
if (kind == initKindStatic && ctxt == inNonInitFunction) || (kind == initKindDynamic && ctxt == inInitFunction) {
slicelit(ctxt, value, a, init)
continue
}

case OARRAYLIT, OSTRUCTLIT:
fixedlit(ctxt, kind, value, a, init)
continue
}

islit := isLiteral(value)
if (kind == initKindStatic && !islit) || (kind == initKindDynamic && islit) {
continue
}

// build list of assignments: var[index] = expr
setlineno(a)
a = nod(OAS, a, value)
a = typecheck(a, ctxStmt)
switch kind {
case initKindStatic:
genAsStatic(a)
case initKindDynamic, initKindLocalCode:
a = orderStmtInPlace(a, map[string][]*Node{})
a = walkstmt(a)
init.Append(a)
default:
Fatalf("fixedlit: bad kind %d", kind)
}

}

...

当数组中的元素数目小于四个的时候,kind的接受的值是initKindLocalCode,述代码会将原有的初始化语句 [3]int{1, 2, 3} 拆分成一个声明变量的表达式和几个赋值表达式,这些表达式会完成对数组的初始化:

1
2
3
4
var arr [3]int
arr[0] = 1
arr[1] = 2
arr[2] = 3

如果当前数组的元素大于 4 个,在上面的anylit 方法会先获取一个唯一的staticname ,然后会调用上面的fixedlit方法,在静态存储区初始化数组中的元素并将临时变量赋值给当前的数组。

总结起来,如果数组中元素的个数小于或者等于 4 个,那么所有的变量会直接在栈上初始化,如果数组元素大于 4 个,变量就会在静态存储区初始化然后拷贝到栈上,这些转换后的代码才会继续进入中间代码生成和机器码生成两个阶段,最后生成可以执行的二进制文件。

访问和赋值

无论是在栈上还是静态存储区,数组在内存中其实就是一连串的内存空间,表示数组的方法就是一个指向数组开头的指针、数组中元素的数量以及数组中元素类型占的空间大小,如果我们不知道数组中元素的数量,访问时就可能发生越界,而如果不知道数组中元素类型的大小,就没有办法知道应该一次取出多少字节的数据,如果没有这些信息,我们就无法知道这片连续的内存空间到底存储了什么数据:

数组内存结构

数组访问越界是非常严重的错误,Go 语言中对越界的判断是可以在编译期间由静态类型检查完成的,cmd/compile/internal/gc/typecheck.go中的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
36
// The result of typecheck1 MUST be assigned back to n, e.g.
// n.Left = typecheck1(n.Left, top)
func typecheck1(n *Node, top int) (res *Node) {
if enableTrace && trace {
defer tracePrint("typecheck1", n)(&res)
}

switch n.Op {
case OLITERAL, ONAME, ONONAME, OTYPE:
if n.Sym == nil {
break
}

if n.Op == ONAME && n.SubOp() != 0 && top&ctxCallee == 0 {
yyerror("use of builtin %v not in function call", n.Sym)
n.Type = nil
return n
}


...

if !n.Bounded() && Isconst(n.Right, CTINT) {
x := n.Right.Int64()
if x < 0 {
yyerror("invalid %s index %v (index must be non-negative)", why, n.Right)
} else if t.IsArray() && x >= t.NumElem() {
yyerror("invalid array index %v (out of bounds for %d-element array)", n.Right, t.NumElem())
} else if Isconst(n.Left, CTSTR) && x >= int64(len(strlit(n.Left))) {
yyerror("invalid string index %v (out of bounds for %d-byte string)", n.Right, len(strlit(n.Left)))
} else if n.Right.Val().U.(*Mpint).Cmp(maxintval[TINT]) > 0 {
yyerror("invalid %s index %v (index too large)", why, n.Right)
}
}

...
  • 访问数组的索引是非整数时会直接报错 —— non-integer array index %v;
  • 访问数组的索引是负数时会直接报错 —— “invalid array index %v (index must be non-negative)”;
  • 访问数组的索引越界时会直接报错 —— “invalid array index %v (out of bounds for %d-element array)”;

数组和字符串的一些简单越界错误都会在编译期间发现,直接使用整数或者常量访问数组,但是如果使用变量去访问数组或者字符串时,编译器就无法发现对应的错误了,这时就需要 Go 语言运行时发挥作用了;Go 语言运行时在发现数组、切片和字符串的越界操作会由运行时的 panicIndex 和 runtime.goPanicIndex 函数触发程序的运行时错误并导致崩溃退出:

1
2
3
4
5
6
7
8
9
TEXT runtime·panicIndex(SB),NOSPLIT,$0-8
MOVL AX, x+0(FP)
MOVL CX, y+4(FP)
JMP runtime·goPanicIndex(SB)

func goPanicIndex(x int, y int) {
panicCheck1(getcallerpc(), "index out of range")
panic(boundsError{x: int64(x), signed: true, y: y, code: boundsIndex})
}

Go 语言对于数组的访问还是有着比较多的检查的,它不仅会在编译期间提前发现一些简单的越界错误并插入用于检测数组上限的函数调用,而在运行期间这些插入的函数会负责保证不会发生越界错误。

数组的赋值和更新操作也会生成 SSA ,生成期间计算出数组当前元素的内存地址,然后修改当前内存地址的内容。

赋值的过程中会先确定目标数组的地址,再通过 PtrIndex 获取目标元素的地址,最后使用 Store 指令将数据存入地址中,从上面的这些 SSA 代码中我们可以看出无论是数组的寻址还是赋值都是在编译阶段完成的,没有运行时的参与。

切片

数组在Go语言中其实并不常用,更常用的数据结构是切片,切片就是动态数组,其长度并不固定,我们可以随意向切片中追加元素,而且切片会在容量不足的时候自动扩容。

切片类型的声明方式与数组有一些相似,由于切片的长度是动态的,所以声明时只需要指定切片中的元素类型:

1
2
[]int
[]interface{}

从切片的定义能推测出,切片在编译期间的生成的类型只会包含切片中的元素类型,即int或者 interface{} 等。ccmd/compile/internal/types/type.go文件中的NewSlice方法就是编译期间用于创建 Slice 类型的函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// NewSlice returns the slice Type with element type elem.
func NewSlice(elem *Type) *Type {
if t := elem.Cache.slice; t != nil {
if t.Elem() != elem {
Fatalf("elem mismatch")
}
return t
}

t := New(TSLICE)
t.Extra = Slice{Elem: elem}
elem.Cache.slice = t
return t
}

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

切片类型

编译期间的切片是 Slice 类型的,但是在运行时切片由如下的 SliceHeader 结构体表示,其中 Data 字段是指向数组的指针,Len 表示当前切片的长度,而 Cap 表示当前切片的容量,也就是 Data 数组的大小:

1
2
3
4
5
6
7
8
9
10
11
// SliceHeader is the runtime representation of a slice.
// It cannot be used safely or portably and its representation may
// change in a later release.
// Moreover, the Data field is not sufficient to guarantee the data
// it references will not be garbage collected, so programs must keep
// a separate, correctly typed pointer to the underlying data.
type SliceHeader struct {
Data uintptr
Len int
Cap int
}

Data作为一个指针,指向的数组是一片连续的内存空间。这片内存空间可以用于存储切片中保存的所有元素。数组中的元素只逻辑上的概念,底层的存储其实都是连续的。所以可以将切片理解成一片连续的内存空间加上长度与容量的标识。

Go切片结构

官方解释Slice就是底层数组的一个View,切片引入了一个抽象层,提供了对数组中部分片段的引用,作为数组的引用,我们可以在运行区间可以修改它的长度,如果底层的数组长度不足就会触发扩容机制,切片中的数组就会发生变化,不过在上层看来切片时没有变化的,上层只需要与切片打交道不需要关心底层的数组变化。

Go语言获取数组大小、对数组中的元素的读写在编译期间就已经进行了简化,由于数组的内存固定且连续,很多操作都会变成对内存的直接读写;但是切片是运行时才会确定内容的结构,所有的操作还需要依赖 Go 语言的运行时来完成。

初始化

Go切片初始化有三种方式:

  1. 通过下标的方式获得数组或者切片的一部分;
  2. 使用字面量初始化新的切片;
  3. 使用关键字make创建切片:
    1
    2
    3
    arr[0:3] or slice[0:3]
    slice := []int{1, 2, 3}
    slice := make([]int, 10)

使用下标

这是最原始,最底层,也是最接近汇编语言的方式,这种操作会被编译器转换为OpSliceMake操作,
cmd/compile/internal/types/type.go文件中的NewSlice可以看到具体操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// NewSlice returns the slice Type with element type elem.
func NewSlice(elem *Type) *Type {
if t := elem.Cache.slice; t != nil {
if t.Elem() != elem {
Fatalf("elem mismatch")
}
return t
}

t := New(TSLICE)
t.Extra = Slice{Elem: elem}
elem.Cache.slice = t
return t
}

可以写一段简单的代码看一下发生了什么:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main

import "fmt"

func newSlice() []int {
arr := [6]int{1, 2, 3, 4, 5, 6}
slice := arr[0:3]
return slice
}

func main() {
s := newSlice()
fmt.Print(s)
}

可以使用GOSSAFUNC 生成中间代码:

1
2
3
4
5
$ GOSSAFUNC=main go build op_slice_make.go
# runtime
dumped SSA to /usr/local/go/src/runtime/ssa.html
# command-line-arguments
dumped SSA to ./ssa.html

可以在decompose builtin阶段,slice := arr[0:3] 对应的部分:

1
2
3
4
name &arr[*[6]int]: v11
name slice.ptr[*int]: v11
name slice.len[int]: v14
name slice.cap[int]: v17

也就是说其实切片的底层是数组,只是包含了三个部分:数组指针,切片大小和容量。同时在SSA中还可以看到v27 (7) = SliceMake <[]int> v11 v25 v26 (~r0[[]int], slice[[]int], s[[]int]) , SliceMake 这个操作需要接受元素类型,数组指针,切片大小和切片容量来创建新的切片。

使用字面量

我们除了使用下标的方式创建切片,还可以使用字面量来创建切片[]int{1,2,3,4,5},在cmd/compile/internal/gc/sinit.go文件的slicelit函数会将这个展开成为下面的代码:

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

我们能看到租后进行的[:]其实是创建切片的真实方法,也就是说[:]操作是创建切片最底层的一种方法。

使用make关键字

使用字面量的方式创建切片,大部分的工作就都会在编译期间完成,但是当我们使用 make 关键字创建切片时,很多工作都需要运行时的参与;调用方必须在 make 函数中传入一个切片的大小以及可选的容量。
cmd/compile/internal/gc/typecheck.go文件的typecheck1方法中能看到,make的时候会对参数进行校验:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

case OMAKE:
ok |= ctxExpr
args := n.List.Slice()
if len(args) == 0 {
yyerror("missing argument to make")
n.Type = nil
return n
}

n.List.Set(nil)

...

switch t.Etype {

...

case TSLICE:
if i >= len(args) {
yyerror("missing len argument to make(%v)", t)
n.Type = nil
return n
}

l = args[i]
i++
l = typecheck(l, ctxExpr)
var r *Node
if i < len(args) {
r = args[i]
i++
r = typecheck(r, ctxExpr)
}

if l.Type == nil || (r != nil && r.Type == nil) {
n.Type = nil
return n
}
if !checkmake(t, "len", l) || r != nil && !checkmake(t, "cap", r) {
n.Type = nil
return n
}
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)
n.Type = nil
return n
}

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

...

...

这个typecheck1函数不仅会检查len是否传入,还会保证传入的容量 cap 一定大于或者等于 len,除了校验参数之外,当前函数会将 OMAKE 节点转换成 OMAKESLICE,随后的中间代码生成阶段在 cmd/compile/internal/gc/walk.go文件中的walkexpr 函数中的 OMAKESLICE 分支依据两个重要条件对这里的 OMAKESLICE 进行转换:

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

当发生逃逸后者非常大的时候,在runtime/slice.go文件中的makeslice函数可以看到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func makeslice(et *_type, len, cap int) unsafe.Pointer {
mem, overflow := math.MulUintptr(et.size, uintptr(cap))
if overflow || mem > maxAlloc || len < 0 || len > cap {
// NOTE: Produce a 'len out of range' error instead of a
// 'cap out of range' error when someone does make([]T, bignumber).
// 'cap out of range' is true too, but since the cap is only being
// supplied implicitly, saying len is clearer.
// See golang.org/issue/4085.
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}

return mallocgc(mem, et, true)
}

mallocgc函数中还有一大段的注释解释了如何尽可能节约分配堆内存的空间。

总之,就是说在分配的切片比较小的情况下,会初始化数组并且直接通过下转换的方式来得到数组的切片,这两部分操作都会在编译阶段完成,编译器会在栈上或者静态存储区创建数组;而分配比较大或者出现逃逸的情况下会在堆上初始化。

makeslice函数主要工作就是计算当前切片占用的内存空间并在堆上申请一片连续的内存,它使用如下的方式计算占用的内存:

内存空间 = 切片中元素大小 x 切片容量

创建切片的过程中如果发生了以下错误就会直接导致程序触发运行时错误并崩溃:

  1. 内存空间的大小发生了溢出
  2. 申请的内存大于最大可分配的内存;
  3. 传入的长度小于 0 或者长度大于容量;

Go的内存分配器实在是过于复杂,半天没研究出来什么有用的信息,就先跳过。

makeslice函数会返回指向底层数组的指针,之前版本的 Go 语言中,数组指针、长度和容量会被合成一个 slice 结构并返回。现在改为构建结构体SliceHeader,这工作就都交给 runtime.makeslice的调用方处理了,这些调用方会在编译期间构建切片结构体。Go官方说这个改动能够减少 ~0.2%Go 语言包大小并且能够减少 92 个 panicindex 的调用,占整个 Go 语言二进制的 ~3.5%1

1
2
3
4
5
type SliceHeader struct {
Data uintptr
Len int
Cap int
}

访问元素

对切片常见的操作就是获取它的长度或者容量,这两个不同的函数 lencapGo 语言的编译器看成是两种特殊的操作,即 OLENOCAP,它们会在 SSA 生成阶段被 cmd/compile/internal/gc/ssa.go文件中的expr函数转换成 OpSliceLenOpSliceCap 操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// expr converts the expression n to ssa, adds it to s and returns the ssa result.
func (s *state) expr(n *Node) *ssa.Value {

...

case OLEN, OCAP:
switch {
case n.Left.Type.IsSlice():
op := ssa.OpSliceLen
if n.Op == OCAP {
op = ssa.OpSliceCap
}
return s.newValue1(op, types.Types[TINT], s.expr(n.Left))
case n.Left.Type.IsString(): // string; not reachable for OCAP
return s.newValue1(ssa.OpStringLen, types.Types[TINT], s.expr(n.Left))
case n.Left.Type.IsMap(), n.Left.Type.IsChan():
return s.referenceTypeBuiltin(n, s.expr(n.Left))
default: // array
return s.constInt(types.Types[TINT], n.Left.Type.NumElem())
}

...

len(slice) 或者 cap(slice) 在一些情况下会被直接替换成切片的长度或者容量,不需要运行时从切片结构中获取:

1
2
3
(SlicePtr (SliceMake ptr _ _ )) -> ptr
(SliceLen (SliceMake _ len _)) -> len
(SliceCap (SliceMake _ _ cap)) -> cap

除了获取切片的长度和容量之外,访问切片中元素使用的 OINDEX 操作也会在中间代码生成期间转换成对地址的直接访问:

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

func (s *state) expr(n *Node) *ssa.Value {

...

case OINDEX:
switch {
case n.Left.Type.IsString():
if n.Bounded() && Isconst(n.Left, CTSTR) && Isconst(n.Right, CTINT) {
// Replace "abc"[1] with 'b'.
// Delayed until now because "abc"[1] is not an ideal constant.
// See test/fixedbugs/issue11370.go.
return s.newValue0I(ssa.OpConst8, types.Types[TUINT8], int64(int8(strlit(n.Left)[n.Right.Int64()])))
}
a := s.expr(n.Left)
i := s.expr(n.Right)
len := s.newValue1(ssa.OpStringLen, types.Types[TINT], a)
i = s.boundsCheck(i, len, ssa.BoundsIndex, n.Bounded())
ptrtyp := s.f.Config.Types.BytePtr
ptr := s.newValue1(ssa.OpStringPtr, ptrtyp, a)
if Isconst(n.Right, CTINT) {
ptr = s.newValue1I(ssa.OpOffPtr, ptrtyp, n.Right.Int64(), ptr)
} else {
ptr = s.newValue2(ssa.OpAddPtr, ptrtyp, ptr, i)
}
return s.load(types.Types[TUINT8], ptr)
case n.Left.Type.IsSlice():
p := s.addr(n, false)
return s.load(n.Left.Type.Elem(), p)

...

切片的操作基本都是在编译期间完成的,除了访问切片的长度、容量或者其中的元素之外,使用range 遍历切片时也会在编译期间转换成形式更简单的代码。

range遍历

追加和扩容

向切片中追加元素是非常常见的操作,在 Go 语言中我们会使用 append 关键字向切片追加元素,中间代码生成阶段的 cmd/compile/internal/gc/ssa.go文件中我们可以看到append方法,该方法追加元素会根据返回值是否会覆盖原变量,分别进入两种流程,如果 append 返回的『新切片』不需要赋值回原有的变量,就会进入如下的处理流程(代码中的注释):

1
2
3
4
5
6
7
8
9
10
11
ptr, len, cap := s
newlen := len + 3
if newlen > cap {
ptr, len, cap = growslice(s, newlen)
newlen = len + 3 // recalculate to avoid a spill
}

*(ptr+len) = e1
*(ptr+len+1) = e2
*(ptr+len+2) = e3
return makeslice(ptr, newlen, cap)

先对结构体进行解析,获取它的指针,大小和容量,如果在追加后切片的大小大于其容量,就会对切片进行扩容,使用的方法是runtime/slice.go文件中的growslice方法 ,扩容策略我们后面再讲;如果append后的切片会覆盖原来的切片,就会使用另一种方式改写关键字,在cmd/compile/internal/gc/ssa.go文件中append程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a := &s
ptr, len, cap := s
newlen := len + 3
if uint(newlen) > uint(cap) {
newptr, len, newcap = growslice(ptr, len, cap, newlen)
vardef(a) // if necessary, advise liveness we are writing a new a
*a.cap = newcap // write before ptr to avoid a spill
*a.ptr = newptr // with write barrier
}
newlen = len + 3 // recalculate to avoid a spill
*a.len = newlen
// with write barriers, if needed:
*(ptr+len) = e1
*(ptr+len+1) = e2
*(ptr+len+2) = e3

如果我们选择覆盖原有的变量,也不需要担心切片的拷贝,因为Go语言的编译器已经对这种情况作了优化。大概如下:

slice扩容

Go语言的切片扩容策略:

  1. 如果期望容量大于当前容量的两倍就会使用期望容量;
  2. 如果当前切片容量小于 1024 就会将容量翻倍;
  3. 如果当前切片容量大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;

runtime/slice.go文件中的growslice方法中能看到如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func growslice(et *_type, old slice, cap int) slice {
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
if newcap <= 0 {
newcap = cap
}
}
}

确定了切片的容量之后,就可以计算切片中新数组占用的内存了,计算的方法就是将目标容量和元素大小相乘,计算新容量时可能会发生溢出或者请求的内存超过上限,这个时候就会出现panic

若切片中元素不是指针类型,那么就会调用 memclrNoHeapPointers 将超出切片当前长度的位置清空并在最后使用 memmove 将原数组内存中的内容拷贝到新申请的内存中。这里的memclrNoHeapPointersmemmove都是用目标机器上的汇编指令实现的。

growslice函数最终会返回一个新的slice结构,其中包含了新的数组指针、大小和容量,这个返回的三元组最终会改变原有的切片,帮助 append 完成元素追加的功能。

切片拷贝

拷贝切片并不常用,Go提供了一个内置的copy(a,b),在cmd/compile/internal/gc/walk.go文件中copyany函数能看到具体的操作 其实是分了两种情况处理,如果copy不是运行时调用,copy(a,b)会被直接转换为下面的代码:

1
2
3
4
5
6
7
n := len(a)
if n > len(b) {
n = len(b)
}
if a.ptr != b.ptr {
memmove(a.ptr, b.ptr, n*sizeof(elem(a)))
}

其中 memmove 会负责对内存进行拷贝,在其他情况下,编译器会使用 slicecopy 函数替换运行期间调用的 copy,例如:`go copy(a, b):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func slicecopy(to, fm slice, width uintptr) int {
if fm.len == 0 || to.len == 0 {
return 0
}
n := fm.len
if to.len < n {
n = to.len
}
if width == 0 {
return n
}
...

size := uintptr(n) * width
if size == 1 {
*(*byte)(to.array) = *(*byte)(fm.array)
} else {
memmove(to.array, fm.array, size)
}
return n
}

两种不同的拷贝方式一般都会通过 memmove 将整块内存中的内容拷贝到目标的内存区域中,如下图所示:
切片扩容

相比于依次对元素进行拷贝,这种方式能够提供更好的性能,但是需要注意的是,哪怕使用 memmove 对内存成块进行拷贝,但是这个操作还是会占用非常多的资源,在大切片上执行拷贝操作时一定要注意性能影响。