首页 > 编程知识 正文

golang切片扩容,golang切片底层原理

时间:2023-05-03 08:49:06 阅读:157414 作者:2792

golang数组和切片数组是声明数组时必须指定数组长度的一组有序元素。

数组是值类型,数组中元素在内存中的地址是连续的。

当声明赋值//数组声明时,指定长度var arr [4]int//数组元素赋值arr[1]=1//打印数组地址fmt.println(unsafe.pointer(arr ) )/0xc 000103 ard 必须指定每个打印元素。元素必须是内存中连续的fmt.println (unsafe.pointer (arr [0] ) )/0xc0000103a0fmt.println ) unsafe.pointer (arr ) 用0000xc 0000103 b0fmt.println (unsafe.pointer (arr [3] ) )//0xc0000103b8片声明///make初始化,用make的第一个参数表示片的长度,2 默认s:=make([]int,4,4 ) /来自数组的片arr:=[.]int ) 0、1、2、3、4 ) s=arr ) :5 )数据结构

typeslicestruct {指向array unsafe.pointer//要引用的数组的指针len int//片的长度cap int//片的容量}自己创建片的结构,并获取片的信息。 reflect/value.go中的SliceHeader与此类似。

typeslicestruct { ptr unsafe.pointerlenintcapint } func main () s:=make([]int,4 ) S1:=*(slice ) unsafe.s 4容量fmt.println(unsafe.sizeof )/24 )切片由指向数组的指针、长度、容量切片的编入方法【make】这3个属性构成

var a []int=make([]int,0,0 ] funcmakeslice [ et * _ type,len,capint]unsafe.pointer{//从容量中选择所需的内存大小mem, 要计算其OVV的uintptr(cap ) ) if overflow|| len0| le ncap { mem,overflow :=math.mul uintptr } et.size uintptr(len ) ) if overflow|| len0(panicmakeslicelen ) }//分配内存,并分配内存的地址randle

make调用runtime.makeslice方法

makeslice主要为片分配内存空间

【复印】深度复印

funcslicecopy(to,fm slice, width uintptr ) int { . size :=uintptr(n ) n ) widthifsize==1{//commoncaseworthabout * * byte ((to.array ) ) knowntobeabytepointer ) else(/FM.array副本为to.array,size size ) returnn ) copy方法是runtime.slicecopy方法slicecopy 让我们看一个例子。

【1】

fun main (()/) ) 1初始化片,len=0,cap=4vars ) (int=make ) ) int,0,4 ) fmt.Println(s )/) ) fmt )

3a0 0 4}// @2s2 := append(s, 1, 2, 3, 4)fmt.Println(s) // []fmt.Println(s2) // [1 2 3 4]fmt.Println(*(*slice)(unsafe.Pointer(&s2))) // {0xc0000103a0 4 4}// @3s3 := append(s, 5)fmt.Println(s) // []fmt.Println(s3) // [5]fmt.Println(*(*slice)(unsafe.Pointer(&s3)))// {0xc0000103a0 1 4}fmt.Println(s2) // [5 2 3 4]fmt.Println(*(*slice)(unsafe.Pointer(&s2))) // {0xc0000103a0 4 4}// @4s4 := s2[1:3]fmt.Println(s) // []fmt.Println(s2) // [5 2 3 4]fmt.Println(s4) // [2 3 4]fmt.Println(*(*slice)(unsafe.Pointer(&s4)))// {0xc0000103a8 2 3}// @5s4[0] = 6fmt.Println(s) // []fmt.Println(s2) // [5 6 3 4]fmt.Println(s3) // [5]fmt.Println(s4) // [6 3]}

观察现象可以看出:

@1,@2中s1,s2的array指向同一个内存地址,表明他们引用的是同一个底层数组@3中s3的底层数组地址跟s1、s2是一样的,不同的是s3的len是1,s2的len是4,append后,s2的第一个元素发生了变化。表明在append时,当所需要的容量没有超出原切片的容量时,将使用同一个底层数组,在这种情况下,append会修改底层数组的值,而引用同一个底层数组的切片的值也会随之发生变化。@4中,s4切片截取了s2切片,发现s4的array地址较s2偏移了8位,容量较s2减少了1。表明通过切片截取的时候,将使用跟原切片一样的底层数组,只是起始指针会随着截取开始的元素进行偏移,而容量取决于原切片的最大容量减去向右偏移数。@5证实了s1、s2、s3、s4引用的同一个数组。

【2】

