聊聊 Go 的 slice

date
Nov 20, 2022
slug
slice
status
Published
tags
Go
summary
通过源码分析slice
type
Post
查看slice的源码slice的初始化slice的扩容机制step 1. 步长step 2. 内存对齐总结slice的拷贝slice遍历的坑一些问题总结Ref

查看slice的源码

查看go的版本
$ go version
go version go1.16.15 darwin/arm64
切换到我们的go安装路径，输入
$ grep -n "type slice struct" -r ./
得到输出
.//src/cmd/compile/internal/gc/go.go:77:// type slice struct {
.//src/runtime/slice.go:13:type slice struct {
我们直接进slice.go 这个文件看下
算上注释也就300行不到的代码，短小精悍，看看定义和函数列表
notion image
结构体定义
type slice struct {
	array unsafe.Pointer    // 底层数组
	len   int               // 数组长度
	cap   int               // 数组容量
}
slice是在底层的数组上面包了一层，array是指向底层数组的指针，底层数组是真正存储值的地方。而len和cap和分别表示数组当前长度和数组的容量，slice根据它们的大小关系来进行扩容。

slice的初始化

我们初始化一个slice，可以有两种方法，分别是：
make([]int, 5)    // 初始化size为5，cap为5的slice
make([]int, 0, 5) // 初始化size为0，cap为5的slice，推荐使用该方式
[]int{1, 2, ... } // 直接给定值声明
对于slice来说，make的第一个参数指定存储类型，这里是int，第二个是size，可选为0，第三个是cap，指定容量
我们一般推荐使用第二种方式，指定好cap，避免扩容带来的开销，而size我们一般指定为0，表示不存储任何元素。
如果我们指定了size，那么会在生成size个默认值在slice中，比如说int类型的默认值就是0。请看下面的打印结果
func TestSlice(t *testing.T) {
	a := make([]int, 5)
	for i := 1; i <= 5; i++ {
		a = append(a, i)
	}
	b := make([]int, 0, 10)
	for i := 1; i <= 5; i++ {
		b = append(b, i)
	}
	c := []int{1, 2, 3, 4, 5}
	fmt.Println(a, len(a), cap(a))
	fmt.Println(b, len(b), cap(b))
	fmt.Println(c, len(c), cap(c))
}
// 输出
// [0 0 0 0 0 1 2 3 4 5] 10 10
// [1 2 3 4 5] 5 10
用make([]int, size) 方式初始化，很容易忘记我们已经存储了若干个值了。除非我们真的需要这样的slice，不然还是用第二种初始化方式比较好。
下面我们看看初始化的源码：
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 {
		// NOTE: Produce a 'len out of range' error instead of a
		// 'cap out of range' error when someone does make([]T, bignumber).
		// 'cap out of range' is true too, but since the cap is only being
		// supplied implicitly, saying len is clearer.
		// See golang.org/issue/4085.
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

	return mallocgc(mem, et, true)
}
外部的逻辑是检查我们开的容量会不会溢出，如果溢出就抛出panic，否则的话调用mallocgc 进行初始化，mallocgc的源码涉及到一些go内存分配的知识，这里就不展开了，感兴趣可以自己看看。

slice的扩容机制

step 1. 步长

当我们len超过cap的时候就会触发扩容，实际调用的函数是growslice，我们来看看go是怎么实现的
// growslice handles slice growth during append.
// It is passed the slice element type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
// The new slice's length is set to the old slice's length,
// NOT to the new requested capacity.
// This is for codegen convenience. The old slice's length is used immediately
// to calculate where to write new values during an append.
// TODO: When the old backend is gone, reconsider this decision.
// The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
func 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
				}
			}
		}
	...
}
变量
含义
cap
期望容量
old.cap
当前容量
doublecap
当前容量的两倍
newcap
最终容量
决策逻辑：
  • 如果期望容量超过当前容量的两倍，直接设置为期望容量，否则
  • 如果当前容量的值小于1024，直接翻倍，否则
  • 如果newcap < cap，不断以1.25倍的速度增长
notion image
 
