深入浅出 go slice

这是【深入浅出 go xx】系列的第一篇。在该系列中,会对 go 的一些基本特性,从定义到源码进行整理和记录。

希望不要跳票。

什么是 slice?

slice 是 Go 的一种基本的数据结构。它在数组之上做了一层封装,相当于动态数组。它持有对底层数组的引用。

因此:

  • 如果你将一个 slice 赋给另一个 slice,那么,这两个 slice 都会指向同一个数组。
  • 如果一个函数的参数包含 slice,那么,对入参 slice 的元素的改动对于该函数的调用者是可见的。类似于传递一个指向底层数组的指针给函数。

每个 slice 都有两个属性:length 和 capacity。前者是 slice 的底层数组的元素个数,后者是底层数组的长度。length 会随着 slice 的元素改动在 capacity 的范围内发生改变。可以通过内置函数 cap 查看 slice 的 capacity,通过 len 查看 length。可以使用 append 方法将数据追加到 slice 之后。如果数据超过了 capacity,那么,会为 slice 重新分配空间,并返回最终的 slice。

注意:对 nil slice 使用 caplen 方法是合法的,此时会返回 0。

如何使用 slice

可以使用内置函数 make([]T, length, capacity) 创建一个新的已初始化的类型为 T 的 slice。例如:

1
2
// 创建并初始化一个类型为 int,length 为 50,capacity 为 100 的 slice
slc := make([]int, 50, 100)

上面的代码等价于创建一个长度为 50 的数组,然后对其进行切片:

1
slc := ([100]int)[0:50]

此外,还可以使用字面量创建切片:

1
2
3
// 会创建一个 length 为 5,capacity 为 5 的 slice
// 注意:[] 里面不要写容量。否则创建的就是数组,而不是 slice 了。
slc := []int{1, 2, 3, 4, 5}

slice 的底层实现

基于 go 1.11.1

结构定义

可以在 /src/runtime/slice.go 中找到对 slice 的定义:

1
2
3
4
5
type slice struct {
array unsafe.Pointer // 指向一个数组的指针
len int // 当前切片的长度
cap int // 当前切片的容量
}

创建切片

使用以下方法创建切片:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func makeslice(et *_type, len, cap int) slice {
// 根据切片元素的类型,获取最大可创建元素个数
maxElements := maxSliceCap(et.size)
// 判断要创建切片的长度:非零且不超过最大个数
if len < 0 || uintptr(len) > maxElements {
panicmakeslicelen()
}
// 判断要创建切片的容量:非零且不超过最大个数
if cap < len || uintptr(cap) > maxElements {
panicmakeslicecap()
}
// 根据容量申请所需内存
p := mallocgc(et.size*uintptr(cap), et, true)
// 返回申请好内存的切片的首地址
return slice{p, len, cap}
}

还有一个针对大小和容量是 int64 的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func makeslice64(et *_type, len64, cap64 int64) slice {
// 长度和容量必须在 int 范围内
len := int(len64)
if int64(len) != len64 {
panicmakeslicelen()
}

cap := int(cap64)
if int64(cap) != cap64 {
panicmakeslicecap()
}
// 将长度和容量转换成 int 后,调用创建
return makeslice(et, len, cap)
}

append()

golang 中有一个内置函数可以对 slice 进行追加。函数声明如下:

1
func append(slice []Type, elems ...Type) []Type

该函数会将 elems 追加到 slice 之后。如果 slice 有足够的 capacity,那么直接追加。否则,会分配一个新的底层数组。

有三种使用方式:

1
2
3
slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)
slice = append([]byte("hello "), "world"...)

扩容

当一个切片满了,就需要扩容了。扩容动作是通过调用下面函数完成的:

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// growslice handles slice growth during append.
// 三个入参非别是:slice 元素类型,旧的 slice,以及所需的最小 capacity
func growslice(et *_type, old slice, cap int) slice {
if raceenabled {
callerpc := getcallerpc()
racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
}
if msanenabled {
msanread(old.array, uintptr(old.len*int(et.size)))
}

if et.size == 0 {
// 检查:申请的新 capacity 不能小于旧的
if cap < old.cap {
panic(errorString("growslice: cap out of range"))
}
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve old.array in this case.
return slice{unsafe.Pointer(&zerobase), old.len, cap}
}

// 确定新的 slice 的 capacity。其初始值为旧的 slice 的 capacity
newcap := old.cap
doublecap := newcap + newcap
// 1. 如果所需要的最小 capacity 超过两倍的旧的 slice 的 capacity,
// 那么将新的 slice 的 capacity 设置为所需要的最小 capacity
if cap > doublecap {
newcap = cap
} else {
// 2. 否则,当旧的 slice 的 length 小于 1024 时,
// 将新的 slice 的 capacity 设置为两倍的旧的 slice 的 capacity
if old.len < 1024 {
newcap = doublecap
} else {
// 3. 否则,不断地扩张新的 slice 的 capacity 直至它的值不小于所需的最小 capacity。每次扩张的值是当前 capacity 的 1/4(这里会检测这个 capacity 是否为正数,以防止溢出以及死循环)
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// 当新的 slice 的 capacity 溢出时,设置它的值为所需的最小 capacity。
if newcap <= 0 {
newcap = cap
}
}
}

// 根据 slice 的元素类型大小,调整新的 slice 的 capacity
var overflow bool
var lenmem, newlenmem, capmem uintptr
// 针对一些常见的元素类型大小(et.size):
// 1. 当大小为 1 时,无需进行任何乘除操作
// 2. 当大小为 sys.PtrSize 时,编译器会将乘除操作优化为常量移位
// 3. 当大小为 2 的幂时,使用变量移位
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 = roundupsize(uintptr(newcap) * et.size)
overflow = uintptr(newcap) > maxSliceCap(et.size)
newcap = int(capmem / et.size)
}

