Go语言中的切片是一个特殊的数据结构,和C++的 std::vector
一样(但又不完全一样)。
Slice切片
用户能够操控slice的有以下内建函数
make
创建一个切片
append
向切片中追加数据
copy
复制切片数据到另一个切片
len/cap
获取切片长度/容量
除此之外,还可以用 slice[from:to]
获取新切片。
slice数据结构定义在 runtime/slice.go
中
type slice struct { array unsafe.Pointer len int cap int }
而在 reflect 包中也存在一个 SliceHeader
数据结构,供用户使用
type SliceHeader struct { Data uintptr Len int Cap int }
虽然切片没有提供删除操作,但是可以通过切片 :
完成一些常规的功能。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 func printSlice (slice []int ) { fmt.Println(slice, len (slice), cap (slice)) }func main () { slice := []int {10 , 20 , 30 } slice = append (slice, []int {40 , 50 , 60 }...) printSlice(slice) slice = slice[:len (slice)-1 ] printSlice(slice) slice = slice[1 :] printSlice(slice) slice = append (slice[:2 ], slice[3 :]...) printSlice(slice) }
一般来说从一个数组/切片中获取新的切片通过 a[low : high]
,实际上还有另一种方法获取切片:a[low : high : max]
,必须满足 0 <= low <= high <= max <= cap(a)
。这种情况下返回的新切片 SliceHeader
为:
a := SliceHeader{...} b := SliceHeader{ Data: a.Data+low Len: high-low Cap: max-low }
使用 a[low:high]
获取新切片实际上省略第三个参数,默认 max=cap(a)
:a[low:high:cap(a)]
举个例子:
a := make ([]int , 5 , 10 ) t := a[2 :6 :8 ] t2 := t[1 :3 ] fmt.Println(len (a), cap (a)) fmt.Println(len (t), cap (t)) fmt.Println(len (t2), cap (t2))5 10 4 6 2 5
想要了解更多有关Go的规范说明可以访问官网:https://go.dev/ref/spec#Slice_expressions
makeslice创建切片
一般获得一个切片有以下几种方式
从数组中获取切片。arr := [...]T{...}; slice := arr[:]
声明切片,默认为零值nil。var slice []T
初始化切片,不为nil。slice := []T{}
通过 make
创建具有长度和一定容量的切片。slice := make([]T, len, cap)
第一种方法是从一个数组 中获取一个切片(不会通过 runtime.makeslice
),但是要注意,对切片的修改也会影响到数组,这样创建切片的方式比较少见。
最后三种创建切片的方法最终会通过函数 runtime.makeslice
来创建
func makeslice (et *_type, len , cap int ) unsafe .Pointer { mem, overflow := math.MulUintptr(et.size, uintptr (cap )) if overflow || mem > maxAlloc || len < 0 || len > cap { mem, overflow := math.MulUintptr(et.size, uintptr (len )) if overflow || mem > maxAlloc || len < 0 { panicmakeslicelen() } panicmakeslicecap() } return mallocgc(mem, et, true ) }
上面可以看到 makeslice
创建切片需要的内容空间为 内存空间大小 = 切片中每个元素大小 * 切片容量
。其中 math.MulUintptr
看似是一个导出函数,实际上它是 internal 包中的函数,外部用户无法直接使用。
该函数返回一个 uintptr
指针类型,和一个 bool
用于指示此次操作是否溢出。注意其中的 goarch.PtrSize
表示的是一个指针大小(不同架构平台下指针大小不同,比如32位指针大小4个字节,64位下指针大小8个字节)。
func MulUintptr (a, b uintptr ) (uintptr , bool ) { if a|b < 1 <<(4 *goarch.PtrSize) || a == 0 { return a * b, false } overflow := b > MaxUintptr/a return a * b, overflow }
makeslice
发生的错误可能有以下几种:
溢出错误,也就是 内存空间大小 溢出
申请的内存空间大于最大可分配的大小
即 maxAlloc = (1 << heapAddrBits) - (1-_64bit)*1
长度小于0或者切片长度len小于最大切片容量cap
当没有错误发生后,调用 mallocgc
开始真正的内存分配(数组)并返回 数组起始指针 。
为何需要使用 SliceHeader
而不直接使用 slice
呢?
一般来说 runtime.slice
是go运行时使用的,如果外部也通过该slice结构体操作切片的话,那么将会额外引入不必要的包和多余的函数。因此,Go在反射库中提供了 SliceHeader
给用户使用,作为轻量级的slice结构体,用于访问切片底层数据
注意,上面的 maekslice
函数 仅仅 返回一个底层数据的指针,最后还需要由 makeslice
的调用方将返回的指针、len、cap构建为 SliceHeader
结构。
具体可以从下面的源文件中 src/cmd/compile/internal/typecheck/expr.go
找到相关的信息
func tcSliceHeader (n *ir.SliceHeaderExpr) ir .Node { t := n.Type() ... n.Ptr = Expr(n.Ptr) n.Len = DefaultLit(Expr(n.Len), types.Types[types.TINT]) n.Cap = DefaultLit(Expr(n.Cap), types.Types[types.TINT]) ... return n }
growslice扩容
Go中一般是通过 append
对一个切片进行扩容,下面是append使用例子
slice := make ([]int , 20 ); slice = append (slice, []int {20 ,30 ,40 })
append
追加数据不一定会发生扩容
扩容机制是通过 growslice
完成的,会重新分配内存空间并将旧切片中的数据复制 到新数组中
PS:下面的扩容切片函数Go1.18版本的,和之前的版本有一点差别
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 func growslice (et *_type, old slice, cap int ) slice { if cap < old.cap { panic (errorString("growslice: cap out of range" )) } if et.size == 0 { return slice{unsafe.Pointer(&zerobase), old.len , cap } } newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 if old.cap < threshold { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += (newcap + 3 *threshold) / 4 } if newcap <= 0 { newcap = cap } } } var overflow bool var lenmem, newlenmem, capmem uintptr switch { case et.size == 1 : ... case et.size == goarch.PtrSize: lenmem = uintptr (oldLen) * goarch.PtrSize newlenmem = uintptr (newLen) * goarch.PtrSize capmem = roundupsize(uintptr (newcap) * goarch.PtrSize) overflow = uintptr (newcap) > maxAlloc/goarch.PtrSize newcap = int (capmem / goarch.PtrSize) case isPowerOfTwo(et.size): ... default : ... } var p unsafe.Pointer if et.ptrdata == 0 { p = mallocgc(capmem, nil , false ) memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { p = mallocgc(capmem, et, true ) ... } memmove(p, old.array, lenmem) return slice{p, old.len , newcap} }
注意上面的 zerobase
,是runtime包下的未导出全局变量: var zerobase uintptr
。
那么这种情况什么时候发生呢?当切片的元素为 struct{}
空结构体或者切片为空 时就会进入该逻辑。
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 type space struct {}func main () { slice1 := []space{space{}, space{}} slice2 := []space{} slice3 := []int {} slice4 := []int {10 } fmt.Println(slice1, len (slice1), cap (slice1)) fmt.Println(slice2, len (slice2), cap (slice2)) fmt.Println(slice3, len (slice3), cap (slice3)) fmt.Println(slice4, len (slice4), cap (slice4)) fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice1)).Data) fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice2)).Data) fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice3)).Data) fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice4)).Data) } [{} {}] 2 2 [] 0 0 [] 0 0 [10 ] 1 1 555 f50555 f50555 f50 c0000aa000
为了验证 555f50
是否等于 &runtime.zerobase
,可以使用 delve
调试工具打印该变量: Delve
> main.main() ./main.go :43 (PC: 0x496d65 ) 38 : fmt.Println(slice3, len (slice3), cap (slice3)) 39 : fmt.Println(slice4, len (slice4), cap (slice4)) 40 : 41 : fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice1)).Data) 42 : fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice2)).Data) => 43 : fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice3)).Data) 44 : fmt.Printf("%x\n" , (*reflect.SliceHeader)(unsafe.Pointer(&slice4)).Data) 45 : } (dlv) 561 f50 ... (dlv) p &runtime.zerobase (*uintptr )(0x561f50 ) (dlv)
OK,接下来才是重要的 初步确定切片容量 的算法,注意这里是初步确定,真正的切片容量还需要之后进行 内存对齐 。
这里我单独拿出来讨论,其中
oldCap 表示 旧切片容量
cap 表示 旧切片容量+新追加元素数量 ,可理解为期望的容量
下面是Go1.18的扩容算法
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 func grow (oldCap int , cap int ) int { newcap := oldCap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 if oldCap < threshold { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += (newcap + 3 *threshold) / 4 } if newcap <= 0 { newcap = cap } } } return newcap }
在Go1.18之前 扩容算法是这样的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 func grow (oldCap int , cap int ) int { newcap := oldCap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if oldCap < 1024 { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } return newcap }
对于Go1.18之前 的扩容机制,我是这样理解的,一般情况下扩容采取的策略是 翻倍扩容 ,但是这样又会导致一个问题:导致内存空间浪费,因此Go的切片扩容机制针对这种情况进行了优化。
如果append后的总容量cap,也就是旧切片容量+新追加元素的数量超过了两倍,则直接使用这个期望容量。这种情况就是一次性append了大量的元素,导致切望容量超过了原来的两倍。
反之期望容量在旧切片容量两倍之内,即最大容量上界为旧切片容量两倍,此时如果旧切片容量没有超过1024,则直接翻倍扩容。目的是对于 小切片 (容量小于1024)直接翻倍扩容,没必要再计算了。
否则每次增加25%的容量,直到新容量大于期望容量,这种策略就是防止盲目的翻倍扩容导致内存空间浪费。
而Go1.18更新后 扩容机制发生了变化,小切片最大容量不再是1024,而是256,同时在计算新容量时除了每次增加25%容量,还额外多加了192。
举个例子来说:假如旧切片容量oldCap为10000,append的元素数量为5000,则期望的容量cap为15000,采取不同的策略扩容:
直接翻倍扩容:newcap=20000
Go1.18之前版本:按比例增长:newcap=15625
Go1.18之后版本:按比例增长:newcap=16057
虽然Go1.17和1.18在计算扩容后新的容量得到的大小不一样,但是别忘了,最后还需要计算内存对齐大小,经过内存对齐后的大小两者是一样的。
除了计算扩容大小之外,还需要计算扩容后的内存对齐大小,下面通过一个例子讲解是如何计算内存对齐大小的。
var slice []int64 = make ([]int64 , 0 ) slice = append (slice, 1 , 2 , 3 , 4 , 5 ) fmt.Println(unsafe.Sizeof(slice)) fmt.Println(len (slice)) fmt.Println(cap (slice))
当执行 append
时,调用 growslice(oldSlice={ptr, 0, 0}, cap=5])
,此时 5 > 0+0
,即 newcap = 5
,由于元素类型为 int64
,大小为8个字节,即64位下指针大小 goarch.PtrSize=8
。
接下来就是计算内存对齐大小:
lenmem = uintptr (old.len ) * goarch.PtrSize newlenmem = uintptr (cap ) * goarch.PtrSize capmem = roundupsize(uintptr (newcap) * goarch.PtrSize) overflow = uintptr (newcap) > maxAlloc/goarch.PtrSize newcap = int (capmem / goarch.PtrSize)
转换为就是
lenmem = uintptr (0 ) * 8 = 0 newlenmem = uintptr (5 ) * 8 = 40 capmem = roundupsize(uintptr (5 ) * 8 ) = 48 overflow = uintptr (newcap) > maxAlloc/goarch.PtrSize newcap = int (48 / 8 ) = 6
注意,上面的重点是 capmem = roundupsize(uintptr(5) * 8) = 48
,那么 roundupsize
做了什么?
roundupsize内存对齐
该函数位于 src/runtime/msize.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 func roundupsize (size uintptr ) uintptr { if size < _MaxSmallSize { if size <= smallSizeMax-8 { return uintptr (class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]]) } else { return uintptr (class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]]) } } if size+_PageSize < size { return size } return alignUp(size, _PageSize) }func divRoundUp (n, a uintptr ) uintptr { return (n + a - 1 ) / a }
其中 class_to_size
和size_to_class8
是一个数组,也就是 内存对齐表 (具体位于 src/runtime/sizeclasses.go
) ,这两个数组在Go中内存分配中还会见到(因为Go大部分采用了TCMalloc多级缓存 内存分配算法)。
size_to_class8 表示需要多少个8字节来内存对齐
class_to_size 表示对应的内存对齐后的字节大小
size_to_class8:0 , 1 , 2 , 3 , 4 , 5 , 5 , 6 , 6 , 7 , 7 , 8 , 8 , 9 , 9 , 10 , 10 , 11 , 11. .. class_to_size:0 , 8 , 16 , 24 , 32 , 48 , 64 , 80 , 96 , 112 , 128 , 144 , 160 , 176 , 192 , 208. ..
因此当我们调用 roundupsize(40*8)
时,实际为:
divRoundUp(40 , 8 ) = ceil(40 /8 ) = 5 ,也就是有5 个8 字节单位 size_to_class8[5 ] = 5 class_to_size[5 ] = 48 ,因此对齐后的内存大小/切片最大容量 为 48 字节,而不是 40 字节。
slicecopy切片复制
Go中使用 copy(to, from)
拷贝切片,举个例子:
var slice1 []int var slice2 []int = make ([]int , 10 );copy (slice1, slice2)
具体实现位于 src/runtime/slice.go
下的 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 , fromPtr unsafe.Pointer, fromLen int , width uintptr ) int { if fromLen == 0 || toLen == 0 { return 0 } n := fromLen if toLen < n { n = toLen } if width == 0 { return n } size := uintptr (n) * width ... if size == 1 { *(*byte )(toPtr) = *(*byte )(fromPtr) } else { memmove(toPtr, fromPtr, size) } return n }
最终拷贝操作 runtime.memmove
由汇编完成的。
总结
Go在1.18版本中加入了 泛型 ,相比之前发生很多的变化,其中就包括了切片扩容计算,在我写这篇文章之前,我在网上搜寻的资料大部分还是之前的版本,截至目前,自Go1.18正式发布 过去很多天了,为了保持与时俱进肯定要研究最新的啦😄。
希望对你有帮助~😘