golang 设计与实现 slice

发表于 | 更新于 | 分类于
字数统计 1.1k | 阅读时长 6

Golang 动态数组 slice。

定义

1
2
3
4
5
type slice struct {
truearray unsafe.Pointer // 数据
truelen   int            // 长度（元素个数）
truecap   int            // 容量
}

创建 slice

采用 mallocgc 分配内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 创建 slice
func makeslice(et *_type, len, cap int) unsafe.Pointer {
truemem, overflow := math.MulUintptr(et.size, uintptr(cap))
trueif overflow || mem > maxAlloc || len < 0 || len > cap {
truetrue// NOTE: Produce a 'len out of range' error instead of a
truetrue// 'cap out of range' error when someone does make([]T, bignumber).
truetrue// 'cap out of range' is true too, but since the cap is only being
truetrue// supplied implicitly, saying len is clearer.
truetrue// See golang.org/issue/4085.
truetruemem, overflow := math.MulUintptr(et.size, uintptr(len))
truetrueif overflow || mem > maxAlloc || len < 0 {
truetruetruepanicmakeslicelen()
truetrue}
truetruepanicmakeslicecap()
true}

truereturn mallocgc(mem, et, true)
}

容量扩容策略

总结：

  1. 新容量 cap 大于旧容量 old.cap 的 2 倍时，直接采用 cap；
  2. 旧容量 old.cap 小于 1024 时，扩容为旧容量 old.cap 的 2 倍；
  3. 旧容量 old.cap 大于等于 1024 时，按照旧容量 old.cap 的 1.25 倍指数幂增长；
  4. 当步骤 3 溢出时，直接采用新容量 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
124
125
126
127
128
129
130
131
132
133
134
135
136
// growslice handles slice growth during append.
// It is passed the slice element type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
// The new slice's length is set to the old slice's length,
// NOT to the new requested capacity.
// This is for codegen convenience. The old slice's length is used immediately
// to calculate where to write new values during an append.
// When the old backend is gone, reconsider this decision.
// The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
//
// slice 在追加数据时使用 growslice 处理容量增长
// 入参：slice 元素类型，旧 slice，期望容量
// 返回：新 slice
func growslice(et *_type, old slice, cap int) slice {
trueif raceenabled {
truetruecallerpc := getcallerpc()
truetrueracereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
true}
trueif msanenabled {
truetruemsanread(old.array, uintptr(old.len*int(et.size)))
true}

trueif cap < old.cap {
truetruepanic(errorString("growslice: cap out of range"))
true}

trueif et.size == 0 {
truetrue// append should not create a slice with nil pointer but non-zero len.
truetrue// We assume that append doesn't need to preserve old.array in this case.
truetruereturn slice{unsafe.Pointer(&zerobase), old.len, cap}
true}

truenewcap := old.cap
truedoublecap := newcap + newcap
true// 期望容量 cap 超过旧容量 2 倍时，直接使用 cap 作为新 slice 的容量
trueif cap > doublecap {
truetruenewcap = cap
true} else {
truetrue// 就容量小于 1024 时，空间按 2 倍增长
truetrueif old.len < 1024 {
truetruetruenewcap = doublecap
truetrue} else {
truetruetrue// Check 0 < newcap to detect overflow
truetruetrue// and prevent an infinite loop.
truetruetrue// 新容量以 (1 + 1 / 4) 倍率增加，直到大于期望容量
truetruetruefor 0 < newcap && newcap < cap {
truetruetruetruenewcap += newcap / 4
truetruetrue}
truetruetrue// Set newcap to the requested cap when
truetruetrue// the newcap calculation overflowed.
truetruetrue// 防止溢出
truetruetrueif newcap <= 0 {
truetruetruetruenewcap = cap
truetruetrue}
truetrue}
true}

truevar overflow bool
truevar lenmem, newlenmem, capmem uintptr
true// Specialize for common values of et.size.
true// For 1 we don't need any division/multiplication.
true// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
true// For powers of 2, use a variable shift.
true// 计算新容量
trueswitch {
truecase et.size == 1:
truetruelenmem = uintptr(old.len)
truetruenewlenmem = uintptr(cap)
truetruecapmem = roundupsize(uintptr(newcap))
truetrueoverflow = uintptr(newcap) > maxAlloc
truetruenewcap = int(capmem)
truecase et.size == sys.PtrSize:
truetruelenmem = uintptr(old.len) * sys.PtrSize
truetruenewlenmem = uintptr(cap) * sys.PtrSize
truetruecapmem = roundupsize(uintptr(newcap) * sys.PtrSize)
truetrueoverflow = uintptr(newcap) > maxAlloc/sys.PtrSize
truetruenewcap = int(capmem / sys.PtrSize)
truecase isPowerOfTwo(et.size):
truetruevar shift uintptr
truetrueif sys.PtrSize == 8 {
truetruetrue// Mask shift for better code generation.
truetruetrueshift = uintptr(sys.Ctz64(uint64(et.size))) & 63
truetrue} else {
truetruetrueshift = uintptr(sys.Ctz32(uint32(et.size))) & 31
truetrue}
truetruelenmem = uintptr(old.len) << shift
truetruenewlenmem = uintptr(cap) << shift
truetruecapmem = roundupsize(uintptr(newcap) << shift)
truetrueoverflow = uintptr(newcap) > (maxAlloc >> shift)
truetruenewcap = int(capmem >> shift)
truedefault:
truetruelenmem = uintptr(old.len) * et.size
truetruenewlenmem = uintptr(cap) * et.size
truetruecapmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
truetruecapmem = roundupsize(capmem)
truetruenewcap = int(capmem / et.size)
true}

true// The check of overflow in addition to capmem > maxAlloc is needed
true// to prevent an overflow which can be used to trigger a segfault
true// on 32bit architectures with this example program:
true//
true// type T [1<<27 + 1]int64
true//
true// var d T
true// var s []T
true//
true// func main() {
true//   s = append(s, d, d, d, d)
true//   print(len(s), "\n")
true// }
trueif overflow || capmem > maxAlloc {
truetruepanic(errorString("growslice: cap out of range"))
true}

truevar p unsafe.Pointer
trueif et.ptrdata == 0 {
truetruep = mallocgc(capmem, nil, false)
truetrue// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
truetrue// Only clear the part that will not be overwritten.
truetruememclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
true} else {
truetrue// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
truetruep = mallocgc(capmem, et, true)
truetrueif lenmem > 0 && writeBarrier.enabled {
truetruetrue// Only shade the pointers in old.array since we know the destination slice p
truetruetrue// only contains nil pointers because it has been cleared during alloc.
truetruetruebulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
truetrue}
true}
true// 复制旧数据
truememmove(p, old.array, lenmem)

truereturn slice{p, old.len, newcap}
}

来源：https://leunggeorge.github.io/

0%