在 Go 语言中,有一个很常用的数据结构,那就是切片(Slice)。
切片是一个拥有相同类型元素的可变长度的序列,它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。
【资料图】
切片是一种引用类型,它有三个属性:指针,长度和容量。
底层源码定义如下:
type slice struct { array unsafe.Pointer len int cap int}指针:指向 slice 可以访问到的第一个元素。长度:slice 中元素个数。容量:slice 起始元素到底层数组最后一个元素间的元素个数。
比如使用make([]byte, 5)创建一个切片,它看起来是这样的:
声明和初始化切片的使用还是比较简单的,这里举一个例子,直接看代码吧。
func main() { var nums []int // 声明切片 fmt.Println(len(nums), cap(nums)) // 0 0 nums = append(nums, 1) // 初始化 fmt.Println(len(nums), cap(nums)) // 1 1 nums1 := []int{1,2,3,4} // 声明并初始化 fmt.Println(len(nums1), cap(nums1)) // 4 4 nums2 := make([]int,3,5) // 使用make()函数构造切片 fmt.Println(len(nums2), cap(nums2)) // 3 5}扩容时机
当切片的长度超过其容量时,切片会自动扩容。这通常发生在使用append函数向切片中添加元素时。
扩容时,Go 运行时会分配一个新的底层数组,并将原始切片中的元素复制到新数组中。然后,原始切片将指向新数组,并更新其长度和容量。
需要注意的是,由于扩容会分配新数组并复制元素,因此可能会影响性能。如果你知道要添加多少元素,可以使用make函数预先分配足够大的切片来避免频繁扩容。
接下来看看append函数,签名如下:
func Append(slice []int, items ...int) []int
append函数参数长度可变,可以追加多个值,还可以直接追加一个切片。使用起来比较简单,分别看两个例子:
追加多个值:
package mainimport "fmt"func main() { s := []int{1, 2, 3} fmt.Println("初始切片:", s) s = append(s, 4, 5, 6) fmt.Println("追加多个值后的切片:", s)}
输出结果为:
初始切片: [1 2 3]追加多个值后的切片: [1 2 3 4 5 6]
再来看一下直接追加一个切片:
package mainimport "fmt"func main() { s1 := []int{1, 2, 3} fmt.Println("初始切片:", s1) s2 := []int{4, 5, 6} s1 = append(s1, s2...) fmt.Println("追加另一个切片后的切片:", s1)}
输出结果为:
初始切片: [1 2 3]追加另一个切片后的切片: [1 2 3 4 5 6]
再来看一个发生扩容的例子:
package mainimport "fmt"func main() { s := make([]int, 0, 3) // 创建一个长度为0,容量为3的切片 fmt.Printf("初始状态: len=%d cap=%d %v\n", len(s), cap(s), s) for i := 1; i <= 5; i++ { s = append(s, i) // 向切片中添加元素 fmt.Printf("添加元素%d: len=%d cap=%d %v\n", i, len(s), cap(s), s) }}
输出结果为:
初始状态: len=0 cap=3 []添加元素1: len=1 cap=3 [1]添加元素2: len=2 cap=3 [1 2]添加元素3: len=3 cap=3 [1 2 3]添加元素4: len=4 cap=6 [1 2 3 4]添加元素5: len=5 cap=6 [1 2 3 4 5]
在这个例子中,我们创建了一个长度为0,容量为3的切片。然后,我们使用append函数向切片中添加5个元素。
当我们添加第4个元素时,切片的长度超过了其容量。此时,切片会自动扩容。新的容量是原始容量的两倍,即6。
表面现象已经看到了,接下来,我们就深入到源码层面,看看切片的扩容机制到底是什么样的。
源码分析在 Go 语言的源码中,切片扩容通常是在进行切片的append操作时触发的。在进行append操作时,如果切片容量不足以容纳新的元素,就需要对切片进行扩容,此时就会调用growslice函数进行扩容。
growslice函数定义在 Go 语言的 runtime 包中,它的调用是在编译后的代码中实现的。具体来说,当执行append操作时,编译器会将其转换为类似下面的代码:
slice = append(slice, elem)
在上述代码中,如果切片容量不足以容纳新的元素,则会调用growslice函数进行扩容。所以growslice函数的调用是由编译器在生成的机器码中实现的,而不是在源代码中显式调用的。
切片扩容策略有两个阶段,go1.18 之前和之后是不同的,这一点在 go1.18 的 release notes 中有说明。
下面我用 go1.17 和 go1.18 两个版本来分开说明。先通过一段测试代码,直观感受一下两个版本在扩容上的区别。
package mainimport "fmt"func main() { s := make([]int, 0) oldCap := cap(s) for i := 0; i < 2048; i++ { s = append(s, i) newCap := cap(s) if newCap != oldCap { fmt.Printf("[%d -> %4d] cap = %-4d | after append %-4d cap = %-4d\n", 0, i-1, oldCap, i, newCap) oldCap = newCap } }}
上述代码先创建了一个空的 slice,然后在一个循环里不断往里面append新元素。
然后记录容量的变化,每当容量发生变化的时候,记录下老的容量,添加的元素,以及添加完元素之后的容量。
这样就可以观察,新老 slice 的容量变化情况,从而找出规律。
运行结果(1.17 版本):
[0 -> -1] cap = 0 | after append 0 cap = 1 [0 -> 0] cap = 1 | after append 1 cap = 2 [0 -> 1] cap = 2 | after append 2 cap = 4 [0 -> 3] cap = 4 | after append 4 cap = 8 [0 -> 7] cap = 8 | after append 8 cap = 16 [0 -> 15] cap = 16 | after append 16 cap = 32 [0 -> 31] cap = 32 | after append 32 cap = 64 [0 -> 63] cap = 64 | after append 64 cap = 128 [0 -> 127] cap = 128 | after append 128 cap = 256 [0 -> 255] cap = 256 | after append 256 cap = 512 [0 -> 511] cap = 512 | after append 512 cap = 1024[0 -> 1023] cap = 1024 | after append 1024 cap = 1280[0 -> 1279] cap = 1280 | after append 1280 cap = 1696[0 -> 1695] cap = 1696 | after append 1696 cap = 2304
运行结果(1.18 版本):
[0 -> -1] cap = 0 | after append 0 cap = 1[0 -> 0] cap = 1 | after append 1 cap = 2 [0 -> 1] cap = 2 | after append 2 cap = 4 [0 -> 3] cap = 4 | after append 4 cap = 8 [0 -> 7] cap = 8 | after append 8 cap = 16 [0 -> 15] cap = 16 | after append 16 cap = 32 [0 -> 31] cap = 32 | after append 32 cap = 64 [0 -> 63] cap = 64 | after append 64 cap = 128 [0 -> 127] cap = 128 | after append 128 cap = 256 [0 -> 255] cap = 256 | after append 256 cap = 512 [0 -> 511] cap = 512 | after append 512 cap = 848 [0 -> 847] cap = 848 | after append 848 cap = 1280[0 -> 1279] cap = 1280 | after append 1280 cap = 1792[0 -> 1791] cap = 1792 | after append 1792 cap = 2560
根据上面的结果还是能看到区别的,具体扩容策略下面边看源码边说明。
go1.17扩容调用的是growslice函数,我复制了其中计算新容量部分的代码。
// src/runtime/slice.gofunc growslice(et *_type, old slice, cap int) slice { // ... 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 } } } // ... return slice{p, old.len, newcap}}
在分配内存空间之前需要先确定新的切片容量,运行时根据切片的当前容量选择不同的策略进行扩容:
如果期望容量大于当前容量的两倍就会使用期望容量;如果当前切片的长度小于 1024 就会将容量翻倍;如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;go1.18// src/runtime/slice.gofunc growslice(et *_type, old slice, cap int) slice { // ... newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 if old.cap < threshold { newcap = doublecap } else { // Check 0 < newcap to detect overflow // and prevent an infinite loop. for 0 < newcap && newcap < cap { // Transition from growing 2x for small slices // to growing 1.25x for large slices. This formula // gives a smooth-ish transition between the two. newcap += (newcap + 3*threshold) / 4 } // Set newcap to the requested cap when // the newcap calculation overflowed. if newcap <= 0 { newcap = cap } } } // ... return slice{p, old.len, newcap}}
和之前版本的区别,主要在扩容阈值,以及这行代码:newcap += (newcap + 3*threshold) / 4。
在分配内存空间之前需要先确定新的切片容量,运行时根据切片的当前容量选择不同的策略进行扩容:
如果期望容量大于当前容量的两倍就会使用期望容量;如果当前切片的长度小于阈值(默认 256)就会将容量翻倍;如果当前切片的长度大于等于阈值(默认 256),就会每次增加 25% 的容量,基准是newcap + 3*threshold,直到新容量大于期望容量;内存对齐分析完两个版本的扩容策略之后,再看前面的那段测试代码,就会发现扩容之后的容量并不是严格按照这个策略的。
那是为什么呢?
实际上,growslice的后半部分还有更进一步的优化(内存对齐等),靠的是roundupsize函数,在计算完newcap值之后,还会有一个步骤计算最终的容量:
capmem = roundupsize(uintptr(newcap) * ptrSize)newcap = int(capmem / ptrSize)
这个函数的实现就不在这里深入了,先挖一个坑,以后再来补上。
总结切片扩容通常是在进行切片的append操作时触发的。在进行append操作时,如果切片容量不足以容纳新的元素,就需要对切片进行扩容,此时就会调用growslice函数进行扩容。
切片扩容分两个阶段,分为 go1.18 之前和之后:
一、go1.18 之前:
如果期望容量大于当前容量的两倍就会使用期望容量;如果当前切片的长度小于 1024 就会将容量翻倍;如果当前切片的长度大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;二、go1.18 之后:
如果期望容量大于当前容量的两倍就会使用期望容量;如果当前切片的长度小于阈值(默认 256)就会将容量翻倍;如果当前切片的长度大于等于阈值(默认 256),就会每次增加 25% 的容量,基准是newcap + 3*threshold,直到新容量大于期望容量;以上就是本文的全部内容,如果觉得还不错的话欢迎点赞,转发和关注,感谢支持。
参考文章:
https://go.dev/doc/go1.18https://go.dev/blog/sliceshttps://go.dev/blog/slices-introhttps://golang.design/go-questions/slice/grow/https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-array-and-slice/标签:
在Go语言中,有一个很常用的数据结构,那就是切片(Slice)。切片是...
为全面落实四川省高考综合改革,深入了解并解决一线教师在实施高一新...
据黑龙江省水文水资源中心消息,4月1日16时,松花江哈尔滨段(哈尔...
央视网消息:3月31日下午,我国自主研制的首套高温超导电动悬浮全要...
海南瑞泽00259604月01日在投资者关系平台上答复了投资者关心的问题...
感冒后的咳嗽和痰是上呼吸道感染的主要症状之一,可以通过以下方式...
3月31日,北京控股队高登(白衣)在比赛中突破。当日,在北京进行的...
生育保险在哪里查询缴费记录?生育保险交满多久可以报销?生育保险...
齐鲁网·闪电新闻3月31日讯3月31日,青岛市崂山区同安路过街天桥和...
1、pengyou。2、朋友。3、友轻声。以上就是【朋友的妈妈2线在完整视...
海贼王漫画剧情还在未来岛篇章,草帽一伙还没有任何办法逃离未来岛...
阿斯加特今日宣布联名华硕ROG推出了首款二次元风格超频电竞DDR5内存...
欢迎观看本篇文章,小升来为大家解答以上问题。科学老师英语怎么读...
如今越来越多的人都比较喜欢越野车,不仅开出去比较有面子,而且超...
1、有问题,百度一下百度一下,你就知道这个应该没有固定的出处,就...
中国航空新闻网讯:据飞行国际消息,资金短缺的维珍轨道公司最近几...
记者今天(31日)从国家知识产权局新闻发布会上获悉,今年4月20日至...
观点网讯:3月31日,深圳华侨城股份有限公司于线上举行2022年度业绩...
兴业银行今日举办2022年度业绩说明会。兴业银行董事长吕家进发表致...
近年来,昆明市林岸馨宸社区党委以建设服务型党组织为目标,丰富服...
杭州荷花什么时候开6月-9月荷花的花期一般在每年的6月-9月期间。盛 ">
据CNBC报道当地时间30日美国维珍轨道公司股价在盘后大跌当天下午美...
新浪科技讯北京时间3月31日上午消息,美国视频流媒体巨头(Netflix...
根据生意社监测的数据显示,截止3月31日,国内工业级优等品环己烷均...
图为税费管家在中国电信海北分公司向企业负责人问需问计。 李涛 ...
河南经济报记者李洪通讯员白永春高亚娟为增长学生的法律知识,营造...
3月30日,瀚蓝环境(600323)融资买入342 34万元,融资偿还400 51...
格隆汇3月31日丨合景悠活(03913 HK)发布公告,截至2022年12月31日...
随着国际疫情防控常态化和国内疫情防控进入新阶段,4月8日至16日,...
1、从字面上说,这句话很好理解,译成现代文是:是谁在江畔第一次看...