召开网站建设培训会,找人做小程序要多少钱,涂鸦app定制开发,军事网站大全军事网在 Go 语言中#xff0c;有一个很常用的数据结构#xff0c;那就是切片#xff08;Slice#xff09;。
切片是一个拥有相同类型元素的可变长度的序列#xff0c;它是基于数组类型做的一层封装。它非常灵活#xff0c;支持自动扩容。
切片是一种引用类型#xff0c;它有…在 Go 语言中有一个很常用的数据结构那就是切片Slice。
切片是一个拥有相同类型元素的可变长度的序列它是基于数组类型做的一层封装。它非常灵活支持自动扩容。
切片是一种引用类型它有三个属性指针长度和容量。 底层源码定义如下
type slice struct {array unsafe.Pointerlen intcap int
}指针 指向 slice 可以访问到的第一个元素。长度 slice 中元素个数。容量 slice 起始元素到底层数组最后一个元素间的元素个数。
比如使用 make([]byte, 5) 创建一个切片它看起来是这样的 声明和初始化
切片的使用还是比较简单的这里举一个例子直接看代码吧。
func main() {var nums []int // 声明切片fmt.Println(len(nums), cap(nums)) // 0 0nums append(nums, 1) // 初始化fmt.Println(len(nums), cap(nums)) // 1 1nums1 : []int{1,2,3,4} // 声明并初始化fmt.Println(len(nums1), cap(nums1)) // 4 4nums2 : make([]int,3,5) // 使用make()函数构造切片fmt.Println(len(nums2), cap(nums2)) // 3 5
}扩容时机
当切片的长度超过其容量时切片会自动扩容。这通常发生在使用 append 函数向切片中添加元素时。
扩容时Go 运行时会分配一个新的底层数组并将原始切片中的元素复制到新数组中。然后原始切片将指向新数组并更新其长度和容量。
需要注意的是由于扩容会分配新数组并复制元素因此可能会影响性能。如果你知道要添加多少元素可以使用 make 函数预先分配足够大的切片来避免频繁扩容。
接下来看看 append 函数签名如下
func Append(slice []int, items ...int) []intappend 函数参数长度可变可以追加多个值还可以直接追加一个切片。使用起来比较简单分别看两个例子
追加多个值
package mainimport fmtfunc 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 fmtfunc 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 fmtfunc 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)}
}输出结果为
初始状态: len0 cap3 []
添加元素1: len1 cap3 [1]
添加元素2: len2 cap3 [1 2]
添加元素3: len3 cap3 [1 2 3]
添加元素4: len4 cap6 [1 2 3 4]
添加元素5: len5 cap6 [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 fmtfunc 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.capdoublecap : newcap newcapif 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.capdoublecap : newcap newcapif cap doublecap {newcap cap} else {const threshold 256if 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直到新容量大于期望容量