func main(){// @1 var s []int = make([]int, 3, 3)fmt.Println(s) // [0 0 0]fmt.Println(*(*slice)(unsafe.Pointer(&s)))// {0xc00000a0f0 3 3}// @2s1 := append(s, 1)fmt.Println(s) // [0 0 0]fmt.Println(s1) // [0 0 0 1]fmt.Println(*(*slice)(unsafe.Pointer(&s1)))// {0xc0000103c0 4 6}// @3s2 := append(s, 1, 2, 3, 4)fmt.Println(s) // [0 0 0]fmt.Println(s2) // [0 0 0 1 2 3 4]fmt.Println(*(*slice)(unsafe.Pointer(&s2)))// {0xc00000e240 7 8}}

观察现象可以看出:

@2中,append后新切片所需要的容量为4,大于s的原容量3,s2 append后容量变成6,说明进行了扩容,指向的底层数组发生了变化,说明扩容后给新切片重新分配了新的底层数组。@3中,append后新切片所需要的容量为7,大于原容量的2倍,扩容后,容量变为8,现象表明,如果扩容后的容量大于原容量的2倍,扩容后的容量为满足容量的最小的偶数。

【growslice】

说明:append只有在原容量不能满足的时候才会调growslice进行扩容。

以 s:=append(make([]int,3,3),4,5,6,7)为例

// cap是新切片需要的容量,计算方法为原切片的长度+append的元素数 ,例子cap=3+4=7func growslice(et *_type, old slice, cap int) slice {...// 计算新切片的容量newcap := old.cap// 3doublecap := newcap + newcap // 6if cap > doublecap {// 如果需要的容量比原容量的2倍还大,newcap就等于需要的容量newcap = cap// 7} else {// 当需要的容量小于原容量的2倍时// 判断原切片的长度if old.len < 1024 {// 如果原切片的长度小于1024,newcap就等于2倍的原容量(2倍扩容)newcap = doublecap} else {// 原容量大于0并且小于需要的容量时,新切片的容量+=原切片容量的四分之一(扩容1/4),循环直到满足容量需求for 0 < newcap && newcap < cap {newcap += newcap / 4}// 当原容量<=0时,newcap等于需要的容量if newcap <= 0 {newcap = cap}}}var overflow boolvar lenmem, newlenmem, capmem uintptr// lenmem 原切片长度len*切片元素size // newlenmem 新切片所需容量cap*切片元素size// capmem 计算出新切片所需要的容量,使用了roundupsize方法// newcap 新切片容量=capmem/切片元素sizeswitch {case et.size == 1:lenmem = uintptr(old.len)newlenmem = uintptr(cap)capmem = roundupsize(uintptr(newcap))overflow = uintptr(newcap) > maxAllocnewcap = int(capmem)case et.size == sys.PtrSize:lenmem = uintptr(old.len) * sys.PtrSize// 3*8newlenmem = uintptr(cap) * sys.PtrSize// 7*8capmem = roundupsize(uintptr(newcap) * sys.PtrSize) // roundupsize(7*8)=64overflow = uintptr(newcap) > maxAlloc/sys.PtrSizenewcap = int(capmem / sys.PtrSize)// 64/8case isPowerOfTwo(et.size):var shift uintptrif 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) << shiftnewlenmem = uintptr(cap) << shiftcapmem = roundupsize(uintptr(newcap) << shift)overflow = uintptr(newcap) > (maxAlloc >> shift)newcap = int(capmem >> shift)default:lenmem = uintptr(old.len) * et.sizenewlenmem = uintptr(cap) * et.sizecapmem, 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.Pointerif 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)}}// 将原切片的数组复制lenmem到新切片memmove(p, old.array, lenmem)// 返回新切片,长度等于原切片的len,容量等于newcapreturn slice{p, old.len, newcap}// slice{p,3,8}}

growslice方法会新生成一个切片,把原切片的数组复制到新切片,然后返回,可以看到,append切片扩容是分两部分进行的,新调用growslice进行扩容,再把新添加的数组添加到新切片中。

需要注意的是roundupsize方法,进行了内存对齐 ,比如传入56,会返回64,详情看roundupsize的实现。

扩容规则:

如果新切片所需容量大于原切片容量的2倍,按新切片所需容量进行扩容如果新切片所需容量小于原切片容量的2倍且原切片长度小于1024,按原切片容量的2倍进行扩容如果新切片所需容量小于原切片容量的2倍且原切片长度大于1024,按原切片容量的1.25倍进行扩容 空切片和nil切片

空切片和 nil 切片的区别在于,空切片指向的地址不是nil,指向的是一个内存地址,但是它没有分配任何内存空间,即底层元素包含0个元素。
最后需要说明的一点是。不管是使用 nil 切片还是空切片,对其调用内置函数 append,len 和 cap 的效果都是一样的。

并发安全问题 func main() {var s []intvar wg sync.WaitGroupwg.Add(10000)for i := 0; i < 10000; i++ {go func() {s = append(s, i)wg.Done()}()}wg.Wait()fmt.Println(len(s))// 9030}

打印的结果不是10000,原因是切片是并发不安全的。可以使用加锁或channel的方式解决。

结论 数组是值类型,切片是引用类型。在函数中传递切片,实际上传递的是slice结构体,包含array,len,cap三个属性,避免在调用的函数中对传递的切片参数进行append切片是对数组中一段数据的引用。切片是引用类型,需要使用make进行初始化。使用make初始化时,指定适当的容量,避免频繁扩容。nil切片可以使用append,cap,len函数。append时要注意切片的扩容规则。使用copy对切片进行深拷贝。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。