// 判断异常情况:
// 1. 缩容
// 2. 申请的容量会导致溢出
if cap < old.cap || overflow || capmem > maxAlloc {
panic(errorString("growslice: cap out of range"))
}

var p unsafe.Pointer // 新的 slice 的底层数组
if et.kind&kindNoPointers != 0 {
// 申请内存。此时并不进行初始化
p = mallocgc(capmem, nil, false)
// 将旧的 slice 的底层数组中的元素拷贝到新的 slice 的底层数组中。
memmove(p, old.array, lenmem)
// 调用该函数的 append() 方法将会重写底层数组中从 old.len 到 cap(将会成为新的 slice 新的 length)索引。
// 因此,仅需初始化不会被重写的部分为零值。也就是 cap 之后的位置
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// 重新申请内存,并初始化为零值
p = mallocgc(capmem, et, true)
if !writeBarrier.enabled {
// 如果不能打开写锁,那么把将旧的 slice 的底层数组中的元素拷贝到新的 slice 的底层数组中
memmove(p, old.array, lenmem)
} else {
// 循环拷贝旧的 slice 的值
for i := uintptr(0); i < lenmem; i += et.size {
typedmemmove(et, add(p, i), add(old.array, i))
}
}
}
// 返回:一个新的 slice,
// 这个 slice 的 capacity 的最小值为传入的 cap,并且会将旧的 slice 中的元素拷贝到这个新的 slice 中。
// 这个 slice 的 length 会被设置成旧的 slice 的 length,而不是新的所需的 capacity。
// 这样做的目的是出于代码生成的方便。而在 append 期间,这个 length 是会随着新元素的写入而发生变化的。
return slice{p, old.len, newcap}
}

拷贝

golang 提供了一个内置函数 copy 来进行 slice 拷贝。函数定义如下:

1
func copy(dst, src []Type) int

这个函数会将源 slice src 中的元素拷贝到目标 slice dst 中(有一个特殊场景:它还会将一个字符串中的字节拷贝到一个 bytes slice 中)。源和目标可能会发生重叠。
该函数返回拷贝的元素个数,即 min(len(src), len(dst)

slice 的拷贝是通过以下函数实现的:

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
func slicecopy(to, fm slice, width uintptr) int {
// 如果源 slice 或者目标 slice 的 length 为 0,则无需拷贝,直接返回
if fm.len == 0 || to.len == 0 {
return 0
}
// 记录源 slice 和目标 slice 之间最短的 length
n := fm.len
if to.len < n {
n = to.len
}

if width == 0 {
return n
}

if raceenabled { // 开启了竞争检测
callerpc := getcallerpc()
pc := funcPC(slicecopy)
racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
}
if msanenabled { // 开启了 the memory sanitizer
msanwrite(to.array, uintptr(n*int(width)))
msanread(fm.array, uintptr(n*int(width)))
}

size := uintptr(n) * width
if size == 1 { // common case worth about 2x to do here
// TODO: is this still worth it with new memmove impl?
*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
} else {
memmove(to.array, fm.array, size)
}
return n
}

还有一个函数 func slicestringcopy(to []byte, fm string) int 实现了上面提到的特殊场景。实现跟 slicecopy 相似,这里不再赘述。

slice 使用注意事项

当 slice 作为函数参数,并且在函数中进行修改时……

来源:GopherCon 2018: Jon Bodner - Go Says WAT

考虑以下例子:

1
2
3
4
5
6
7
8
9
10
11
12
func grow(s []int) {
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
s = append(s, 4, 5, 6)
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

func main() {
s := []int{1, 2, 3}
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
grow(s)
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

运行输出

1
2
3
4
value: [1 2 3], length: 3, capacity: 3, addr: 0xc00000a460
value: [1 2 3], length: 3, capacity: 3, addr: 0xc00000a460
value: [1 2 3 4 5 6], length: 6, capacity: 6, addr: 0xc00000c330
value: [1 2 3], length: 3, capacity: 3, addr: 0xc00000a460

为什么调用 grow() 之后得到的 s[1 2 3],而不是 [1 2 3 4 5 6] 呢?

因为在 append 的时候,s 没有足够的容量。因此,会创建一个新的 slice。可以从上面的打印看到,在 append 调用前后,s 的容量和地址都发生了改变。因此,append 并不会对 main 函数中的 s 作出任何修改。

那么,如果我们给 s 设置了一个足够大的 capacity 呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
func grow(s []int) {
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
s = append(s, 4, 5, 6)
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

func main() {
s := make([]int, 0, 10)
s = append(s, 1, 2, 3)
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
grow(s)
fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

运行输出:

1
2
3
4
value: [1 2 3], length: 3, capacity: 10, addr: 0xc00007e0a0
value: [1 2 3], length: 3, capacity: 10, addr: 0xc00007e0a0
value: [1 2 3 4 5 6], length: 6, capacity: 10, addr: 0xc00007e0a0
value: [1 2 3], length: 3, capacity: 10, addr: 0xc00007e0a0

结果是,调用 grow() 之后得到的 s 还是 [1 2 3]

这是因为,上面提到了,一个 slice 是由 arraylencap 一起标识的,并且在作为入参时是按值传递的。因此,无论是在 main 函数,还是在 grow 函数,s 指向的都是同一个底层数组。但是,在 grow 函数中,slen 值发生了改变,而在 main 中,slen 值还是保持了原样。

另一方面,Go 使用 reflect 包的 Value.Pointer 来获取指针,此时,得到的是底层数组的指针,而不是 slice 的指针。因此,打印出来的指针是同一个。

参考