0%

《Golang》Slice 原理

血案

先看一个血案:

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

import (
"fmt"
)

func main() {
a := make([]int, 1, 10)
a[0] = 0

b := a[:] // 做了什么?深拷贝还是浅拷贝?
//b = append(b, 2)
b[0] = 1 // a会被改变吗?

fmt.Println(a)
}

代码中备注的问题你能回答上几个?下面通过源码分析来做解答

源码浅析

首先看看 slice 的底层结构

1
2
3
4
5
type slice struct {
array unsafe.Pointer // 指向底层数组的指针
len int // slice的大小
cap int // slice的容量
}

slice 的 make 会被编译器翻译成 makeslice 或者 makeslice64 方法,下面看看他们做了什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func makeslice(et *_type, len, cap int) unsafe.Pointer {  // make([]int) 会被翻译成这个函数
mem, overflow := math.MulUintptr(et.size, uintptr(cap)) // 判断容量是否太大导致地址溢出
if overflow || mem > maxAlloc || len < 0 || len > cap { // 如果溢出或者需要的内存大于最大能分配内存或大小<0或者大小比容量还大,则panic
// 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) // 从堆中分配底层数组,返回指向数组开始位置的指针
}

如果 append 前,slice 已经初始化,则 append 会被翻译成两个步骤

  1. slice 的大小加上 append 的元素的个数与 slice 的容量做比较
  2. 如果 slice 的大小加上 1 <= 容量,则直接修改底层数组就 ok,如果大于的话就会跳转到 runtime.growslice 方法执行,执行完后再修改底层数组

如果 append 前,slice 没有初始化,则翻译成:

  1. 初始化 slice ,大小设置为 0 ,容量设置为 1
  2. 然后调用 runtime.growslice 方法

下面看看 runtime.growslice 方法

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
func growslice(et *_type, old slice, cap int) slice {  // 当 append 发现需要扩容时会调用这个方法。cap 是指 slice 的大小加 append 的元素的个数后的值,表示大小至少要这么多
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 { // 虽然 append 有判断,但这里 double check
panic(errorString("growslice: cap out of range"))
}

if et.size == 0 { // 如果元素类型的大小是 0 ,则返回一个 slice ,它的底层数组指针指向一个 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 { // 如果需要的大于两倍的原来容量,则新容量选择需要的容量。意味着 append 后所有容量都将被占用,大小等于容量,如果这个 slice 频繁的 append ,则会一直扩容,降低性能
newcap = cap
} else { // 如果两倍的后足够存放数据了
if old.len < 1024 { // 如果 append 前的元素个数小于 1024,则新容量就设置为双倍
newcap = doublecap
} else { // 如果原来的元素个数比 1024 还大,则不采用翻倍,而是 0.25 被增长,直到足够。这种做法不至于浪费内存,但是如果这个 slice 频繁的 append,则会一直扩容,降低性能
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap { // 从老容量开始 0.25 倍增长,直到新容量大于需要的容量
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
// 新容量选定后,开始扩容
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: // 如果元素类型占用大小为 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 // 得到 append 前所有数据占用的空间大小
newlenmem = uintptr(cap) * sys.PtrSize // 得到 append 后所有数据占用的空间大小
capmem = roundupsize(uintptr(newcap) * sys.PtrSize) // 得到新容量占用的空间大小。如果不是 8kb 的倍数,则向上取,16kb、24kb、32kb
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 { // 如果元素是指针类型,就需要扫描标记,mallocgc的参数不一样
// 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)
}
}
memmove(p, old.array, lenmem) // 将原slice中的数据直接copy到新空间

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

血案分析

先将上面的案例编译成汇编看看:

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
main.go:7             0x109cf60               65488b0c2530000000              MOVQ GS:0x30, CX                        
main.go:7 0x109cf69 488d4424e0 LEAQ -0x20(SP), AX
main.go:7 0x109cf6e 483b4110 CMPQ 0x10(CX), AX
main.go:7 0x109cf72 0f863a010000 JBE 0x109d0b2
main.go:7 0x109cf78 4881eca0000000 SUBQ $0xa0, SP
main.go:7 0x109cf7f 4889ac2498000000 MOVQ BP, 0x98(SP)
main.go:7 0x109cf87 488dac2498000000 LEAQ 0x98(SP), BP
main.go:8 0x109cf8f 488d05aadb0000 LEAQ type.*+55936(SB), AX // 这里开始make a slice
main.go:8 0x109cf96 48890424 MOVQ AX, 0(SP)
main.go:8 0x109cf9a 48c744240801000000 MOVQ $0x1, 0x8(SP)
main.go:8 0x109cfa3 48c74424100a000000 MOVQ $0xa, 0x10(SP)
main.go:8 0x109cfac e84f64faff CALL runtime.makeslice(SB)
main.go:8 0x109cfb1 488b442418 MOVQ 0x18(SP), AX // makeslice的返回值保存到AX,就是指向底层数组的指针
main.go:8 0x109cfb6 4889442468 MOVQ AX, 0x68(SP) // 底层数组指针存到栈帧68的位置
main.go:8 0x109cfbb 48c744247001000000 MOVQ $0x1, 0x70(SP) // slice大小放到栈帧70的位置
main.go:8 0x109cfc4 48c74424780a000000 MOVQ $0xa, 0x78(SP) // slice容量放到栈帧78的位置
main.go:9 0x109cfcd eb00 JMP 0x109cfcf
main.go:9 0x109cfcf 48c70000000000 MOVQ $0x0, 0(AX) // AX里面存的还是指向底层数组的指针,这里就讲0数字存入数组第一个位置
main.go:11 0x109cfd6 488b542468 MOVQ 0x68(SP), DX // a的数组指针放到DX
main.go:11 0x109cfdb 488b4c2470 MOVQ 0x70(SP), CX // a的大小放到CX
main.go:11 0x109cfe0 488b5c2478 MOVQ 0x78(SP), BX // a的容量放到BX
main.go:11 0x109cfe5 4889542450 MOVQ DX, 0x50(SP) // a的数组指针放入栈帧50的位置,就是一个复制
main.go:11 0x109cfea 48894c2458 MOVQ CX, 0x58(SP) // a的大小放入栈帧58位置
main.go:11 0x109cfef 48895c2460 MOVQ BX, 0x60(SP) // a的容量放入栈帧60位置。到这里就完成了a slice的复制,但还是指向同一个底层数组
main.go:13 0x109cff4 4885c9 TESTQ CX, CX
main.go:13 0x109cff7 7705 JA 0x109cffe
main.go:13 0x109cff9 e9ac000000 JMP 0x109d0aa
main.go:13 0x109cffe 48c70201000000 MOVQ $0x1, 0(DX) // 1存入底层数组0的位置。很明显a和b都受影响了
main.go:15 0x109d005 488b442478 MOVQ 0x78(SP), AX // 下面都是fmt.Println,不做分析了
main.go:15 0x109d00a 488b4c2468 MOVQ 0x68(SP), CX
main.go:15 0x109d00f 488b542470 MOVQ 0x70(SP), DX
main.go:15 0x109d014 48890c24 MOVQ CX, 0(SP)
main.go:15 0x109d018 4889542408 MOVQ DX, 0x8(SP)
main.go:15 0x109d01d 4889442410 MOVQ AX, 0x10(SP)
main.go:15 0x109d022 e8e9c0f6ff CALL runtime.convTslice(SB)
main.go:15 0x109d027 488b442418 MOVQ 0x18(SP), AX
main.go:15 0x109d02c 4889442438 MOVQ AX, 0x38(SP)
main.go:15 0x109d031 0f57c0 XORPS X0, X0
main.go:15 0x109d034 0f11442440 MOVUPS X0, 0x40(SP)
main.go:15 0x109d039 488d442440 LEAQ 0x40(SP), AX
main.go:15 0x109d03e 4889442430 MOVQ AX, 0x30(SP)
main.go:15 0x109d043 8400 TESTB AL, 0(AX)

从上面源码浅析和汇编代码的分析后就可以回答问题了

b := a[:] 做了什么?

复制了 slice,但是仅仅是复制了 slice struct 中的 3 个成员,底层数组不会复制。其实跟 b := a 一毛一样的效果

那如果想做深拷贝呢,怎么做?有两种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func main() {
a := make([]int, 1, 10)
a[0] = 1

b := make([]int, len(a)) // 第一种方法是使用copy,这里底层数组大小一定要是a底层数组的大小,否则runtime.memmove是复制不过去的
copy(b, a[:])
fmt.Println(b)

c := append(make([]int,0), a[:]...) // 第二种办法是append到一个新slice
fmt.Println(c)

a[0] = 2
fmt.Println(b, c)
}

有兴趣的同学可以 benchmark 一下这两种方式,看看哪个性能好一些

看看下面我的测试情况

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
func Benchmark_Copy(b *testing.B) {
a := make([]int, 5, 10)
a[0] = 1

b.ResetTimer()
for i := 0; i < b.N; i++ {
b := make([]int, 5)
copy(b, a[:])
}
b.StopTimer()
// Benchmark_Copy-8 1000000000 0.323 ns/op
}

func Benchmark_Append(b *testing.B) {
a := make([]int, 5, 10)
a[0] = 1
var c []int

b.ResetTimer()
for i := 0; i < b.N; i++ {
c = append(make([]int,0,5), a[:]...)
}
b.StopTimer()

fmt.Println(c)
// Benchmark_Append-8 36875870 32.1 ns/op
}

可以看出 copy 的方式比 append 性能好上一百多倍

因为 copy 被编译器翻译成 runtime.memmove,直接是内存拷贝,而 append 却有一些多余的判断,甚至还会扩容

所以深拷贝还是建议直接用 copy 的方式

a 会被改变吗?

a 会被改变,因为改变 b 就改变了底层数组的值,而 a 也指向了那个底层数组

但如果是下面情况:

1
2
3
4
5
6
7
8
9
10
func main() {
a := make([]int, 1, 1)
a[0] = 0

b := a[:] // 做了什么?深拷贝还是浅拷贝?
b = append(b, 2)
b[0] = 1 // a会被改变吗?跟a的容量是否有关系?

fmt.Println(a)
}

a 就不会被改变,因为 b 复制了 a 后,b 的容量也是 1,append 发现容量不够,就会扩容

而扩容是新开辟一个内存,原有数据 copy 过去,导致 b 的 slice 结构中的 array 字段指向了新的底层数组

而 a 的 slice 中的 array 字段没有变动,指向的还是原来的数组,所以对 b 的底层数组的改动不会影响 a 了

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
package main

import (
"fmt"
)

func main() {
a := make([]int, 2, 2)
a[0] = 12
a[1] = 100

b := &a
c := a

fmt.Printf("&a: %p\n", &a) // a slice的栈中地址
fmt.Printf("b: %p\n", b) // a slice的栈中地址
fmt.Printf("&b: %p\n", &b) // b变量的栈中地址

fmt.Printf("a: %p\n", a) // a slice堆中的底层数组地址
fmt.Printf("c: %p\n", c) // c slice堆中的底层数组地址
fmt.Printf("&a[0]: %p\n", &a[0]) // a的底层数组第一个元素的地址

p := go_reflect.Reflect.MustToUint64(fmt.Sprintf("%p", a))
po := unsafe.Pointer(uintptr(unsafe.Pointer(uintptr(p))) + 8)
fmt.Println(*(*int)(po)) // 输出100。底层数组第二个元素
}

下面是输出结果:

1
2
3
4
5
6
&a: 0xc0000a6020
b: 0xc0000a6020
&b: 0xc0000ae018
a: 0xc0000b4010
c: 0xc0000b4010
&a[0]: 0xc0000b4010

可以看出 Slice 虽然不是指针类型,但是却很像指针类型,slice 本身就被编译器视为了指向底层数组的地址,而普通的 struct 是无法直接输出地址的,必须 & 符号取地址

这一点跟 Map 一样

两种初始化方式的比较

1
2
3
4
aa := []int{1}   // 会翻译成runtime.newobject
aaa := make([]int, 1) // 会翻译成runtime.makeslice
aaa[0] = 1
fmt.Println(aa, aaa)

看看他两的性能测试:

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
package main

import (
"fmt"
"testing"
)

func Benchmark_Make(b *testing.B) {
var test []int
b.ResetTimer()
for i := 0; i < b.N; i++ {
test = make([]int, 0, 4)
test = append(test, 1, 2, 3, 4)
}
b.StopTimer()
// Benchmark_Make-8 38368233 28.7 ns/op
}

func Benchmark_Direct(b *testing.B) {
var test []int

b.ResetTimer()
for i := 0; i < b.N; i++ {
test = []int{}
test = append(test, 1, 2, 3, 4)
}
b.StopTimer()

fmt.Println(test)
// Benchmark_Direct-8 30331087 36.9 ns/op
}

可以看出 make 的方式性能好一些

因为上面测试例子中,make 时指定了足够的容量,slice 不会扩容,而 []int{} 时无法设置容量,其容量就是数组大小,都是 0,append 时发生扩容,导致性能下降

[]int{1,2} 的初始化方式,底层数组分配在栈中

总结

  1. slice 是值类型,参数传递时发生拷贝,但拷贝的仅仅是 struct 结构体,底层数组不拷贝,看起来是一个指针类型。
  2. b := a[1:3],b 的指针将指向底层数组的第二个元素,大小变成 2,容量将变成 a 的容量 -1。不会进行底层数组拷贝
  3. append 的时候会判断 slice 容量够不够存这些新增的数据,如果不够则会扩容
  4. 扩容时如果发现需要的容量比原来容量两倍还大,则扩容到需要的容量。如果比原来容量两倍小,则判断原来的元素个数如果不足 1024,则扩容一倍,如果原来的元素个数大于了 1024,则在原来的容量基础上 0.25 倍增长直到大于需要的容量
  5. copy 与 append 两种深拷贝方式,copy 性能更好,建议使用 copy
  6. slice 结构体放在栈中,底层数组在堆中
  7. 与 Map 还有 Channel 一样,Slice 本身就被编译器视为地址。但指向底层数组第一个元素,而不是结构体第一个字段。可以解释为:slice、map、channel 都被视为指针,都是指向堆中数据开始位置。
  8. make 和 []int{} 的初始化方式,推荐使用 make 并限定容量
  9. []int{1,2} 的初始化方式,底层数组 [1,2] 分配在栈中



微信关注我,及时接收最新技术文章