Golang源码分析 - slice切片

Go语言中的切片是一个特殊的数据结构，和C++的 std::vector 一样（但又不完全一样）。

Slice切片

用户能够操控slice的有以下内建函数

  • make 创建一个切片

  • append 向切片中追加数据

  • copy 复制切片数据到另一个切片

  • len/cap 获取切片长度/容量

除此之外，还可以用 slice[from:to] 获取新切片。

slice数据结构定义在 runtime/slice.go 中

1
2
3
4
5
type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

而在 reflect 包中也存在一个 SliceHeader 数据结构，供用户使用

1
2
3
4
5
type SliceHeader struct {
	Data uintptr
	Len  int
	Cap  int
}

虽然切片没有提供删除操作，但是可以通过切片 : 完成一些常规的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func printSlice(slice []int) {
	fmt.Println(slice, len(slice), cap(slice))
}

func main() {
	slice := []int{10, 20, 30}
	slice = append(slice, []int{40, 50, 60}...)
	printSlice(slice)

	// 删除最后一个元素
	slice = slice[:len(slice)-1]
	printSlice(slice)

	// 删除第一个元素
	slice = slice[1:]
	printSlice(slice)

	// 删除下标为2的元素
	slice = append(slice[:2], slice[3:]...)
	printSlice(slice)
}

一般来说从一个数组/切片中获取新的切片通过 a[low : high]，实际上还有另一种方法获取切片：a[low : high : max]，必须满足 0 <= low <= high <= max <= cap(a)。这种情况下返回的新切片 SliceHeader 为：

1
2
3
4
5
6
a := SliceHeader{...}
b := SliceHeader{
  Data: a.Data+low
  Len: high-low
  Cap: max-low
}

使用 a[low:high] 获取新切片实际上省略第三个参数，默认 max=cap(a) ：a[low:high:cap(a)]

举个例子：

1
2
3
4
5
6
7
8
9
10
a := make([]int, 5, 10) // SliceHeader{Ptr, 5, 10}
t := a[2:6:8]						// SliceHeader{Ptr+2, 4, 6}
t2 := t[1:3]						// SliceHeader{Ptr+3, 2, 5}
fmt.Println(len(a), cap(a))
fmt.Println(len(t), cap(t))
fmt.Println(len(t2), cap(t2))
// 输出
5 10
4 6
2 5

想要了解更多有关Go的规范说明可以访问官网：https://go.dev/ref/spec#Slice_expressions

makeslice创建切片

一般获得一个切片有以下几种方式

  • 从数组中获取切片。arr := [...]T{...}; slice := arr[:]

  • 声明切片，默认为零值nil。var slice []T

  • 初始化切片，不为nil。slice := []T{}

  • 通过 make 创建具有长度和一定容量的切片。slice := make([]T, len, cap)

第一种方法是从一个数组中获取一个切片（不会通过 runtime.makeslice），但是要注意，对切片的修改也会影响到数组，这样创建切片的方式比较少见。

最后三种创建切片的方法最终会通过函数 runtime.makeslice 来创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func makeslice(et *_type, len, cap int) unsafe.Pointer {
  // 内存空间大小 = 切片中元每个素数大小 * 切片容量
  // 比如 make([]int, 10) 此时 len=cap=10
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
  // 如果发生以下错误，则panic
	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)
}

上面可以看到 makeslice 创建切片需要的内容空间为 内存空间大小 = 切片中每个元素大小 * 切片容量。其中 math.MulUintptr 看似是一个导出函数，实际上它是 internal 包中的函数，外部用户无法直接使用。

该函数返回一个 uintptr 指针类型，和一个 bool 用于指示此次操作是否溢出。注意其中的 goarch.PtrSize 表示的是一个指针大小（不同架构平台下指针大小不同，比如32位指针大小4个字节，64位下指针大小8个字节）。

1
2
3
4
5
6
7
func MulUintptr(a, b uintptr) (uintptr, bool) {
	if a|b < 1<<(4*goarch.PtrSize) || a == 0 {
		return a * b, false
	}
	overflow := b > MaxUintptr/a
	return a * b, overflow
}

