3.1 数组

Kesa...大约 8 分钟

3.1.1 概述

数组是由相同类型元素的集合组成的数据结构, 在计算机中使用一块连续的内存来保存其中的元素, 可以使用索引快速访问元素.

常见的数组一般是一维数组, 多维数组在数值和图形结算领域较为常见.

Golang 中的数组是一种基本数据类型, 数组的类型由两个因素确定:

元素类型
数组长度(数组大小), 数组能够最大存储的元素个数

[2]int 和 [20]int 		是两种不同类型, 数组长度不同
[2]int 和 [2]interface{} 是两种不同类型, 数组元素类型不同

Golang 的数组在初始化之后大小就无法改变, 存储元素相同但是大小不同将被视作不同的类型, 只有两者完全相同时才是同一类型.

编译期间的数组类型由函数 cmd/compile/internal/types.NewArrayopen in new window 生成.

// go1.17 cmd/compile/internal/types/type.go 

// NewArray returns a new fixed-length array Type.
func NewArray(elem *Type, bound int64) *Type {
	if bound < 0 {
		base.Fatalf("NewArray: invalid bound %v", bound)
	}
	t := New(TARRAY)
	t.Extra = &Array{Elem: elem, Bound: bound}
	t.SetNotInHeap(elem.NotInHeap())
	if elem.HasTParam() {
		t.SetHasTParam(true)
	}
	return t
}

数组类型包含两个字段: Elem和Bound
数组是否应该在堆栈中初始化也是在编译期确定的.

3.1.2 初始化

Golang 数组的初始化有两种不同的创建方式:

显式指定数组大小
使用[...T]声明数组, Golang 将在编译期通过源代码推导数组大小

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

上述两种声明在运行期间得到的结果是完全相同的.

后一种方式在编译期间会完成对数组大小的推导, 推导过程有两步:

上限推导
语句转换

上限推导

若使用[10]T这种形式, 那么变量类型将在类型检查open in new window 阶段就会被提取出来, 随后使用 cmd/compile/internal/types.NewArrayopen in new window 创建结构体 cmd/compile/internal/types.Arrayopen in new window

// go1.17 cmd/compile/internal/types/type.go

// Array contains Type fields specific to array types.
type Array struct {
	Elem  *Type // element type
	Bound int64 // number of elements; <0 if unknown yet
}

若使用[...T]的形式, 编译器将会在函数 cmd/compile/internal/gc.typecheckcomplitopen in new window 函数中对该数组大小进行推导:

(备注: 原书中提到的函数在go1.17之后已删除, go1.17的函数位置为 cmd/compile/internal/typecheck.tcComplitopen in new window)

// go1.17 cmd/compile/internal/typecheck/expr.go

// The result of tcCompLit MUST be assigned back to n, e.g.
//
//	n.Left = tcCompLit(n.Left)
func tcCompLit(n *ir.CompLitExpr) (res ir.Node) {
	if base.EnableTrace && base.Flag.LowerT {
		defer tracePrint("tcCompLit", n)(&res)
	}

	lno := base.Pos
	defer func() {
		base.Pos = lno
	}()

	ir.SetPos(n)

	t := n.Type()
	base.AssertfAt(t != nil, n.Pos(), "missing type in composite literal")

	switch t.Kind() {
	... 
	case types.TARRAY:
		typecheckarraylit(t.Elem(), t.NumElem(), n.List, "array literal")
		n.SetOp(ir.OARRAYLIT)
	...
	}

	return n
}

函数会使用 cmd/compile/internal/gc.typecheckarraylitopen in new window 遍历元素的方式计算数组中元素的数量. (备注: 原书中提到的函数在go1.17之后已删除, go1.17的函数位置为 cmd/compile/internal/typecheck.typecheckarraylitopen in new window)

[3]T{1,2,3}和[...]T{1,2,3}是在运行时等价的，[...]T是Golang语法糖，当不想手动计算数组长度时，可以减少工作量。

语句转换

对于一个由字面量组成的数组，根据数组数量的不同，编译器在负责初始化字面量的函数cmd/compile/internal/gc.anylitopen in new window 中做两种不同的优化 (备注: 原书中提到的函数在go1.17之后已删除, go1.17的函数位置为 cmd/compile/internal/walk.anylitopen in new window)：

当元素数量小于或等于 4 个时，直接将数组中的元素放到栈上
当元素数量大于 4 个时，将数组中的元素放到静态区并在运行时取出

// go1.17 cmd/compile/internal/walk/complit.go

