Go学习之Slice

Sunday, July 3, 2022

1. 概述

数组在 Go 语言中没那么常用,更常用的数据结构是切片,即动态数组。我们可以向切片中追加元素,它会在容量不足时自动扩容

Go 语言中,切片类型的声明方式与数组相似,区别在于声明切片时只需指定切片中的元素类型。

编译期间生成切片类型的函数为 src/cmd/compile/internal/types/type.go::NewArray,从源码可以看出,切片内元素的类型都是在编译期确定的,编译器确定了类型后,会将类型存储在 Extra 字段中帮助程序在运行时动态获取。

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

编译器的切片是 cmd/complie/internal/types.Slice 类型,如下所示:

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

运行时切片可由 reflect.SliceHeader 表示,如下所示:

// 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:当前切片的容量,即 Data 数组的大小

Data 是一块连续的内存空间,可以将切片理解成一块连续的内存空间加上长度和容量的标识。

切片引入了一个抽象层,提供了对数组部分连续片段的引用,而作为数组的引用,可以在运行时修改长度和范围。当切片底层的数组长度不足时会自动扩容,切片指向的数组可能会发生变化。不过在上层看来切片没有变化,上层只需要与切片打交道,不需要关心数组的变化。

2. 初始化

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

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

2.1 使用下标

使用小标创建切片是最原始也是最接近汇编语言的方式,它是所有方法中最为底层的一种。编译器会将语句转换成 OpSliceMake 操作,如下:

package slice

// newSlice 生成切片
func newSlice() []int {
	arr := [3]int{1, 2, 3}
	slice := arr[0:1]
	return slice
}

使用 GOSSAFUNC 变量编译上述代码:GOSSAFUNC=newSlice go build new.go,ssa 中间代码中 decompose builtin 阶段代码如下:

decompose builtin [22354 ns]

...

v25 (6) = SliceMake <[]int> v9 v12 v15

...

name &arr[*[3]int]: v9
name slice.ptr[*int]: v9
name slice.len[int]: v12
name slice.cap[int]: v15

从上述结果可以看出,SliceMake 操作接收了四个变量:

  • 元素类型
  • 数组指针
  • 切片大小
  • 容量

需要注意的是,使用下标初始化切片不会复制原数组或原切片的数据,而只会创建一个指向原数组的切片结构体,所以修改新切片的数据也会修改原切片

2.2 字面量

使用字面量 []int{1, 2, 3} 创建切片时,相关的操作如下:

  • 根据切片中的元素数量推断底层数组的大小并创建一个数组 a
  • 将这些字面量元素存储到初始化的数组 a 中
  • 创建一个同样指向 [3]int 类型的数组指针 b
  • 将静态存储区的数组 a 赋值给数组 b 指针所在的地址
  • 通过 [:] 操作获取一个底层使用 b 的切片

从以上可以看出,[:] 操作是创建切片的一个最底层方法。另外,如果使用字面量创建切片,大部分的工作会在编译期间完成。

3.3 关键字

使用 make 关键字创建切片时,很多工作需要运行时的参与;调用方法必须向 make 函数传入切片的大小及可选的容量。类型检查期间,会由 src/cmd/compile/internal/gc/typecheck.go@typecheck1 函数校验入参,相关代码如下:

func typecheck1(n *Node, top int) (res *Node) {
	
	...

	switch n.Op {

	...

	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)
		l := args[0]
		l = typecheck(l, ctxType)
		t := l.Type
		if t == nil {
			n.Type = nil
			return n
		}

		i := 1
		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

		}

		...

	}

	...

}

上述函数不仅会检查 len 是否传入,还会保证传入的容量 cap 一定大于或等于 len。另外,该函数会将 OMAKE 节点转换成 OMAKESLICE,函数 src/cmd/compile/internal/gc/walk.go@walkexpr 会依据以下两个条件转换 OMAKESLICE 类型的节点:

  • 切片大小和容量是否足够小
  • 切片是否发生了逃逸

如果切片发生了逃逸或者非常大,运行时需要 runtime.makeslice 函数在堆中初始化切片。

如果没有发生逃逸并且非常小,则 make 初始化方式会初始化数组并通过下标 [:] 的方式得到数组对应的切片。