makeslice 发生的错误可能有以下几种：

  • 溢出错误，也就是 内存空间大小 溢出
  • 申请的内存空间大于最大可分配的大小
    • 即 maxAlloc = (1 << heapAddrBits) - (1-_64bit)*1
  • 长度小于0或者切片长度len小于最大切片容量cap

当没有错误发生后，调用 mallocgc 开始真正的内存分配（数组）并返回 数组起始指针。

为何需要使用 SliceHeader 而不直接使用 slice 呢？

一般来说 runtime.slice 是go运行时使用的，如果外部也通过该slice结构体操作切片的话，那么将会额外引入不必要的包和多余的函数。因此，Go在反射库中提供了 SliceHeader 给用户使用，作为轻量级的slice结构体，用于访问切片底层数据

注意，上面的 maekslice 函数 仅仅 返回一个底层数据的指针，最后还需要由 makeslice 的调用方将返回的指针、len、cap构建为 SliceHeader 结构。

具体可以从下面的源文件中 src/cmd/compile/internal/typecheck/expr.go 找到相关的信息

1
2
3
4
5
6
7
8
9
10
11
12
func tcSliceHeader(n *ir.SliceHeaderExpr) ir.Node {
	t := n.Type()
	...
  // 通过 makeslice 返回指向底层数组的指针
	n.Ptr = Expr(n.Ptr)
  // 长度
	n.Len = DefaultLit(Expr(n.Len), types.Types[types.TINT])
  // 容量
	n.Cap = DefaultLit(Expr(n.Cap), types.Types[types.TINT])
	...
	return n
}

growslice扩容

Go中一般是通过 append 对一个切片进行扩容，下面是append使用例子

1
2
3
4
// len=cap=20
slice := make([]int, 20); 
// 此时append slice一定会导致扩容
slice = append(slice, []int{20,30,40})

append追加数据不一定会发生扩容

扩容机制是通过 growslice 完成的，会重新分配内存空间并将旧切片中的数据复制到新数组中

PS：下面的扩容切片函数Go1.18版本的，和之前的版本有一点差别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// old: 要追加数据的旧切片
// cap: 新的容量，也就是旧切片容量+追加数据数量
// 比如 
// slice := []int{10, 20, 30}
// slice = append(slice, []int{40, 50, 60}...)
// 那么此时 growslice 参数中 cap 为 6 
func growslice(et *_type, old slice, cap int) slice {
	if cap < old.cap {
		panic(errorString("growslice: cap out of range"))
	}

  // 如果元素类型大小为0，则返回一个全局 zerobase
  // 这种情况就是 切片元素为空结构体 struct{}
	if et.size == 0 {
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

  // 下面是重要的扩容算法！！！
  // 初步确定切片容量
	newcap := old.cap
	doublecap := newcap + newcap
  // 注意1.18版本扩容算法已变
	if cap > doublecap {
		newcap = cap
	} else {
		const threshold = 256
		if old.cap < threshold {
			newcap = doublecap
		} else {
			// Check 0 < newcap to 检测溢出
			for 0 < newcap && newcap < cap {
				// 平缓newcap增加
				newcap += (newcap + 3*threshold) / 4
			}
			// 如果newcap计算溢出，则设置为cap
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

  // 内存对齐
	var overflow bool
	var lenmem, newlenmem, capmem uintptr
  // 对元素类型大小为1、goarch.PtrSize、2^n 进行优化
	switch {
	case et.size == 1:
		...
	case et.size == goarch.PtrSize:
		lenmem = uintptr(oldLen) * goarch.PtrSize
		newlenmem = uintptr(newLen) * goarch.PtrSize
		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		newcap = int(capmem / goarch.PtrSize)
	case isPowerOfTwo(et.size):
    // 使用移位优化计算
		...
	default:
		...
	}
	
  // 扩容后新的切片数组起始指针地址
	var p unsafe.Pointer
	if et.ptrdata == 0 {
		p = mallocgc(capmem, nil, false)
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
    // 重新分配新的内存并返回
		p = mallocgc(capmem, et, true)
		...
	}
  
  // 将旧切片中的数据复制到新的数组中，该memmove是由汇编代码写的
	memmove(p, old.array, lenmem)
	// 返回新切片结构体slice
	return slice{p, old.len, newcap}
}

注意上面的 zerobase ，是runtime包下的未导出全局变量： var zerobase uintptr。

那么这种情况什么时候发生呢？当切片的元素为 struct{} 空结构体或者切片为空 时就会进入该逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
type space struct{}

func main() {
	slice1 := []space{space{}, space{}}
	slice2 := []space{}
	slice3 := []int{}
	slice4 := []int{10}
	fmt.Println(slice1, len(slice1), cap(slice1))
	fmt.Println(slice2, len(slice2), cap(slice2))
	fmt.Println(slice3, len(slice3), cap(slice3))
	fmt.Println(slice4, len(slice4), cap(slice4))

	fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice1)).Data)
	fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice2)).Data)
	fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice3)).Data)
	fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice4)).Data)
}