对于1.25倍扩增速度，go的1.18.1版本作出了优化
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 {
					// 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
					}
			}
	}
	...
}
这里的区别就是newcap += (newcap + 3*threshold) / 4 ，注释上说相比于旧版本，这里增长速度更加smooth，具体效果可以用python画图模拟一下，这里就不展开了。
下面我们来看一段代码，看看结果是不是和我们上面分析得一样
func TestSlice(t *testing.T) {
	c := make([]int, 0, 2)
	// 此时c满
	c = append(c, 1, 2)
	// 此时按照计算公式，期望容量为5，当前容量为2，则c的最终容量是5
	c = append(c, 3, 4, 5)
	// 猜测为5 5
	fmt.Println(len(c), cap(c))
}
但是输出结果是5 6，cap被设置成了6，这是为什么呢？原因是go还会进行内存对齐

step 2. 内存对齐

func 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
			}
		}
	}

	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	// Specialize for common values of et.size.
	// For 1 we don't need any division/multiplication.
	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
	// For powers of 2, use a variable shift.
	switch {
	case et.size == 1:
		...
	case et.size == sys.PtrSize:
		...
	case isPowerOfTwo(et.size):
		var shift uintptr
		if 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) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		...
	}
	...

	return slice{p, old.len, newcap}
}
et.size指的是存储元素类型的大小，这里int类型字节是8，使用下面的函数判断通过
func isPowerOfTwo(x uintptr) bool {
	return x&(x-1) == 0
}
先不看代码，我们分析一下怎么内存对齐：
我们的slice现在存储了5个元素，int类型8个字节，则新的存储容量大小newcap = 5 * 8 = 40，但是为了更好的内存分配减少碎片，go使用了和c一样的内存对齐策略，使用roundupsize 向上调整大小，这里调整成了48，那么最终的cap = 48 / 8 = 6，所以在上面的例子cap被设置为了6
为什么被调整到48呢？
原因是Go语言的内存管理通常把这些内存块都预先申请好，并且被分为常用的规格，比如8，16， 32， 48， 64等，当我们申请40 bytes的时候，会申请一个足够大的内存块给我们，这就返回的是48 bytes
至于怎么设置的呢，这里有两个很巧妙的函数 Ctz64 和 roundupsize
// Ctz64 counts trailing (low-order) zeroes,
// and if all are zero, then 64.
// 返回x中末尾0的个数
func Ctz64(x uint64) int {
	x &= -x                       // isolate low-order bit
	y := x * deBruijn64ctz >> 58  // extract part of deBruijn sequence
	i := int(deBruijnIdx64ctz[y]) // convert to bit index
	z := int((x - 1) >> 57 & 64)  // adjustment if zero
	return i + z
}

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)
}

// alignUp rounds n up to a multiple of a. a must be a power of 2.
func alignUp(n, a uintptr) uintptr {
	return (n + a - 1) &^ (a - 1)
}
// &^ 是 ANT NOT 运算符
然后我们再看这一块代码
	case isPowerOfTwo(et.size):
		var shift uintptr
		if 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
		}
		capmem = roundupsize(uintptr(newcap) << shift)
		newcap = int(capmem >> shift)
首先我们通过Ctz64(et.size) 得到shift的值，int类型是8个字节，则8的二进制末尾有3个0，我们得到shift=3
然后newcap<<shift 就是 5 << 3 得到40
经过roundupsize，得到capmem = 48
最终再还原回来 newcap = int(48 >> 3) = 6
这样就能内存对齐啦

总结

slice的扩容步骤有两步
  1. 调整期望容量
    1. 如果期望容量是当前容量的两倍，直接更新，否则
    2. 如果小于1024，直接翻倍当前容量，否则
    3. 当前容量按照1.25的速度增长，直到超过期望容量
  1. 进行内存对齐，向上调整到最接近的2的n次幂

slice的拷贝

