3.2 切片

Kesa...大约 8 分钟

和数组不同，切片是动态的，向切片中添加元素其会在容量不足时自动扩容。

切片声明只需要元素类型即可：

[]int
[]interface{}

切片在编译期间生成的类型只包含元素类型，cmd/compile/internal/types.NewSliceopen in new window

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

// 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 {
			base.Fatalf("elem mismatch")
		}
		return t
	}

	t := New(TSLICE)
	t.Extra = Slice{Elem: elem}
	elem.cache.slice = t
	if elem.HasTParam() {
		t.SetHasTParam(true)
	}
	return t
}

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

// Slice contains Type fields specific to slice types.
type Slice struct {
	Elem *Type // element type
}

切片内的元素类型在编译期就已确定，存储在Type.Extra字段中以帮助程序在运行时动态获取。

3.2.1 数据结构

编译期的切片是cmd/compile/internal/types.Slice 类型的

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

// Slice contains Type fields specific to slice types.
type Slice struct {
	Elem *Type // element type
}

运行时的切片类型由 reflect.SliceHeaderopen in new window

// go1.17 

// 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: 指向数组的指针
Len: 当前切片的长度
Cap: 当前切片的容量

golang-slice-struct 切片引入了一个抽象层，提供了对数组部分片段的引用。对于上层来说，无需关心底层数组的变化，只需关注切片的操作即可。

和数组不同，数组内存固定且连续在编译期即可确定操作的内存位置，而切片是动态的，操作需要依赖运行时。

3.2.2 初始化

Golang 包含三种初始化切片的方式：

通过索引（下标）获取数组或切片的一部分
通过字面量初始化新的切片
通过关键字make创建切片

arr[0:3] or slice[0:3]
slice := []int{1, 2, 3}
slice := make([]int, length, capacity)

使用索引（下标）

使用下标初始化是最底层的操作，其他操作最后会使用下标初始化。

编译器将语句转换成OpSliceMake操作，将如下代码编译成 SSA 中间代码：

func newSlice() []int {
    a := [3]int{1, 2, 3}
    s := a[0:1]
    return s
}

decompose builtin 部分：

b4:
v1 (?) = InitMem <mem>
v3 (?) = SB <uintptr>
v6 (?) = Addr <*uint8> {type:[3]int} v3
v7 (+11) = StaticLECall <*[3]int,mem> {AuxCall{runtime.newobject}} [16] v6 v1
v8 (11) = SelectN <mem> [1] v7
v9 (11) = SelectN <*[3]int> [0] v7 (s.ptr[*int], &a[*[3]int])
v10 (?) = Addr <*[3]int> {command-line-arguments..stmp_0} v3
v11 (11) = Move <mem> {[3]int} [24] v9 v10 v8
v12 (?) = Const64 <int> [1] (s.len[int])
v15 (?) = Const64 <int> [3] (s.cap[int])
v22 (?) = Const64 <int64> [0]
v25 (+12) = SliceMake <[]int> v9 v12 v15
v26 (+13) = MakeResult <[]int,mem> v25 v11
Ret v26 (+13)
name &a[*[3]int]: v9
name s.ptr[*int]: v9
name s.len[int]: v12
name s.cap[int]: v15

由上可以看出，SliceMake 接受四个参数：元素类型，数组指针，长度和容量。使用下标创建切片并不会拷贝数组或切片中的数据，而是构造了指向相同数组的新切片，所以改变新切片会影响原切片。

字面量

使用字面量时，和数组类似，编译器会将其展开成如下流程：

// 使用 []int{1,2,3} 初始化
var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice := vauto[:]

推断数组长度，并创建新数组
将字面量数据存入数组
创建指向数组的指针
将静态存储区的数组vstat赋值给指针vatuo所在的地址
通过[:]获取指向vauto的切片

第 5 步使用的是下标初始化。

关键字 make

使用make时，需要传入长度和容量（可选），编译期使用cmd/compile/internal/typecheck.typecheck1open in new window校验make的参数：

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

// typecheck1 should ONLY be called from typecheck.
func typecheck1(n ir.Node, top int) ir.Node {
    ...
	case ir.OMAKE:
		n := n.(*ir.CallExpr)
		return tcMake(n)
	...
	// No return n here!
	// Individual cases can type-assert n, introducing a new one.
	// Each must execute its own return n.
}

cmd/compile/internal/typecheck.tcMakeopen in new window

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

// tcMake typechecks an OMAKE node.
func tcMake(n *ir.CallExpr) ir.Node {
    ...
    i := 1
    ...
    case types.TSLICE:
		if i >= len(args) {
			base.Errorf("missing len argument to make(%v)", t)
			n.SetType(nil)
			return n
		}

		l = args[i]
		i++
		l = Expr(l)
		var r ir.Node
		if i < len(args) {
			r = args[i]
			i++
			r = Expr(r)
		}
		...
		if ir.IsConst(l, constant.Int) && r != nil && ir.IsConst(r, constant.Int) && constant.Compare(l.Val(), token.GTR, r.Val()) {
			base.Errorf("len larger than cap in make(%v)", t)
			n.SetType(nil)
			return n
		}
		nn = ir.NewMakeExpr(n.Pos(), ir.OMAKESLICE, l, r)
    ...
}