// 输出
[{} {}] 2 2
[] 0 0
[] 0 0
[10] 1 1
555f50
555f50
555f50
c0000aa000

为了验证 555f50 是否等于 &runtime.zerobase ，可以使用 delve 调试工具打印该变量： Delve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> main.main() ./main.go:43 (PC: 0x496d65)
    38:         fmt.Println(slice3, len(slice3), cap(slice3))
    39:         fmt.Println(slice4, len(slice4), cap(slice4))
    40:
    41:         fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice1)).Data)
    42:         fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice2)).Data)
=>  43:         fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice3)).Data)
    44:         fmt.Printf("%x\n", (*reflect.SliceHeader)(unsafe.Pointer(&slice4)).Data)
    45: }
(dlv) 
561f50
...
(dlv) p &runtime.zerobase
(*uintptr)(0x561f50)
(dlv)

OK，接下来才是重要的 初步确定切片容量 的算法，注意这里是初步确定，真正的切片容量还需要之后进行 内存对齐。

这里我单独拿出来讨论，其中

  • oldCap 表示 旧切片容量
  • cap 表示 旧切片容量+新追加元素数量，可理解为期望的容量

下面是Go1.18的扩容算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func grow(oldCap int, cap int) int {
	newcap := oldCap
	doublecap := newcap + newcap

  // 直接使用当前的期望容量，因为超过了旧容量的2倍
	if cap > doublecap {
		newcap = cap
	} else {
		const threshold = 256
		if oldCap < threshold {
      // 小切片 容量翻倍
			newcap = doublecap
		} else {
      // 除了每次增加25%容量，还额外多加192
			for 0 < newcap && newcap < cap {
				newcap += (newcap + 3*threshold) / 4
        // newcap += (newcap)/4
        // newcap += 192
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	return newcap
}

在Go1.18之前 扩容算法是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func grow(oldCap int, cap int) int {
	newcap := oldCap
	doublecap := newcap + newcap

	// 直接使用当前的期望容量，因为超过了旧容量的2倍
  if cap > doublecap {
		newcap = cap
	} else {
    // 没有超过旧容量的两倍
		if oldCap < 1024 {
      // 小切片 容量翻倍
			newcap = doublecap
		} else {
      // 每次增加 25% 容量，直到新容量大于期望容量
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
	return newcap
}

对于Go1.18之前的扩容机制，我是这样理解的，一般情况下扩容采取的策略是 翻倍扩容，但是这样又会导致一个问题：导致内存空间浪费，因此Go的切片扩容机制针对这种情况进行了优化。

  • 如果append后的总容量cap，也就是旧切片容量+新追加元素的数量超过了两倍，则直接使用这个期望容量。这种情况就是一次性append了大量的元素，导致切望容量超过了原来的两倍。
  • 反之期望容量在旧切片容量两倍之内，即最大容量上界为旧切片容量两倍，此时如果旧切片容量没有超过1024，则直接翻倍扩容。目的是对于 小切片（容量小于1024）直接翻倍扩容，没必要再计算了。
  • 否则每次增加25%的容量，直到新容量大于期望容量，这种策略就是防止盲目的翻倍扩容导致内存空间浪费。

而Go1.18更新后扩容机制发生了变化，小切片最大容量不再是1024，而是256，同时在计算新容量时除了每次增加25%容量，还额外多加了192。

举个例子来说：假如旧切片容量oldCap为10000，append的元素数量为5000，则期望的容量cap为15000，采取不同的策略扩容：

  • 直接翻倍扩容：newcap=20000
  • Go1.18之前版本：按比例增长：newcap=15625
  • Go1.18之后版本：按比例增长：newcap=16057

虽然Go1.17和1.18在计算扩容后新的容量得到的大小不一样，但是别忘了，最后还需要计算内存对齐大小，经过内存对齐后的大小两者是一样的。

除了计算扩容大小之外，还需要计算扩容后的内存对齐大小，下面通过一个例子讲解是如何计算内存对齐大小的。

1
2
3
4
5
6
7
8
9
var slice []int64 = make([]int64, 0)
slice = append(slice, 1, 2, 3, 4, 5)
fmt.Println(unsafe.Sizeof(slice))
fmt.Println(len(slice))
fmt.Println(cap(slice))
// 输出
// 24
// 5
// 6

当执行 append 时，调用 growslice(oldSlice={ptr, 0, 0}, cap=5])，此时 5 > 0+0 ，即 newcap = 5，由于元素类型为 int64，大小为8个字节，即64位下指针大小 goarch.PtrSize=8。

接下来就是计算内存对齐大小：

1
2
3
4
5
lenmem = uintptr(old.len) * goarch.PtrSize
newlenmem = uintptr(cap) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)

转换为就是

1
2
3
4
5
lenmem = uintptr(0) * 8 = 0
newlenmem = uintptr(5) * 8 = 40
capmem = roundupsize(uintptr(5) * 8) = 48
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(48 / 8) = 6

注意，上面的重点是 capmem = roundupsize(uintptr(5) * 8) = 48 ，那么 roundupsize做了什么？

roundupsize内存对齐

该函数位于 src/runtime/msize.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
	maxSmallSize = 32 << 10
	smallSizeDiv = 8
	smallSizeMax = 1024
*/
func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		if size <= smallSizeMax-8 {
			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
		} else {
			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
		}
	}
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize)
}

// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
	return (n + a - 1) / a
}

其中 class_to_size 和size_to_class8是一个数组，也就是 内存对齐表（具体位于 src/runtime/sizeclasses.go） ，这两个数组在Go中内存分配中还会见到（因为Go大部分采用了TCMalloc多级缓存内存分配算法）。

  • size_to_class8 表示需要多少个8字节来内存对齐
  • class_to_size 表示对应的内存对齐后的字节大小
1
2
size_to_class8：0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11...
class_to_size：0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208...

因此当我们调用 roundupsize(40*8) 时，实际为：

1
2
3
divRoundUp(40, 8) = ceil(40/8) = 5，也就是有5个8字节单位
size_to_class8[5] = 5
class_to_size[5] = 48，因此对齐后的内存大小/切片最大容量 为 48 字节，而不是 40 字节。

slicecopy切片复制

Go中使用 copy(to, from) 拷贝切片，举个例子：

1
2
3
var slice1 []int
var slice2 []int = make([]int, 10);
copy(slice1, slice2)

具体实现位于 src/runtime/slice.go 下的 slicecopy 函数，该函数比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 size == 1 {
		*(*byte)(toPtr) = *(*byte)(fromPtr)
	} else {
		memmove(toPtr, fromPtr, size)
	}
	return n
}

最终拷贝操作 runtime.memmove 由汇编完成的。

总结

Go在1.18版本中加入了 泛型，相比之前发生很多的变化，其中就包括了切片扩容计算，在我写这篇文章之前，我在网上搜寻的资料大部分还是之前的版本，截至目前，自Go1.18正式发布过去很多天了，为了保持与时俱进肯定要研究最新的啦😄。

希望对你有帮助～😘