这两部分操作都会在编译阶段完成,编译器会在栈上或者静态存储区创建数组,并将 [:] 操作转换成 OpSliceMake 操作。

以下是 runtime.makeslice 函数的代码:

maxAlloc = (1 << heapAddrBits) - (1-_64bit)*1

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

func panicmakeslicelen() {
	panic(errorString("makeslice: len out of range"))
}

func panicmakeslicecap() {
	panic(errorString("makeslice: cap out of range"))
}

上述函数的主要作用是计算切片占用的内存空间,并在堆中申请一块连续的内存,计算方式:内存空间 = 切片中元素大小 * 切片容量

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

  • 内存空间大小发生溢出
  • 申请的内存大于最大可分配内存
  • 传入的长度小于0或大于容量

3. 访问元素

使用 lencap 获取长度或者容量是切片最常见的操作,编译器将它们看成两种特殊操作 — OLENOCAP

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

访问切片的元素使用的 OINDEX 操作也会在中间代码生成期间转换成对地址的直接访问。

切片的操作基本都是在编译期间完成的,除了访问切片的长度、容量或其中的元素外,编译期间也会将包含 range 关键字的遍历转换成形式更简单的循环。

4. 追加和扩容

切片扩容时,会先从切片中获取它的数组指针、大小和容量,如果在追加元素后切片大小小于容量,就会调用 runtime.growslice 对切片进行扩容并将新元素依次加入切片。

4.1 扩容流程

中间代码生成阶段的 src/cmd/compile/internal/gc/ssa.go@state.append 函数会根据返回值是否覆盖原变量进入两种流程。

func (s *state) append(n *Node, inplace bool) *ssa.Value {}
  • inplace 为 false,即不需要赋值会原变量,则处理为表达式 append(s, e1, e2, e3)

    	ptr, len, cap := s
    	newlen := len + 3
    	if newlen > cap {
          ptr, len, cap = growslice(s, newlen)
          newlen = len + 3 // recalculate to avoid a spill
    	}
    	// with write barriers, if needed:
    	*(ptr+len) = e1
    	*(ptr+len+1) = e2
    	*(ptr+len+2) = e3
    	return makeslice(ptr, newlen, cap)
    
  • inplace 为 true,即需要赋值会原变量,则处理为表达式 **s = append(s, e1, e2, e3)

    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 语言已经对这种常见情况做了优化。

4.2 扩容方法

扩容是为切片分配新的内存地址,并且复制原切片中元素的过程,方法为 runtime.growslice

growslice 函数在 append 期间处理切片的扩容,传入的参数有切片的元素类型、旧切片以及新的最小容量,该函数返回一个至少具有该容量的新切片,并将旧数据复制其中,新切片的长度设置为旧切片的长度,而不是新的容量,旧切片的长度用于计算在追加新元素写入的位置。

growslice 函数最终会返回一个新切片,其中包含了新的数组指针、大小和容量,这个返回的三元组最终会覆盖原切片。

1. 容量预算
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,就会每次增加 1/4 的容量,直到新容量大于期望容量。

  • 如果当前切片的容量计算溢出或容量为0时,将容量设置为期望容量。

这里需要注意,最新代码已经不再以 1024 做比较,而是 256,并且当前切片大于 1024 时,也不再是每次扩容 1/4,而是 1/4 + 192。这个改动发生于 v1.18.1 版本,官方的说法是:对于容量小的切片,按照2倍的速率扩容和对于容量大的切片,按照1.25倍的速度扩容,为两者提供了平滑的过渡。

image-20220703222724007

2. 内存对齐

上一步对切片的容量进行了计算,确定了切片的大致容量,实际上还需要根据切片中的元素大小进行内存对齐,当元素大小为 1、2 或 8 的倍数时,运行时便会进行内存对齐,代码如下:

var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
  case et.size == 1:
    lenmem = uintptr(old.len)
    newlenmem = uintptr(cap)
    capmem = roundupsize(uintptr(newcap))
    overflow = uintptr(newcap) > maxAlloc
    newcap = int(capmem)
  case et.size == sys.PtrSize:
    lenmem = uintptr(old.len) * sys.PtrSize
    newlenmem = uintptr(cap) * sys.PtrSize
    capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
    overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
    newcap = int(capmem / sys.PtrSize)
  case isPowerOfTwo(et.size):
    var shift uintptr
    if sys.PtrSize == 8 {
      // Mask shift for better code generation.
      shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
    } else {
      shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
    }
    lenmem = uintptr(old.len) << shift
    newlenmem = uintptr(cap) << shift
    capmem = roundupsize(uintptr(newcap) << shift)
    overflow = uintptr(newcap) > (maxAlloc >> shift)
    newcap = int(capmem >> shift)
  default:
    lenmem = uintptr(old.len) * et.size
    newlenmem = uintptr(cap) * et.size
    capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
    capmem = roundupsize(capmem)
    newcap = int(capmem / et.size)
}

其中,roundupsize 函数会将申请的内存向上取整,取整时会使用 runtime.class_to_size 数组,以提高内存的分配效率并减少碎片。

var class_to_size = [_NumSizeClasses]uint16{
	0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448,
	480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096,
	4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480,
	21760, 24576, 27264, 28672, 32768,
}

默认情况下,会将目标容量和元素大小相乘得到占用的内存,如果计算新容量时发现内存溢出或者请求内存超过上限,程序会直接崩溃退出。

如果切片不是指针类型,那么会调用 runtime.memclrNoHeapPointers 将超出切片当前长度的位置清空,并在最后使用 runtime.memmove 将原数组内存中的内容复制到新申请的内存中。

3. 示例

假设有如下追加代码:

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

上述代码执行时,会调用 runtime.growslice 函数进行扩容,并传入期望容量 5,这时期望分配的内存大小为 40 字节,不过由于切片中元素的大小等于 sys.PtrSize,因此会进行内存对齐,调用 runtime.roundupsize 向上取整为 48,因此新切片的容量为 48/8 = 6,并不是5。

实际验证代码:

package main

import (
	"fmt"
)

func main() {
	var arr []int64
	fmt.Println("old", len(arr), cap(arr))
	arr = append(arr, 1, 2, 3, 4, 5)
	fmt.Println("new", len(arr), cap(arr))
}

执行结果:

old 0 0
new 5 6

这里附上 Go 语言中各个基础类型的大小:

  • bit(位):计算机中数据的最小单位,二进制数中的一个数位,0或者1
  • Byte(字节):计算机中数据的基本单位,每8位(bit)组成一个字节
类型 大小
int8 1字节
int16 2字节
int32 4字节
int64 8字节
int 4字节(32位)/8字节(64位)
float32 4字节
float64 8字节
string 1字节(英文)/2~4字节(中文,取决于字符编码类型)
bool 1字节

5. 复制切片

复制操作并不常见,当使用 copy(a, b) 进行切片复制时,src/cmd/compile/internal/gc/walk.go@copyany 函数会分两种情况来进行处理:

  • 编译器调用

    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))) }
    
  • 运行时调用

    编译器会使用 runtime.slicecopy 函数替换运行期间调用的 copy,该函数代码如下:

    func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
    	if fromLen == 0 || toLen == 0 {
          return 0
    	}
    
    	n := fromLen
    	if toLen < n {
          n = toLen
    	}
    
    	if width == 0 {
          return n
    	}
    
    	size := uintptr(n) * width
    	if raceenabled {
          callerpc := getcallerpc()
          pc := funcPC(slicecopy)
          racereadrangepc(fromPtr, size, callerpc, pc)
          racewriterangepc(toPtr, size, callerpc, pc)
    	}
    	if msanenabled {
          msanread(fromPtr, size)
          msanwrite(toPtr, size)
    	}
    
    	if size == 1 { // common case worth about 2x to do here
          // TODO: is this still worth it with new memmove impl?
          *(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
    	} else {
          memmove(toPtr, fromPtr, size)
    	}
    	return n
    }
    

以上两种情况,复制时都会通过 runtime.memmove 将整块内存的内容复制到目标内存区域中,相较于依次复制,runtime.memmove 函数的性能更高,但需要注意该函数仍然会占用非常多的资源,在大切片上执行复制操作时一定要注意对性能的影响

6. 总结

切片的很多功能都是由运行时实现的,无论是初始化、追加、扩容还是复制,都可能需要运行时的支持。需要注意,在遇到大切片扩容或复制时,可能会发生大规模的内存复制,一定要减少此类操作已避免对性能的影响。

Go Slice Go

Go学习之Array