前言
今天来说个简单的,也不简单的东西,那就是切片。slice对于golang来说那真的是一个非常常用的东西了,很多地方都会用到它,今天就来说说,slice底层是如何实现的,又有哪些坑是需要提前注意的。
slice结构
很多第一次接触golang的同学都会认为,数组和切片是差不多的东西,其实不是的,切片是数组的封装。
type slice struct {
array unsafe.Pointer
len int
cap int
}
上面这个就是slice的结构,顺便说一下:slice的源码位置是:
go/src/runtime/slice.go
- 其中array是一个指针,指向底层的数组
- len代表slice的长度
- cap代表slice的容量
为什么会有长度和容量这个区分呢,这两个东西是用来干什么的呢?我们往下看。
slice的长度和容量
我们先来看一个最简单的案例
sli := make([]int, 2)
fmt.Printf("len=%d cap=%d\n", len(sli), cap(sli))
sli = append(sli, 1)
fmt.Printf("len=%d cap=%d\n", len(sli), cap(sli))
我们创建一个长度为2的slice然后打印一下它的len和cap。
然后添加一个元素,再次打印最后结果为:
len=2 cap=2
len=3 cap=4
从中我们可以知道len和cap是不同的东西,明显嘛。但是为什么呢?
其实原因很简单,因为数组在创建的时候只能创建固定大小的数组,而当slice在不断往其中添加元素的时候,势必会遇到大小不够的情况,如果每次添加都不够,那么每次都要创建新的数组,那会相当浪费时间和资源,所以当不够的时候索性一次就创建大一些,所以cap其实就代表了整体的一个容量,而len代表当前用到了第几个。
slice的扩容
刚才提到的整个过程就是扩容的原因,那么slice究竟是如何进行扩容的呢?
网上我看见过两个说法:
- 每次2倍
- 当len<1024的时候每次2倍,当len>1024的时候每次1.25倍
我最后得到的结论是其实两个都不完全正确。正确的应该看看源码中是怎么说的。
func growslice(et *_type, old slice, cap int) slice {
.....
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 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
}
}
}
var overflow bool
var lenmem, newlenmem, capmem uintptr
const ptrSize = unsafe.Sizeof((*byte)(nil))
switch et.size {
case 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > _MaxMem
newcap = int(capmem)
case ptrSize:
lenmem = uintptr(old.len) * ptrSize
newlenmem = uintptr(cap) * ptrSize
capmem = roundupsize(uintptr(newcap) * ptrSize)
overflow = uintptr(newcap) > _MaxMem/ptrSize
newcap = int(capmem / ptrSize)
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)
}
......
return slice{p, old.len, newcap}
}
我们省略其中部分代码看关键部分,首先说明一下growslice这个方法是扩容的方法,其中的入参
et *_type, old slice, cap int
分别是元素的类型,老的slice,新slice要求的最小容量
针对最后这个参数举个简单的例子,当前如果是len=2,cap=2的一个slice添加一个元素,那么这个参数传入的就是3,因为最小需要容量为3。
其实从前半部分来看,第二种说法是正确的,当len<1024确实就是两倍,而当len>1024的时候,每次以原来的25%增加直到满足要求。
但是其实你看后面部分,有一个roundupsize的方法,并且又对newcap进行赋值,所以肯定修改了cap的值,所以其实扩容并没有描述的那么简单,实际中会进行内存对齐
,具体什么事内存对齐呢?简单的描述是,内存中肯定不是你想怎么放就怎么放的肯定要满足一个规则,有的地方虽然你只要这么点地方,但是由于美观的要求,会多给你一点,凑个整,保持统一整齐,这就是内存对齐。(是不是花里胡哨的,我尽可能已经白话了,具体还是要看https://blog.csdn.net/u011957758/article/details/85059117)
总之,我们知道,slice的扩容并不是那么简单的。最后附上一个例子作为验证:
func main() {
sli := make([]int, 2)
preCap := cap(sli)
for i := 0; i <= 2048; i++ {
sli = append(sli, i)
if cap(sli) != preCap {
fmt.Printf("len=%4d \t cap=%d\n", len(sli)-1, cap(sli))
preCap = cap(sli)
}
}
}
输出
len= 2 cap=4
len= 4 cap=8
len= 8 cap=16
len= 16 cap=32
len= 32 cap=64
len= 64 cap=128
len= 128 cap=256
len= 256 cap=512
len= 512 cap=1024
len=1024 cap=1280
len=1280 cap=1696
len=1696 cap=2304
1280 = 1024 * 1.25
1696 = 1280 * 1.325
slice的操作
普通的创建添加元素我就不多说了,你肯定知道,你要是不知道就不会来看我的博客了。说一些看起来高端的微操。
创建slice
make([]int, 10, 32)
make的时候可以指定第三个参数也就是初始的cap
slice删除一个元素
sli = append(sli[:3], sli[4:]...)
因为底层是数组,所以删除一个元素看起来会比较麻烦
reslice
func main() {
sli := make([]int, 0)
for i := 1; i <= 10; i++ {
sli = append(sli, i)
}
fmt.Println(sli)
sli = sli[1:3:5]
fmt.Println(sli)
fmt.Println(len(sli), cap(sli))
}
sli = sli[1:3:5]
reslice的时候也可以指定cap,但是注意的是,这个时候并不是指定的整体容量为5,而是容量为原来slice下标为5的地方。
如果原来是[1 2 3 4 5 6 7 8 9 10]
按照上面的操作,按照我自己的平常说的就是切两刀,第一刀是切到3,第二刀是切到5
slice是[2,3],但是实际底层还有[4,5] cap应该是4,所以输出应该是:
[1 2 3 4 5 6 7 8 9 10]
[2 3]
2 4
slice的坑点
slice的坑其实主要在于使用者需要清楚值传递引用传递的关系。
首先在golang中只有值传递,没有引用传递。
- reslice的时候要注意,如果只是reslice那么后续操作是会对原来的slice造成影响的。
- 但是如果经过append之后,那么由于扩容的时候回重新分配内存,如果涉及扩容之后,那么就不会对原来的slice造成影响。
- 如果作为函数的参数传递的是数组,因为是值传递,所以函数内部的修改不会对外部的变量产生影响,但是如果是slice传递,那么因为传递的是指针,所以会修改外部的变量。
- 同时因为是值传递,形参的重新赋值是不会对外部的变量造成影响的。
下面的代码说明了以上可能出现的坑点
package main
import "fmt"
func main() {
a := [3]int{1, 1, 1}
s := []int{1, 1, 1}
modifyArray(a)
fmt.Println(a)
modifySlice(s)
fmt.Println(s)
reslice(s)
fmt.Println(s)
s1 := make([]int, 2, 3)
s2 := append(s1, 1)
s2[0] = 3
fmt.Println(s1)
s3 := append(s1, 1, 1)
s3[0] = 4
fmt.Println(s1)
}
func modifyArray(a [3]int) {
a[0] = 2
}
func modifySlice(s []int) {
s[0] = 2
}
func reslice(s []int) {
s = s[:2]
}
总结
总结一下,创建slice的时候如果可以的话尽可能初始化好要用容量,以免经常扩容。slice作为参数进行传递的时候,还有slice进行append的时候注意一下,别的应该没有问题。总的来说slice的实现还是比较简单的。