切片拷贝的方法是slicecopy，我们看看是怎么做的：
// slicecopy is used to copy from a string or slice of pointerless elements into a slice.
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
	// 如果有一个长度为0，提前退出
	if fromLen == 0 || toLen == 0 {
		return 0
	}
	
	// 记录下较短的长度
	n := fromLen
	if toLen < n {
		n = toLen
	}
	// 如果指定的长度为0，那么提前退出
	if width == 0 {
		return n
	}

	size := uintptr(n) * width
	...

	if size == 1 { // common case worth about 2x to do here
		// TODO: is this still worth it with new memmove impl?

		// 如果只有一个长度，直接指针转换即可
		*(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
	} else {
		// 从from.array 移动 size 个 bytes 拷贝到 to.array
		memmove(toPtr, fromPtr, size)
	}
	return n
}
执行看看效果
func TestCopy(t *testing.T) {
	a := []int{1, 2, 3}
	b := make([]int, 5)
	c := make([]int, 2)
	n := copy(b, a)
	fmt.Println(b, n)
	n = copy(c, a)
	fmt.Println(c, n)
}

// === RUN   TestCopy
// [1 2 3 0 0] 3
// [1 2] 2
// --- PASS: TestCopy (0.00s)

slice遍历的坑

但是我们拷贝有一个需要注意的地方：
func TestFor(t *testing.T) {
	slice := []int{10, 20, 30, 40}
	for index, value := range slice {
		fmt.Printf("value = %d , value-addr = %x , slice-addr = %x\n", value, &value, &slice[index])
	}
}
输出：
=== RUN   TestFor
value = 10 , value-addr = 1400001e250 , slice-addr = 1400001a0a0
value = 20 , value-addr = 1400001e250 , slice-addr = 1400001a0a8
value = 30 , value-addr = 1400001e250 , slice-addr = 1400001a0b0
value = 40 , value-addr = 1400001e250 , slice-addr = 1400001a0b8
--- PASS: TestFor (0.00s)
可以看到，我们用range去遍历切片的时候，拿到的value其实是切片里面的值拷贝，所以每次Value的地址都不变。因此我们需要用&slice[index]才能拿到真实的地址
notion image
ref: 深入解析 Go 中 Slice 底层实现 (halfrost.com)
如果不注意到这点的话，会带来什么问题呢？当我们拷贝的时候可能就会踩坑了：
func TestFor(t *testing.T) {
	slice := []int{10, 20, 30, 40}
	to := make([]*int, 0, len(slice))
	for _, value := range slice {
		to = append(to, &value)
	}
	for _, value := range to {
		fmt.Println(*value, value)
	}
}
输出：
=== RUN   TestFor
40 0x14000098168
40 0x14000098168
40 0x14000098168
40 0x14000098168
--- PASS: TestFor (0.00s)
可以发现，每次append到to里面的地址都是创建的临时变量value，而value最后的值是40，所以导致最后输出值都是40，且指向的地址就是value的地址。
要避免这个坑，我们要记住for遍历的时候会创建临时变量，避免直接对临时变量操作。
// 方法一，直接操作slice的值
for index, _ := range slice {
		to = append(to, &slice[index])
}

// 方法二，创建临时变量
for _, value := range slice {
		tmp := value
		to = append(to, &tmp)
}
 

一些问题

  • 为什么1024之后的扩展速度变为1.25倍呢？
因为内存空间很宝贵，底层的数组是在内存中连续的空间，申请这样大规模连续的空间是很昂贵的，1024之后我们用1.25的速度扩展已经足够大了，这样相比于翻倍扩展能解决更多的空间
  • 为什么要内存对齐？
因为内存管理会预先申请内存后再进行分配，预先申请的大小都是常用的规格，比如说8，16，32，48，64等，因此我们需要进行内存对齐来返回一个足够大的内存块使用。这样避免任意大小的内存块产生内存碎片，影响空间申请和整理。

总结

简单介绍了一下slice的代码，短小精悍，主要有初始化、扩容、拷贝三种操作。
日常使用的时候，我们最好指定cap的上限，避免扩容带来的开销。同时避免切片遍历的坑。

Ref

浅谈 Go 1.18.1的切片扩容机制 - Lookcos 的网络日志
深入解析 Go 中 Slice 底层实现 (halfrost.com)
slice · 深入解析Go (gitbooks.io)
golang slice扩容机制 (lifegoeson.cn)
1.5 在 Go 中恰到好处的内存对齐 - 跟煎鱼学 Go (gitbook.io)
go：&^ 运算符 - 知乎 (zhihu.com)

© hhmy 2019 - 2023

powered by nobelium