0%

Golang源码阅读(一) slice

Golang Slice源码解读。结构、初始化、append、拷贝

首先我们可以通过make方法创建一个slice,类型为int,长度为0,容量为2。然后通过append方法往slice中加入数据。也就是append的时候必定会扩容

1
2
3
4
5
6
7
8
9
10
11
package main

import (
"fmt"
)
func main() {
s := make([]int, 0,2)
fmt.Println(s)
s = append(s, 1, 2, 3)
fmt.Println(s)
}

输出结果如下图,第一个print输出一个空slice,第二个print输出了加入数据1、2、3后的slice

接下来转变成汇编代码

main.go这个文件目录下运行go tool compile来生成汇编代码

1
go tool compile -N -S main.go | grep main.go

在汇编代码中我们可以看到make slice的时候调用了runtime.makeslice这个函数

在append触发扩容的时候调用了runtime.growslice这个函数

makeslice和growslice在go的源码/src/runtime/slice.go中

结构

在源码slice.go中对于slice的定义如下。第一位是一个指针,用来存放数据。第二位len用来保存slice的长度。第三位cap用来保存当前slice的容量

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

我们可以用unsafe.Pointer强制转换代码中的slice类型,输出slice结构体的三个变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import (
"fmt"
"unsafe"
)
func main() {
s := make([]int, 0, 2)
fmt.Println(s)
// 将slice强制转换成unsafe.Pointer类型 (可以当做C的void *)
ptr := unsafe.Pointer(&s)
// 将这个Pointer再强制转为长度为3的数组
opt := (*[3]int)(ptr)
// 通过数组访问输出slice结构体的三个变量
fmt.Printf("%x %d %d\n", opt[0], opt[1], opt[2])
s = append(s, 1, 2, 3)
fmt.Println(s)
ptr = unsafe.Pointer(&s)
opt = (*[3]int)(ptr)
fmt.Printf("%x %d %d\n", opt[0], opt[1], opt[2])
}

输出结果

初始化

unsafe.Pointeruintptr的区别

  • unsafe.Pointer只是单纯的一种指针类型,用来转换成不同类型的指针(和C的Void *指针比较类似),它不能参与指针运算

  • uintptr是用于指针运算的,GC 不把 uintptr 当指针,也就是说 uintptr 无法持有对象, uintptr 类型的目标会被回收

  • unsafe.Pointer 可以和 普通指针 进行相互转换

  • unsafe.Pointer 可以和 uintptr 进行相互转换。

在slice.go中找到makeslice函数

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
func makeslice(et *_type, len, cap int) unsafe.Pointer {
// 根据类型的占用大小和容量cap大小计算slice所需要的内存大小
mem, overflow := math.MulUintptr(et.size, uintptr(cap))
if overflow || mem > maxAlloc || len < 0 || len > cap {
// '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
// 当前已经是会报错容量的问题,但还是要先看slice的长度是否溢出
// 根据类型的占用大小和长度len大小计算slice所需要的内存大小
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
// 报出slice的长度len超出范围
panicmakeslicelen()
}
// len没有问题,就报出slice的容量cap超出范围
panicmakeslicecap()
}
// mallocgc申请内存
return mallocgc(mem, et, true)
}

// math.MulUintptr
// 返回值是类型占用大小和长度或者容量的乘积 以及是否溢出的flag
func MulUintptr(a, b uintptr) (uintptr, bool) {
if a|b < 1<<(4*sys.PtrSize) || a == 0 {
return a * b, false
}
overflow := b > MaxUintptr/a
return a * b, overflow
}

maxAlloc是多少?找到maxAlloc定义的地方,在malloc.go中,三行代码确定了值

1
2
3
4
5
_64bit = 1 << (^uintptr(0) >> 63) / 2

heapAddrBits = (_64bit*(1-sys.GoarchWasm)*(1-sys.GoosIos*sys.GoarchArm64))*48 + (1-_64bit+sys.GoarchWasm)*(32-(sys.GoarchMips+sys.GoarchMipsle)) + 33*sys.GoosIos*sys.GoarchArm64

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

这里有个^uintptr(0)吸引到了我,输出看了下。

1
2
fmt.Println(uintptr(0)) // 0
fmt.Println(^uintptr(0)) // 18446744073709551615

首先^是按位异或的意思,uintptr(0)创建了一个空的uintptr类型。查看uintptr的本质后看到他的描述是an integer type that is large enough to hold the bit pattern of any pointer,也就是他为了能够成功转换成任意类型,其类型实际上和uint64是对等的。查阅了一些资料后,看到了这样一段代码。

1
2
3
4
5
#ifdef _64BIT
typedef uint64 uintptr;
#else
typedef uint32 uintptr;
#endif

uintptr的类型根据系统是32位还是64位进行变换。

所以在32位系统下uintptr 为 uint32 类型,占用大小为 4 个字节,在64位系统下uintptr 为 uint64 类型,占用大小为 8 个字节。

那对^uintptr(0)实际上就是对一串全为0的长度为64的bytes进行按位异或,得到全为1的长度为64的bytes。也就是64位系统支持的最大值,与math.MaxUint64和2的64次方-1相等

_64bit就可以简单计算出为1

再是heapAddrBits在这个里面引用了sys中一堆东西,怼进去看了全是常量0,我估计是对系统结构上的区分,在源码的注释中有这样一段

1
On most 64-bit platforms, we limit this to 48 bits based on a combination of hardware and OS limitations.

也就是说heapAddrBits这个值在大多数的64位操作系统上,Go限制在了48

因此maxAlloc在大多数的64位系统上允许用户分配的最大虚拟内存空间就是48bits

添加 append

在slice.go中找到growslice函数

流程就是先根据容量规则计算出新的容量大小,再以切片类型来分情况加速计算上述新容量所需要申请的内存大小,申请内存,将老slice.array数据部分移动到新申请的空间中,返回新的slice,更新了slice的array,len,cap变量。

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
122
123
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 cap < old.cap {
panic(errorString("growslice: cap out of range"))
}
// 不允许类型为nil
if et.size == 0 {
// 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}
}
// 计算扩容后的新容量
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
// 扩容有个规则
// 如果老的容量小于1024 新扩容就是原来扩容的2倍
// 如果大于1024 新扩容就是原来的1.25倍
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
}
}
}

// 获取需要申请的内存大小。
// 为了加速计算(少用除法,乘法)
// 对于不同的slice元素大小,选择不同的计算方法
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)
}

// The check of overflow in addition to capmem > maxAlloc is needed
// to prevent an overflow which can be used to trigger a segfault
// on 32bit architectures with this example program:
//
// type T [1<<27 + 1]int64
//
// var d T
// var s []T
//
// func main() {
// s = append(s, d, d, d, d)
// print(len(s), "\n")
// }
if overflow || capmem > maxAlloc {
panic(errorString("growslice: cap out of range"))
}
// 根据上面需求的内存大小申请内存空间
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in old.array since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
}
}
// 将老的slice中array变量的内容移动到新的指针中
memmove(p, old.array, lenmem)
// 返回新的slice
return slice{p, old.len, newcap}
}

当然memmove是非常消耗时间的,go不可能每次append都来调用一次growslice

下面的代码可以很好的说明

1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"

func main() {
s := make([]int, 0, 2)
for i := 0; i < 20; i++ {
s = append(s,1)
fmt.Println(&s[0])
}
}

输出如下,我们现在知道slice容量小于1024的时候容量都是翻倍,最开始slice的容量为2,后面的翻倍就是2->4->8->16。代码控制了4次扩容,只看前三次。可以看到地址是有改变的,但并不是每次都改变,也就是当我们程序需要扩容的时候才会调用growslice去申请新的空间并移动数据。

拷贝

先看这段代码,有关slice的截取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main

import "fmt"

func main() {
s := make([]int, 0, 3)
a := s[:2]
fmt.Println( "a:",a)
for i := 0; i < 20; i++ {
s = append(s,i)
}
fmt.Println( "s:",s)
fmt.Println( "a:",a)
}

和之前一样,创建一个容量为2的slice,现在有个变量a,截取了slice前两个。

第一次输出在slice append之前,a的两个值都是0。当给slice添加内容后,再次输出,a的两个值变成了s的前两个值。

有了对append的growslice的了解,可以知道当前s和a的内存地址并不是同一个,s这个slice已经经过了几次扩容,地址已经改变,所以我们现在对a这个slice进行append,结果当然是不会影响到原始的s slice。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package main

import "fmt"

func main() {
s := make([]int, 0, 3)
a := s[:2]
fmt.Println( "a:",a)
for i := 0; i < 20; i++ {
s = append(s,i)
}
fmt.Println( "s:",s)
fmt.Println( "a:",a)
a = append(a, 21,22,23)
fmt.Println( "s:",s)
fmt.Println( "a:",a)
}

但是当s容量很大没有触发扩容的时候,比如说在make slice的时候将扩容设置成30,也就是s在append的时候不会触发扩容,那么此时a的地址和s的地址都是同一个,此时再改变对a进行append,就会影响到s这个slice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package main

import "fmt"

func main() {
s := make([]int, 0, 30)
a := s[:2]
fmt.Println( "a:",a)
for i := 0; i < 20; i++ {
s = append(s,i)
}
fmt.Println( "s:",s)
fmt.Println( "a:",a)
a = append(a, 21,22,23)
fmt.Println( "s:",s)
fmt.Println( "a:",a)
}




======================
全 文 结 束    感 谢 阅 读
======================