上述函数主要进行如下操作：

检查len是否传入
保证len小于等于cap
并将节点转化为ir.OMAKESLICE

节点转化之后，cmd/compile/internal/walk.walkExpropen in new window 会根据两个条件转化节点

切片的长度和容量是否足够小
切片是否发生了逃逸，最终在堆上初始化

切片不会发生逃逸且非常小

例如：make([]int, 3, 4)会直接转化成如下代码：

var arr [4]int
n := arr[:3]

上述操作都会在编译期完成，编译器会在栈或静态存储区中创建数组并将[:3]转换成OpSliceMake操作。

切片会发生逃逸或非常大

运行时runtime.makesliceopen in new window 在堆上初始化切片：

// go1.17 runtime/slice.go

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)
}

主要操作是计算切片占用的内存空间并在堆上申请一片连续内存，计算占用空间公式如下:

$\text{内存空间大小} = \text{切片元素大小} \times \text{切片容量}$

其次检查如下错误并触发 panic：

内存空间溢出
申请内存大于最大可分配内存
长度小于 0 或长度小于容量

3.2.3 访问元素

获取长度和容量被视作两种特殊操作：OLEN和 OCAP，在 SSA 生成阶段会被转换成OpSliceLen和OpSliceCap。

访问切片中的字段可能会触发decompose builtin 阶段的优化，len(a)或cap(a)某些情况下直接替换成长度和容量，无需在运行时获取。

访问元素使用的OINDEX在编译期间转换成对地址的直接访问。

此外，range也将被转换成更简单的循环。

3.2.4 追加和扩容

追加

使用append向切片中添加新元素，有两种不同情况：

返回值不会覆盖原变量
返回值覆盖原变量

若返回值不会覆盖原变量，则进入如下流程

// append(slice, 1, 2, 3)
ptr, len, cap := slice
newlen := len + 3
if newlen > cap {
    ptr, len, cap = growslice(slice, newlen)
    newlen = len + 3
}
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
return makeslice(ptr, newlen, cap)

结构切片
若追加后容量大于当前容量，进行扩容
追加新元素

若返回值覆盖原变量

// slice = append(slice, 1, 2, 3)
a := &slice
ptr, len, cap := slice
newlen := len + 3
if uint(newlen) > uint(cap) {
   newptr, len, newcap = growslice(slice, newlen)
   vardef(a)
   *a.cap = newcap
   *a.ptr = newptr
}
newlen = len + 3
*a.len = newlen
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3

流程和之前类似，但不会创建新的切片结构体，而是在原切片上直接修改。

扩容

扩容时调用runtime/slice.growSliceopen in new window

// go1.17 runtime/slice.go

func growslice(et *_type, old slice, cap int) slice {
	...
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		if old.cap < 1024 {
			newcap = doublecap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
    ...
}

扩容前确认新的容量，然后根据当前容量选择不同的策略扩容：

若期望容量大于当前容量的两倍，使用期望容量
若当前容量小于 1024，新容量为原容量的两倍
若当前容量大于 1024，原容量每次增加 25%，直到大于期望容量

上述代码段计算的只是大致容量，后序需要进行根据元素大小进行内存对齐，内存对齐函数runtime.roundupsizeopen in new window会根据数组runtime.class_to_size open in new window向上取整，使用该数组的整数可以提高内存的分配效率并减少碎片。

例如:

var arr []int64
arr = append(arr, 1, 2, 3, 4, 5)

期望分配的内存为 40Ｂ，向上取整为48Ｂ，此时容量就是 48/8 = 6。

3.2.5 拷贝

编译期

若copy(a, b)不在运行时被调用，那么在编译期会被转换成如下代码：

n := len(a)
if n > len(b) {
    n = len(b)
}
if a.ptr != b.ptr {
    memmove(a.ptr, b.ptr, n*sizeof(elem(a))) 
}

运行时

若copy(a, b)在运行时发生（如：go copy(a, b)），则会使用 runtime.slicecopyopen in new window替换copy操作。

两种拷贝方式都会用到函数runtime.memmoveopen in new window将整块内存拷贝到目标内存区域中，比依次拷贝元素有着更好的性能。

3.2.6 小结

切片很多功能都是由运行时实现的。

注意大切片扩容或复制时会发生大规模的内存拷贝，要减少此类操作避免影响性能。

Reference

昵称

邮箱

网址

按正序
按倒序
按热度

3.2 切片

# 3.2.1 数据结构

# 3.2.2 初始化

# 使用索引（下标）

# 字面量

# 关键字 make

# 切片 不会发生逃逸 且 非常小

# 切片 会发生逃逸 或 非常大

# 3.2.3 访问元素

# 3.2.4 追加和扩容

# 追加

# 扩容

# 3.2.5 拷贝

# 编译期

# 运行时

# 3.2.6 小结

# Reference

预览: