本文从源码角度学习 golang slice 的创建、删除、扩容，深拷贝和slice的源码实现。
golang 中的 slice 非常强大，让数组操作非常方便高效。在开发中不定长度表示的数组全部都是 slice 。但是很多同学对 slice 的模糊认识，造成认为golang中的数组是引用类型，结果就是在实际开发中碰到很多坑，以至于出现一些莫名奇妙的问题，数组中的数据丢失了。
slice的用法
定义slice的几种方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
//声明一个slice,值是nil
var s []int
//静态显式初始化 初始化成一个大小为0的slice.
//此时变量(s == nil)已经不成立了，但是s的大小len(s)还是等于0
//实际上 []string{} == make([]string, 0)。
s := []int{}
//通过make初始化
//第一个是数据类型，第二个是 len ，第三个是 cap 。如果不穿入第三个参数，则 cap=len
s := make([]int,0,3)
//切片生成
var data [10]int
slice := data[2:8]
//append 生成 ，建议append生成的时候预先make指定长度，性能会好上很多
slice := make([]int,0,1000)
slice = append(slice,6)
//第二种append生成方式 性能最优
s := make([]int,1000) //len=1000,cap=1000
for j:=0;j<1000;j++ {
s[j] = j
}
|
1.当cap < 1024 的时候 slice 每次扩容 * 2
2.当cap >= 1024 的时候， slice每次扩容 * 1.25
3.预先分配内存可以提升性能
4.直接用index赋值而非append可以更进一步提升性能
slice 定义的时候是没有长度的，slice的长度是动态可变的，有点类似java语言中的动态数组。
其他优化：bounds checking elimination
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
package bechmark
import (
"testing"
)
var (
// 原始slice
origin = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
// 需要删除的元素
targetEle = 6
)
// 第一种
func BenchmarkMake(t *testing.B) {
t.ResetTimer()
for i := 0; i < t.N; i++ {
target := make([]int, 0, len(origin))
for _, item := range origin {
if item != targetEle {
target = append(target, item)
}
}
}
}
// 第二种
func BenchmarkReuse(t *testing.B) {
t.ResetTimer()
for i := 0; i < t.N; i++ {
target := origin[:0]
for _, item := range origin {
if item != targetEle {
target = append(target, item)
}
}
}
}
// 第三种
func BenchmarkEditOne(t *testing.B) {
t.ResetTimer()
for i := 0; i < t.N; i++ {
for i := 0; i < len(origin); i++ {
if origin[i] == targetEle {
origin = append(origin[:i], origin[i+1:]...)
i-- // maintain the correct index
}
}
}
}
-----------------------
☁ bechmark go test -v -bench=. -benchtime=3s -benchmem
goos: darwin
goarch: amd64
pkg: test/bechmark
BenchmarkMake-4 95345845 35.8 ns/op 80 B/op 1 allocs/op
BenchmarkReuse-4 255912920 14.4 ns/op 0 B/op 0 allocs/op
BenchmarkEditOne-4 473434452 7.56 ns/op 0 B/op 0 allocs/op
PASS
ok test/bechmark 12.915s
|
- 除了第一种方法外，其他方法都对原数据进行了修改；
- 第一种方法适合不污染原slice数据的情况下使用，这种方式也比较简单，大部分学习golang的人也都能想到，不过性能稍差一些，还存在内存分配情况，不过也要看业务需要;
- 第二种方法比较巧妙，创建了一个slice，但是共用原始slice的底层数组；这样就不需要额外分配内存空间，直接在原数据上进行修改。
- 第三种方法也会对底层数组进行修改，思路和前两种正好相反，如果找到需要移除的元素的时候，将其之后的元素前移，覆盖该元素的位置。
slice翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func reverse1(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
func reverse2(s []int) {
for i := 0; i < len(s)/2; i++ {
s[i], s[len(s)-i-1] = s[len(s)-i-1], s[i]
}
}
func main() {
var s []int = []int{1, 2, 3}
reverse1(s)
fmt.Printf("s:%v\n", s)
fmt.Println()
reverse2(s)
fmt.Printf("s:%v\n", s)
}
|
slice传递问题
下面看一段代码：
1
2
3
4
5
6
7
8
9
10
11
12
|
func TestSlice1(t *testing.T) {
var s []int
for i := 0; i < 3; i++ {
s = append(s, i)
}
modifySlice(s)
fmt.Println(s)
}
func modifySlice(s []int) {
s = append(s, 2048)
s[0] = 1024
}
|
聪明的你一眼就能看出来，肯定是打印[1024,1,2,2048]吧，其实不是，运行这段代码后只会打印出 [1024,1,2]。原因就是slice 是按值传递的，这里传递的是s底层的数组的指针。
但是仅仅是共享了slice底层的数组，slice底层的len和cap都是被复制了一份，所以在modifySlice里面的len+1在外层是看不到的。外层的len还是3。
更进一步，如果我们再append一条数据会怎么样呢？
1
2
3
4
5
|
func modifySlice(s []int) {
s = append(s, 2048)
s = append(s, 4096)
s[0] = 1024
}
|
我们可以看到外层打印的slice变成了 [0,1,2]。因为modifySlice函数内的slice底层的数组发生了扩容，变成了另一个扩容后的结构体，但是外层的slice还是引用的老的结构体。
由此我们得出： slice 还有array 都按值传递的 (传递的时候会复制内存)，golang里所有数据都是按值传递的，指针也是值的一种
如果没有发生扩容，修改在原来的底层数组内存中
如果发生了扩容，修改会在新的内存中
最后我们如果换成这种方式，外部打印的slice又会成什么样呢？
1
2
3
4
5
|
func modifySlice(s []int) {
s[0] = 1024
s = append(s, 2048)
s = append(s, 4096)
}
|
答案是 [1024,1,2] 我们一行一行分析：
第一行：slice还是老的底层数组，这时候直接修改0下标，外部内部都生效
第二行：slice还是老的底层数组，这时候添加了一位，modfiySlice函数内的s len+1 但是外部的len还是3 所以不会打印出2048
第三部：modifySlice内部的s底层数组扩容，彻底和外部的slice独立成2个slice。
总结
- 不要轻易的对切片append，如果新的切片容量比旧的大的话，需要进行growslice操作，新的地址开辟，数据拷贝
- 尽量对切片设置初始容量值以避免growslice，类似make([]int,0,100)
- 切片是一个结构体，保存着切片的容量，实际长度以及数组的地址
- 切片作为函数参数传入会进行引用拷贝，生成一个新的切片，指向同一个数组
slice截取
go中的slice是支持截取操作的，虽然使用起来非常的方便，但是有很多坑，稍有不慎就会出现bug且不易排查。
让我们来看一段程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
package main
import "fmt"
func main() {
slice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
s1 := slice[2:5]
s2 := s1[2:7]
fmt.Printf("len=%-4d cap=%-4d slice=%-1v n", len(slice), cap(slice), slice)
fmt.Printf("len=%-4d cap=%-4d s1=%-1v n", len(s1), cap(s1), s1)
fmt.Printf("len=%-4d cap=%-4d s2=%-1v n", len(s2), cap(s2), s2)
}
|
程序输出：
1
2
3
|
len=10 cap=10 slice=[0 1 2 3 4 5 6 7 8 9]
len=3 cap=8 s1=[2 3 4]
len=5 cap=6 s2=[4 5 6 7 8]
|
s1的长度变成3，cap变为8（默认截取到最大容量）， 但是s2截取s1的第2到第7个元素，左闭右开，很多人想问，s1根本没有那么元素啊，但是实际情况是s2截取到了，并且没有发生数组越界，原因就是s2实际截取的是底层数组，目前slice、s1、s2都是共用的同一个底层数组。
我们继续操作：
1
2
|
fmt.Println("--------append 100----------------")
s2 = append(s2, 100)
|
输出结果是：
1
2
3
4
|
--------append 100----------------
len=10 cap=10 slice=[0 1 2 3 4 5 6 7 8 100]
len=3 cap=8 s1=[2 3 4]
len=6 cap=6 s2=[4 5 6 7 8 100]
|
我们看到往s2里append数据影响到了slice，正是因为两者底层数组是一样的；但是既然都是共用的同一底层数组，s1为什么没有100，因为s1的len是3所以不会有100。我们继续进行操作：
1
2
|
fmt.Println("--------append 200----------------")
s2 = append(s2, 200)
|
输出结果是：
1
2
3
4
|
--------append 200----------------
len=10 cap=10 slice=[0 1 2 3 4 5 6 7 8 100]
len=3 cap=8 s1=[2 3 4]
len=7 cap=12 s2=[4 5 6 7 8 100 200]
|
我们看到继续往s2中append一个200，但是只有s2发生了变化，slice并未改变，为什么呢？对，是因为在append完100后，s2的容量已满，再往s2中append，底层数组发生复制，系统分配了一块新的内存地址给s2，s2的容量也翻倍了。
我们继续操作：
1
2
|
fmt.Println("--------modify s1----------------")
s1[2] = 20
|
输出会是什么样呢？
1
2
3
4
|
--------modify s1----------------
len=10 cap=10 slice=[0 1 2 3 20 5 6 7 8 100]
len=3 cap=8 s1=[2 3 20]
len=7 cap=12 s2=[4 5 6 7 8 100 200]
|
这就很容易理解了，我们对s1进行更新，影响了slice，因为两者共用的还是同一底层数组，s2未发生改变是因为在上一步时底层数组已经发生了变化；
以此来看，slice截取的坑确实很多，极容易出现bug，并且难以排查，大家在使用的时候一定注意。
slice源码分析
slice 数据结构
这个是 slice 的数据结构，它很简单，一个指向真实 array 地址的指针 ptr ，slice 的长度 len 和容量 cap 。
1
2
3
4
5
|
type slice struct {
array unsafe.Pointer //底层数组
len int //长度
cap int //容量
}
|
Slice 的底层数据结构共分为三部分，如下：
- array：指向所引用的数组指针（ unsafe.Pointer 可以表示任何可寻址的值的指针）
- len：长度，当前引用切片的元素个数,len总是小于等于cap
- cap：容量，当前引用切片的容量（底层数组的元素总数）
其中 len 和 cap 就是我们在调用 len(slice) 和 cap(slice) 返回的值。
slice 创建源码
我们可以看下创建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
|
// maxSliceCap returns the maximum capacity for a slice.
func maxSliceCap(elemsize uintptr) uintptr {
if elemsize < uintptr(len(maxElems)) {
return maxElems[elemsize]
}
return _MaxMem / elemsize
}
func makeslice(et *_type, len, cap int) slice {
// NOTE: The len > maxElements check here is not strictly necessary,
// but it produces 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 issue 4085.
// 计算最大可分配长度
maxElements := maxSliceCap(et.size)
if len < 0 || uintptr(len) > maxElements {
panic(errorString("makeslice: len out of range"))
}
if cap < len || uintptr(cap) > maxElements {
panic(errorString("makeslice: cap out of range"))
}
// 分配连续区间
p := mallocgc(et.size*uintptr(cap), et, true)
return slice{p, len, cap}
}
|
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
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
|
// 与append(slice,s)对应的函数growslice
// 通过切片的类型，旧切片的容量和数据得出新切片的容量，新切片跟据容量重新申请一块地址，把旧切片的数据拷贝到新切片中
func growslice(et *_type, old slice, cap int) slice {
// 单纯地扩容，不写数据
// 如果存储的类型空间为0， 比如说 []struct{}, 数据为空，长度不为空
if et.size == 0 {
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}
}
// 扩容规则 1.新的容量大于旧的2倍，直接扩容至新的容量
// 2.新的容量不大于旧的2倍，当旧的长度小于1024时，扩容至旧的2倍，否则扩容至旧的5/4倍
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
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))
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)
} }
// 异常情况，旧的容量比
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)
}
}
// 数据拷贝
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap
}
|
slice的拷贝
slice的拷贝也是针对切片提供的接口，是深拷贝，可以通过调用copy()函数将src切片中的值拷贝到dst切片中，通过该函数进行的切片拷贝后，针对dst切片进行的操作不会对src产生任何的影响，其拷贝长度是按照src与dst切片中最小的len长度去计算的，runtime.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, fmPtr unsafe.Pointer, fmLen int, width uintptr) int {
if fmLen == 0 || toLen == 0 {
return 0
}
n := fmLen
if toLen < n {
n = toLen
}
if width == 0 {
return n
}
size := uintptr(n) * width
if size == 1 {
// 如果就1个元素 直接赋值过去就好了
*(*byte)(toPtr) = *(*byte)(fmPtr)
} else {
// 直接进行内存的拷贝，如果slice数据量过大将会影响性能
memmove(toPtr, fmPtr, size)
}
return n
}
|