数组和切片是 Go 语言中常见的数据结构,很多刚刚使用 Go 的开发者往往会混淆这两个概念,数组作为最常见的集合在编程语言中是非常重要的,除了数组之外,Go 语言引入了另一个概念 — 切片,切片与数组有一些类似,但是它们的不同之处导致使用上会产生巨大的差别。
这里我们将从 Go 语言 编译期间 的工作和运行时来介绍数组以及切片的底层实现原理,其中会包括数组的初始化以及访问、切片的结构和常见的基本操作。
数组
数组是由相同类型元素的集合组成的数据结构,计算机会为数组分配一块连续的内存来保存数组中的元素,我们可以利用数组中元素的索引快速访问元素对应的存储地址,常见的数组大多都是一维的线性数组,而多维数组在数值和图形计算领域却有比较常见的应用。
数组作为一种数据类型,一般情况下由两部分组成,其中一部分表示了数组中存储的元素类型,另一部分表示数组最大能够存储的元素个数,Go 语言的数组类型一般是这样的:
[10]int
[200]interface{}
Go 语言中数组的大小在初始化之后就无法改变,数组存储元素的类型相同,但是大小不同的数组类型在 Go 语言看来也是完全不同的,只有两个条件都相同才是同一个类型。
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
}
编译期间的数组类型 Array
就包含两个结构,一个是元素类型 Elem
,另一个是数组的大小上限 Bound
,这两个字段构成了数组类型,而当前数组是否应该在堆栈中初始化也在编译期间就确定了。
创建
Go 语言中的数组有两种不同的创建方式,一种是我们显式指定数组的大小,另一种是编译器通过源代码自行推断数组的大小:
arr1 := [3]int{1, 2, 3}
arr2 := [...]int{1, 2, 3}
后一种声明方式在编译期间就会被『转换』成为前一种,下面我们先来介绍数组大小的编译期推导过程。
上限推导
这两种不同的方式会导致编译器做出不同的处理,如果我们使用第一种方式 [10]T
,那么变量的类型在编译进行到 类型检查 阶段就会被推断出来,在这时编译器会使用 NewArray
创建包含数组大小的 Array
类型,而如果使用 [...]T
的方式,虽然在这一步也会创建一个 Array
类型 Array{Elem: elem, Bound: -1}
,但是其中的数组大小上限会是 -1
的结构,这意味着还需要后面的 typecheckcomplit
函数推导该数组的大小:
func typecheckcomplit(n *Node) (res *Node) {
// ...
switch t.Etype {
case TARRAY, TSLICE:
var length, i int64
nl := n.List.Slice()
for i2, l := range nl {
i++
if i > length {
length = i
}
}
if t.IsDDDArray() {
t.SetNumElem(length)
}
}
}
这个删减后的 typecheckcomplit
函数通过遍历元素来推导当前数组的长度,我们能看出 [...]T
类型的声明不是在运行时被推导的,它会在类型检查期间就被推断出正确的数组大小。
语句转换
虽然 [...]T{1, 2, 3}
和 [3]T{1, 2, 3}
在运行时是完全等价的,但是这种简短的初始化方式也只是 Go 语言为我们提供的一种语法糖,对于一个由字面量组成的数组,根据数组元素数量的不同,编译器会在负责初始化字面量的 anylit
函数中做两种不同的优化:
func anylit(n *Node, var_ *Node, init *Nodes) {
t := n.Type
switch n.Op {
case OSTRUCTLIT, OARRAYLIT:
if n.List.Len() > 4 {
vstat := staticname(t)
vstat.Name.SetReadonly(true)
fixedlit(inNonInitFunction, initKindStatic, n, vstat, init)
a := nod(OAS, var_, vstat)
a = typecheck(a, ctxStmt)
a = walkexpr(a, init)
init.Append(a)
break
}
fixedlit(inInitFunction, initKindLocalCode, n, var_, init)
// ...
}
}
- 当元素数量小于或者等于 4 个时,会直接将数组中的元素放置在栈上;
- 当元素数量大于 4 个时,会将数组中的元素放置到静态区并在运行时取出;
当数组的元素小于或者等于四个时,fixedlit
会负责在函数编译之前将批了语法糖外衣的代码转换成原有的样子:
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)
a = nod(OAS, a, value)
a = typecheck(a, ctxStmt)
switch kind {
case initKindStatic:
genAsStatic(a)
case initKindLocalCode:
a = orderStmtInPlace(a, map[string][]*Node{})
a = walkstmt(a)
init.Append(a)
default:
Fatalf("fixedlit: bad kind %d", kind)
}
}
}
由于传入的类型是 initKindLocalCode
,上述代码会将原有的初始化语法拆分成一个声明变量的语句和 N 个用于赋值的语句:
var arr [3]int
arr[0] = 1
arr[1] = 2
arr[2] = 3
但是如果当前数组的元素大于 4 个时,anylit
方法会先获取一个唯一的 staticname
,然后调用 fixedlit
函数在静态存储区初始化数组中的元素并将临时变量赋值给当前的数组:
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)
setlineno(value)
a = nod(OAS, a, value)
a = typecheck(a, ctxStmt)
switch kin