func anylit(n ir.Node, var_ ir.Node, init *ir.Nodes) {
	t := n.Type()
	switch n.Op() {
	default:
		base.Fatalf("anylit: not lit, op=%v node=%v", n.Op(), n)
	...

	case ir.OSTRUCTLIT, ir.OARRAYLIT:
		n := n.(*ir.CompLitExpr)
		if !t.IsStruct() && !t.IsArray() {
			base.Fatalf("anylit: not struct/array")
		}

		if isSimpleName(var_) && len(n.List) > 4 {
			...
		}

		var components int64
		if n.Op() == ir.OARRAYLIT {
			components = t.NumElem()
		} else {
			components = int64(t.NumFields())
		}
		// initialization of an array or struct with unspecified components (missing fields or arrays)
		if isSimpleName(var_) || int64(len(n.List)) < components {
			appendWalkStmt(init, ir.NewAssignStmt(base.Pos, var_, nil))
		}

		fixedlit(inInitFunction, initKindLocalCode, n, var_, init)
	
    ...
	}
}

当数组元素数目小于或等于 4 个，函数fixedlit将接收参数initKindLocalCode，会将原有的初始化语句拆分成声明表达式和赋值表达式：

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

// go1.17 cmd/compile/internal/walk/complit.go

func anylit(n ir.Node, var_ ir.Node, init *ir.Nodes) {
	t := n.Type()
	switch n.Op() {
	default:
		base.Fatalf("anylit: not lit, op=%v node=%v", n.Op(), n)
	...

	case ir.OSTRUCTLIT, ir.OARRAYLIT:
		n := n.(*ir.CompLitExpr)
		if !t.IsStruct() && !t.IsArray() {
			base.Fatalf("anylit: not struct/array")
		}

		if isSimpleName(var_) && len(n.List) > 4 {
			// lay out static data
			vstat := readonlystaticname(t)

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

			// copy static to var
			appendWalkStmt(init, ir.NewAssignStmt(base.Pos, var_, vstat))

			// add expressions to automatic
			fixedlit(inInitFunction, initKindDynamic, n, var_, init)
			break
		}
        
    ...
	}
}

若数组元素大于 4 个，则通过readonlystaticname获取staticname，调用fixedlit在静态存储区初始化数组并将临时变量赋值给数组。

假设初始化[5]int{1,2,3,4,5}流程的伪代码如下：

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

综上，在不考虑逃逸分析的情况下：

数组元素小于等于 4 个，直接在栈上初始化
数组元素大于 4 个，在静态存储区初始化，然后拷贝到栈上

这些转换后的代码才会继续进入中间代码生成open in new window和机器码生成open in new window两个阶段，最后生成可以执行的二进制文件。

3.1.3 访问和赋值

访问

数组在内存中的占用一段连续的内存空间，并通过指向数组开头的指针、元素数量和元素类型占用空间大小来表示数组。

数组访问越界是非常严重的错误，Golang 在编译期的静态类型检查判断数组越界，cmd/compile/internal/gc.typecheck1open in new window会验证访问数组的索引(备注：go1.17 的函数为cmd/compile/internal/typecheckopen in new window，并调用cmd/compile/internal/typecheck.tcIndexopen in new window )：

// go1.17 cmd/compile/internal/typecheck/typecheck.go

// typecheck1 should ONLY be called from typecheck.
func typecheck1(n ir.Node, top int) ir.Node {
	if n, ok := n.(*ir.Name); ok {
		typecheckdef(n)
	}

	switch n.Op() {
	default:
		ir.Dump("typecheck", n)
		base.Fatalf("typecheck %v", n.Op())
		panic("unreachable")

	...
	case ir.OINDEX:
		n := n.(*ir.IndexExpr)
		return tcIndex(n)
	...
	}

	// No return n here!
	// Individual cases can type-assert n, introducing a new one.
	// Each must execute its own return n.
}

