Go Slice 深度解析

站长

2022年12月09日 05:41 · 阅读数 53

1. Slice

1.1 Slice的类型

Slice由一个指向数组的指针和两个int类型的变量 长度、容量 组成。

type Slice struct{
    array unsafe.Pointer // 指向底层数组
    len   int // 切片可用元素的个数，使用下标访问元素时，下标不能超过的长度
    cap   int // 底层数组的元素个数，容量 >= 长度
}

1.2 Nil Slice 和 Empty Slice

创建方式	nil切片	空切片
方式一	var s1 []int	var s2 = []int{}
方式二	var s4 = *new([]int)	var s3 = make([]int, 0)
和 `nil` 比较	`true`	`false`

nil Slice 和 Empty Slice 的长度和容量都为空但空切片的指针指向都指向着同一个地址(每台机器可能不同) Go Slice 深度解析

2. Slice 和 Array

2.1 Slice 和 Array的区别

slice 的底层数据是数组，slice 是对数组的封装，它描述一个数组的片段。两者都可以通过下标来访问单个元素。

数组是定长的，长度定义好之后，不能再更改。其长度是类型的一部分，限制了它的表达能力，比如 [1]int 和 [2]int 就是不同的类型。

而切片则非常灵活，它可以动态地扩容。切片的类型和长度无关。我们写一个函数调用打印二者的 len 与 cap

2.2 Slice 和 Array的传递对比

package main
func main(){
	s := make([]int, 10)
	printSlice(s)

	var a [100]int
	printArray(a)
}

func printSlice(s []int){
	print(len(s))
	print(cap(s))
}

func printArray(a [100]int){
	println(len(a))
	println(cap(a))
}

go tool compile -N -S -l main.go 生成汇编代码
- -N 参数表示禁止编译优化
- -l 表示禁止内联
- -S 表示打印汇编
printSlice
- 可以看出传递的是结构体
- 红线部分为将 Slice 的 len 和 cap 传递给堆栈寄存器

Go Slice 深度解析

print函数将栈底存储的 len 和 cap 传递给栈顶并打印

Go Slice 深度解析

printArray
- 而Array的 len 和 cap 是传入固定的值

3. Slice 的 append

3.1 示例

func main() {
	s := make([]int, 0)

	oldCap := cap(s)

	for i := 0; i < 1024; i++ {
		s = append(s, i)

		newCap := cap(s)

		if newCap != oldCap {
			fmt.Printf(" cap = %-4d  ->  cap = %-4d\n",  oldCap,  newCap)
			oldCap = newCap
		}
	}
}

打印结果 Go Slice 深度解析我们发现好像并非网络上所说的若老数组的容量小于 1024 则每次扩容 cap 翻倍，大于则扩充接近 1/4 的容量为什么呢？让我们去标准库中寻找结果吧！

3.2 扩容内涵

runtime/slice.go

func 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 {
			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:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == goarch.PtrSize:
		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)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if goarch.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) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}

	...

不要被这么长的代码吓到，我们先来分析一下前面半段。 cap 是我们将要扩充到的容量，我们先获取老底层数组的容量的翻倍 doublecap

如果 cap比 doublecap 还大的话则直接将新数组容定为 cap
否则我们设置一个门槛(threshold) = 256,
- 如果扩容前容量小于门槛的话直接翻倍
- 否则 newcap += (newcap + 3*threshold) / 4 直到 newcap 大于 cap

我们拿 512 扩容到 848的例子来试一试： old.cap 大于 threshold，所以进行 newcap += (newcap + 3*threshold) / 4 （512 + 3 * 256）/4 = 320, 512 + 320 = 832 欸？不对啊，不应该是848吗？

不急，我们再回到源码中的 switch 语句中我们只需要知道 roundupsize 函数的作用是内存对齐，而最终的结果是经过内存对齐后的结果，这也是扩充后的容量比计算的大的原因了。

3.3 调优

在 len 和 cap 为0 的Slice中添加三个值，此时该 Slice的 cap 是多少呢？

s := make([]int, 0)
	s = append(s, 1,2,3)
	print(cap(s))

答案是3， Go在此情况下进行了内存的优化

3.4 append Slice 三种方法对比

方法1：对 len = 0, cap = 0 的Slice进行扩容 10000 次

func BenchmarkAppend1(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++{
		var s []int
		for j := 0; j < 10000; j++{
			s = append(s, j)
		}
	}
}

方法2：对 len = 0, cap = 10000 的Slice进行扩容 10000 次

func BenchmarkAppend2(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++{
		s := make([]int, 0, 10000)
		for j := 0; j < 10000; j++{
			s = append(s, j)
		}
	}
}

方法3：对 len = 0, cap = 10000 的Slice进行扩容 10000 次，但是用索引赋值

func BenchmarkAppend3(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++{
		s := make([]int, 10000)
		for j := 0; j < 10000; j++{
			s[j] = j
		}
	}
}

执行结果可以看出 cap 从0开始扩容明显比其他两个慢许多而索引赋值稍快于 append

为什么索引赋值更快呢？我们看看底层的汇编代码
- append 赋值
- 索引赋值

不用关注具体细节，从代码量来看索引赋值明显比 append 赋值少

3.5 简单案例

func main(){
	var s []int
	for i := 0; i < 3; i++{
		s = append(s, i)
	}
	modifySlice(s)
	fmt.Print(s)
}

func modifySlice(s []int){
	s[0] = 1024
}

执行结果为 [1024 1 2] 传递的结构体内有底层数组的指针，通过指针修改底层数组

我们在 modify 函数内增加一句 append 语句

func main(){
	var s []int
	for i := 0; i < 3; i++{
		s = append(s, i)
	}
	modifySlice(s)
	fmt.Print(s)
}

func modifySlice(s []int){
	s = append(s, 2048)
	s[0] = 1024
}

执行结果为 [1024 1 2] append后 len + 1，由于结构体值传递 len 传递的为值而不向底层数组传递的是地址(指针用法)，所以改动无法回到 main 函数内

再添加一句 append

func main(){
	var s []int
	for i := 0; i < 3; i++{
		s = append(s, i)
	}
	modifySlice(s)
	fmt.Print(s)
}

func modifySlice(s []int){
	s = append(s, 2048)
	s = append(s, 4096)
	s[0] = 1024
}

执行结果为 [0 1 2] 第二次 append 时由于 cap 不够了，Slice 进行扩容操作，新建了一个底层数组并指向它，从此函数的 Slice 的数组指针和 main函数的 Slice的数组指针不再相同(地址不一样)，函数内对数组的修改不再作用于 main 函数

4. 小技巧 Bounds Checking Elimination 边界检查

平常我们获取 Slice 内容时都是直接获取

func nomal(s []int){
	i := 0
	i += s[0]
	i += s[1]
	i += s[2]
}

但我们可以在获取之前对要获取的最大索引进行检查

func bce(s []int){
	_ = s[2]
	i := 0
	i += s[0]
	i += s[1]
	i += s[2]
}

这样会加快我们的运行效率。为什么呢？让我们从汇编的角度去看看吧！

nomal函数调用时由于索引是递增调用，编译器无法确定索引值是否存在，所以每次赋值前都需先比较一次，若不存在则 JLS(跳跃到) 相应语句，执行 panicIndex
而边界检查先将所需要使用的最大的索引进行赋值判断，编译器知道最大的索引是否存在后，即可不再判断其余的索引了

本节内容到此结束！感谢阅读。

转载自:https://juejin.cn/post/7170008177465884709