Skip to content

Latest commit

 

History

History
409 lines (301 loc) · 15.7 KB

2.切片slice.md

File metadata and controls

409 lines (301 loc) · 15.7 KB

在 Go 语言中，切片类型的声明方式与数组有一些相似，不过由于切片的长度是动态的，所以声明时只需要指定切片中的元素类型：

[]int
[]interface{}

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

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
}

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

数据结构

编译期间的切片是 cmd/compile/internal/types.Slice 类型的，但是在运行时切片可以由如下的 reflect.SliceHeader 结构体表示：

type SliceHeader struct {
	Data uintptr //指向数组中某一元素的指针
	Len  int     //切片长度
	Cap  int     //切片容量
}

因此可以通过 unsafe.Pointer 操纵地址来获取切片的 data、len 和 cap 字段

a := []int{3, 4}
arrayAddr := uintptr(unsafe.Pointer(&b))    // 切片起始地址
lenAddr := arrayAddr + unsafe.Sizeof(1)     // 长度地址
capAddr := arrayAddr + unsafe.Sizeof(1)*2   // 容量地址
println(*((*int)(unsafe.Pointer(lenAddr)))) // len = 2
println(*((*int)(unsafe.Pointer(capAddr)))) // cap = 2

上一节介绍过编译器在编译期间简化了获取数组大小、读写数组中的元素等操作：因为数组的内存固定且连续，多数操作都会直接读写内存的特定位置。但是切片是运行时才会确定内容的结构，所有操作还需要依赖 Go 语言的运行时，下面的内容会结合运行时介绍切片常见操作的实现原理。

初始化

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

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

使用下标

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

// ch03/op_slice_make.go
package opslicemake

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

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

v27 (+5) = SliceMake <[]int> v11 v14 v17

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

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

字面量

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

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

第 5 步中的 [:] 就是上文中使用下标创建切片的方法，从这一点我们也能看出 [:] 操作是创建切片最底层的一种方法。

make关键字

如果使用字面量的方式创建切片，大部分的工作都会在编译期间完成。但是当我们使用 make 关键字创建切片时，很多工作都需要运行时的参与；调用方必须向 make 函数传入切片的大小以及可选的容量，类型检查期间的 cmd/compile/internal/gc.typecheck1 函数会校验入参：

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]
			}
			...
			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 // 将 OMAKE 节点转换成 OMAKESLICE
		}
	...
	}
}

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

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

当切片发生逃逸或者非常大时，运行时需要 runtime.makeslice 在堆上初始化切片；如果当前的切片不会发生逃逸并且切片非常小的时候，make([]int, 3, 4) 会被直接转换成如下所示的代码：

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

上述代码会初始化数组并通过下标 [:3] 得到数组对应的切片，这两部分操作都会在编译阶段完成，编译器会在栈上或者静态存储区创建数组并将 [:3] 转换成上一节提到的 OpSliceMake 操作。

分析了主要由编译器处理的分支之后，我们回到用于创建切片的运行时函数 runtime.makeslice，这个函数的实现很简单：

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 {
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

	return mallocgc(mem, et, true) // 申请内存
}

上述函数的主要工作是计算切片占用的内存空间并在堆上申请一片连续的内存，它使用如下的方式计算占用的内存： $$ 内存空间 = 切片中元素大小 × 切片容量 $$ 虽然编译期间可以检查出很多错误，但是在创建切片的过程中如果发生了以下错误会直接触发运行时错误并崩溃：

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

在之前版本的 Go 语言中，数组指针、长度和容量会被合成一个 runtime.slice 结构，但是从 cmd/compile: move slice construction to callers of makeslice 提交之后，构建结构体 reflect.SliceHeader 的工作就都交给了 runtime.makeslice 的调用方，该函数仅会返回指向底层数组的指针，调用方会在编译期间构建切片结构体：

func typecheck1(n *Node, top int) (res *Node) {
	switch n.Op {
	...
	case OSLICEHEADER:
	switch 
		t := n.Type
		n.Left = typecheck(n.Left, ctxExpr)
		l := typecheck(n.List.First(), ctxExpr)
		c := typecheck(n.List.Second(), ctxExpr)
		l = defaultlit(l, types.Types[TINT])
		c = defaultlit(c, types.Types[TINT])

		n.List.SetFirst(l)
		n.List.SetSecond(c)
	...
	}
}

OSLICEHEADER 操作会创建我们在上面介绍过的结构体 reflect.SliceHeader，其中包含数组指针、切片长度和容量，它是切片在运行时的表示：

type SliceHeader struct {
	Data uintptr
	Len  int
	Cap  int
}

正是因为大多数对切片类型的操作并不需要直接操作原来的 runtime.slice 结构体，所以 reflect.SliceHeader 的引入能够减少切片初始化时的少量开销，该改动不仅能够减少 ~0.2% 的 Go 语言包大小，还能够减少 92 个 runtime.panicIndex 的调用，占 Go 语言二进制的 ~3.5%1。

这结构看起来和 SliceHeader 也没差啊？

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

访问元素

使用 len 和 cap 获取长度或者容量是切片最常见的操作，编译器将这它们看成两种特殊操作，即 OLEN 和 OCAP，cmd/compile/internal/gc.state.expr 函数会在 SSA 生成阶段阶段将它们分别转换成 OpSliceLen 和 OpSliceCap：

func (s *state) expr(n *Node) *ssa.Value {
	switch n.Op {
	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))
		...
		}
	...
	}
}

访问切片中的字段可能会触发 “decompose builtin” 阶段的优化，len(slice) 或者 cap(slice) 在一些情况下会直接替换成切片的长度或者容量，不需要在运行时获取：

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

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

func (s *state) expr(n *Node) *ssa.Value {
	switch n.Op {
	case OINDEX:
		switch {
		case n.Left.Type.IsSlice():
			p := s.addr(n, false)
			return s.load(n.Left.Type.Elem(), p)
		...
		}
	...
	}
}

切片的操作基本都是在编译期间完成的，除了访问切片的长度、容量或者其中的元素之外，编译期间也会将包含 range 关键字的遍历转换成形式更简单的循环，我们会在后面的章节中介绍使用 range 遍历切片的过程。

append追加

append 目前的源码是在编译期间生成的，中间代码生成阶段可见 cmd/compile/internal/gc.state.append 方法。

以 slice = append(slice, 1, 2, 3) 为例：我们会先解构切片结构体获取它的数组指针、大小和容量。如果在追加元素后切片的大小大于容量，那么就会调用 runtime.growslice 对切片进行扩容并将新的元素依次加入切片。否则直接对底层数组赋值。

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)

扩容

  1. 如果期望容量大于当前容量的两倍就会使用期望容量；
  2. 如果当前切片的长度小于 1024 就会将容量翻倍；
  3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；
  4. 之后还会按 spanClass 进行内存对齐（减少碎片）

比如 append([1, 2], 3, 4, 5)，翻倍后容量为 4，但原有 2 个元素加上新的 3 个元素后为 5，大于翻倍数量，因此扩容后容量应为 5。之后还会进行内存对齐，5个int 使用 40bit，spanClass 里向上接近的是 48bit，实际最后的 cap 为 6

// 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.len < 1024 { // 小于 1024 翻倍
			newcap = doublecap 
		} else {
			for 0 < newcap && newcap < cap { // 不断翻 1.25 倍
				newcap += newcap / 4
			}
		}
	}
    
  switch {
    case et.size == 1: // 根据元素大小计算需要申请的空间
    capmem = roundupsize(uintptr(newcap)) // 内存对齐
    newcap = int(capmem)
  }
  
  // 复制旧数组元素到新数组
  p = mallocgc(capmem, et, true)
  memmove(p, old.array, lenmem)
  return slice{p, old.len, newcap}
}

// runtime/msize.go
// 内存对齐，获取最接近的 spanClass 的大小
// Returns size of the memory block that mallocgc will allocate if you ask for the size.
func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		if size <= smallSizeMax-8 {
			return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
		} else {
			return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
		}
	}
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize)
}

拷贝切片

copy(a, b) 底层实际调用 runtime.memmove，将连续内存内容都拷贝到目标区域

Q & A

数组和切片的区别
  1. 切片底层是数组，是对数组的封装，是截取了数组的一部分，所以叫切片。多个切片可以使用同一个底层数组，各切各的
  2. 数组长度固定，声明对象时需指定长度；切片是变长的，可以自动扩容
  3. 数组是值类型，可以比较，传参是值拷贝；切片是引用类型
nil 切片与空切片的区别

nil 切片没做初始化，没有分配内存

空切片只是底层数组没有初始化，其结构体本身、 len、capacity 字段都是有值的

并发问题

切片并非并发安全的。不加锁并发 append 时会产生数据覆盖、数据缺少、零值数据的情况。

前两种问题比较好理解，零值是因为追加数据时，是先 1. 修改切片长度、2. 赋新值两步完成的。那么在刚完成 1未完成 2时，切片末尾元素便是零值。此时另一个协程若再追加数据，刚好触发扩容，便会导致零值元素被复制至扩容后的切片。

参考

Go语言圣经 - 4.2 Slice

draveness - 3.2-切片