// tcIndex typechecks an OINDEX node.
func tcIndex(n *ir.IndexExpr) ir.Node {
	...
	switch t.Kind() {
	default:
		base.Errorf("invalid operation: %v (type %v does not support indexing)", n, t)
		n.SetType(nil)
		return n

	case types.TSTRING, types.TARRAY, types.TSLICE:
		n.Index = indexlit(n.Index)
		if t.IsString() {
			n.SetType(types.ByteType)
		} else {
			n.SetType(t.Elem())
		}
		why := "string"
		if t.IsArray() {
			why = "array"
		} else if t.IsSlice() {
			why = "slice"
		}

		if n.Index.Type() != nil && !n.Index.Type().IsInteger() {
			base.Errorf("non-integer %s index %v", why, n.Index)
			return n
		}

		if !n.Bounded() && ir.IsConst(n.Index, constant.Int) {
			x := n.Index.Val()
			if constant.Sign(x) < 0 {
				base.Errorf("invalid %s index %v (index must be non-negative)", why, n.Index)
			} else if t.IsArray() && constant.Compare(x, token.GEQ, constant.MakeInt64(t.NumElem())) {
				base.Errorf("invalid array index %v (out of bounds for %d-element array)", n.Index, t.NumElem())
			} else if ir.IsConst(n.X, constant.String) && constant.Compare(x, token.GEQ, constant.MakeInt64(int64(len(ir.StringVal(n.X))))) {
				base.Errorf("invalid string index %v (out of bounds for %d-byte string)", n.Index, len(ir.StringVal(n.X)))
			} else if ir.ConstOverflow(x, types.Types[types.TINT]) {
				base.Errorf("invalid %s index %v (index too large)", why, n.Index)
			}
		}

	...
	return n
}

若索引非整数，报错"non-integer %s index %v
若索引为负数，报错invalid %s index %v (index must be non-negative)
若索引越界，报错invalid array index %v (out of bounds for %d-element array

当使用字面量或常量作为索引访问数组时，在编译期可以发现错误。

当使用变量做为索引访问时，需要在运行时阻止不合法的访问：

arr[4]: invalid array index 4 (out of bounds for 3-element array)
arr[i]: panic: runtime error: index out of range [4] with length 3

Golang 语言运行时在发现数组、切片和字符串的越界操作会由运行时的 runtime.panicIndexopen in new window 和 runtime.goPanicIndexopen in new window 触发程序的运行时错误并导致崩溃退出：

// go1.17 runtime/asm_389.s 

TEXT runtime·panicIndex(SB),NOSPLIT,$0-8
	MOVL	AX, x+0(FP)
	MOVL	CX, y+4(FP)
	JMP	runtime·goPanicIndex(SB)

// go1.17 runtime/panic.go

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

当数组访问通过编译期检查之后，会被转换成 SSA 指令。假设如下代码：

package check

func outOfRange() int {
	arr := [3]int{1, 2, 3}
	i := 4
	elem := arr[i]
	return elem
}

$ GOSSAFUNC=outOfRange go build array.go
dumped SSA to ./ssa.html

b1:
    ...
    v22 (6) = LocalAddr <*[3]int> {arr} v2 v20
    v23 (6) = IsInBounds <bool> v21 v11
If v23 → b2 b3 (likely) (6)

b2: ← b1-
    v26 (6) = PtrIndex <*int> v22 v21
    v27 (6) = Copy <mem> v20
    v28 (6) = Load <int> v26 v27 (elem[int])
    ...
Ret v30 (+7)

b3: ← b1-
    v24 (6) = Copy <mem> v20
    v25 (6) = PanicBounds <mem> [0] v21 v11 v24
Exit v25 (6)

数组的访问操作生成了判断数组上限的指令 IsInBounds 以及当条件不满足时触发程序崩溃的 PanicBounds 指令。

编译器会将 PanicBounds 指令转换成 runtime.panicIndex 函数，当数组下标没有越界时，编译器会先获取数组的内存地址和访问的下标、利用 PtrIndex 计算出目标元素的地址，最后使用 Load 操作将指针中的元素加载到内存中。

当然只有当编译器无法对数组下标是否越界无法做出判断时才会加入 PanicBounds 指令交给运行时进行判断。

赋值

数组的赋值和更新操作 a[i] = 2 也会生成 SSA 生成期间计算出数组当前元素的内存地址，然后修改当前内存地址的内容，这些赋值语句会被转换成如下所示的 SSA 代码：

b1:
    ...
    v21 (5) = LocalAddr <*[3]int> {arr} v2 v19
    v22 (5) = PtrIndex <*int> v21 v13
    v23 (5) = Store <mem> {int} v22 v20 v19
    ...

赋值的过程中会先确定目标数组的地址，再通过 PtrIndex 获取目标元素的地址，最后使用 Store 指令将数据存入地址中。

由上可以看出数组寻址和赋值都是在编译阶段完成的，没有运行时的参与。

3.1.4 小结

数组的访问同时依赖编译器和运行时，大多数数组操作在编译期间会转换成直接读写内存，在中间代码生成期间会插入运行时方法runtime.panicIndex防止发生越界。

Reference

昵称

邮箱

网址

按正序
按倒序
按热度

3.1 数组

# 3.1.1 概述

# 3.1.2 初始化

# 上限推导

# 语句转换

# 3.1.3 访问和赋值

# 访问

# 赋值

# 3.1.4 小结

# Reference

预览: