深入浅出 go slice

这是【深入浅出 go xx】系列的第一篇。在该系列中，会对 go 的一些基本特性，从定义到源码进行整理和记录。

希望不要跳票。

什么是 slice？

slice 是 Go 的一种基本的数据结构。它在数组之上做了一层封装，相当于动态数组。它持有对底层数组的引用。

因此： * 如果你将一个 slice 赋给另一个 slice，那么，这两个 slice 都会指向同一个数组。 * 如果一个函数的参数包含 slice，那么，对入参 slice 的元素的改动对于该函数的调用者是可见的。类似于传递一个指向底层数组的指针给函数。

每个 slice 都有两个属性：length 和 capacity。前者是 slice 的底层数组的元素个数，后者是底层数组的长度。length 会随着 slice 的元素改动在 capacity 的范围内发生改变。可以通过内置函数 cap 查看 slice 的 capacity，通过 len 查看 length。可以使用 append 方法将数据追加到 slice 之后。如果数据超过了 capacity，那么，会为 slice 重新分配空间，并返回最终的 slice。

注意：对 nil slice 使用 cap 和 len 方法是合法的，此时会返回 0。

如何使用 slice

可以使用内置函数 make([]T, length, capacity) 创建一个新的已初始化的类型为 T 的 slice。例如：

// 创建并初始化一个类型为 int，length 为 50，capacity 为 100 的 slice
slc := make([]int, 50, 100)

上面的代码等价于创建一个长度为 50 的数组，然后对其进行切片：

slc := ([100]int)[0:50]

此外，还可以使用字面量创建切片：

// 会创建一个 length 为 5，capacity 为 5 的 slice
// 注意：[] 里面不要写容量。否则创建的就是数组，而不是 slice 了。
slc := []int{1, 2, 3, 4, 5}

## slice 的底层实现 > 基于 go 1.11.1

结构定义

可以在 /src/runtime/slice.go 中找到对 slice 的定义：

type slice struct {
	array unsafe.Pointer // 指向一个数组的指针
	len   int // 当前切片的长度
	cap   int // 当前切片的容量
}

创建切片

使用以下方法创建切片：

func makeslice(et *_type, len, cap int) slice {
	// 根据切片元素的类型，获取最大可创建元素个数
	maxElements := maxSliceCap(et.size)
	// 判断要创建切片的长度：非零且不超过最大个数
	if len < 0 || uintptr(len) > maxElements {
		panicmakeslicelen()
	}
    // 判断要创建切片的容量：非零且不超过最大个数
	if cap < len || uintptr(cap) > maxElements {
		panicmakeslicecap()
	}
    // 根据容量申请所需内存
	p := mallocgc(et.size*uintptr(cap), et, true)
	// 返回申请好内存的切片的首地址
	return slice{p, len, cap}
}

还有一个针对大小和容量是 int64 的方法：

func makeslice64(et *_type, len64, cap64 int64) slice {
    // 长度和容量必须在 int 范围内
	len := int(len64)
	if int64(len) != len64 {
		panicmakeslicelen()
	}

	cap := int(cap64)
	if int64(cap) != cap64 {
		panicmakeslicecap()
	}
    // 将长度和容量转换成 int 后，调用创建
	return makeslice(et, len, cap)
}

append()

golang 中有一个内置函数可以对 slice 进行追加。函数声明如下：

func append(slice []Type, elems ...Type) []Type

该函数会将 elems 追加到 slice 之后。如果 slice 有足够的 capacity，那么直接追加。否则，会分配一个新的底层数组。

有三种使用方式：

slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)
slice = append([]byte("hello "), "world"...)

### 扩容 当一个切片满了，就需要扩容了。扩容动作是通过调用下面函数完成的：

// growslice handles slice growth during append.
// 三个入参非别是：slice 元素类型，旧的 slice，以及所需的最小 capacity
func growslice(et *_type, old slice, cap int) slice {
	if raceenabled {
		callerpc := getcallerpc()
		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
	}
	if msanenabled {
		msanread(old.array, uintptr(old.len*int(et.size)))
	}

	if et.size == 0 {
	    // 检查：申请的新 capacity 不能小于旧的
		if cap < old.cap {
			panic(errorString("growslice: cap out of range"))
		}
		// append should not create a slice with nil pointer but non-zero len.
		// We assume that append doesn't need to preserve old.array in this case.
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

    // 确定新的 slice 的 capacity。其初始值为旧的 slice 的 capacity
	newcap := old.cap
	doublecap := newcap + newcap
	// 1. 如果所需要的最小 capacity 超过两倍的旧的 slice 的 capacity，
	// 那么将新的 slice 的 capacity 设置为所需要的最小 capacity
	if cap > doublecap { 
		newcap = cap
	} else {
	    // 2. 否则，当旧的 slice 的 length 小于 1024 时，
	    // 将新的 slice 的 capacity 设置为两倍的旧的 slice 的 capacity
		if old.len < 1024 {
			newcap = doublecap
		} else {
		    // 3. 否则，不断地扩张新的 slice 的 capacity 直至它的值不小于所需的最小 capacity。每次扩张的值是当前 capacity 的 1/4（这里会检测这个 capacity 是否为正数，以防止溢出以及死循环）
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			// 当新的 slice 的 capacity 溢出时，设置它的值为所需的最小 capacity。
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

    // 根据 slice 的元素类型大小，调整新的 slice 的 capacity
	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	// 针对一些常见的元素类型大小（et.size）：
	// 1. 当大小为 1 时，无需进行任何乘除操作
	// 2. 当大小为 sys.PtrSize 时，编译器会将乘除操作优化为常量移位
	// 3. 当大小为 2 的幂时，使用变量移位
	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 == sys.PtrSize:
		lenmem = uintptr(old.len) * sys.PtrSize
		newlenmem = uintptr(cap) * sys.PtrSize
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
		newcap = int(capmem / 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:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem = roundupsize(uintptr(newcap) * et.size)
		overflow = uintptr(newcap) > maxSliceCap(et.size)
		newcap = int(capmem / et.size)
	}

	// 判断异常情况：
	// 1. 缩容
	// 2. 申请的容量会导致溢出
	if cap < old.cap || overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer // 新的 slice 的底层数组
	if et.kind&kindNoPointers != 0 {
	    // 申请内存。此时并不进行初始化
		p = mallocgc(capmem, nil, false)
		// 将旧的 slice 的底层数组中的元素拷贝到新的 slice 的底层数组中。
		memmove(p, old.array, lenmem)
		// 调用该函数的 append() 方法将会重写底层数组中从 old.len 到 cap（将会成为新的 slice 新的 length）索引。
		// 因此，仅需初始化不会被重写的部分为零值。也就是 cap 之后的位置
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// 重新申请内存，并初始化为零值
		p = mallocgc(capmem, et, true)
		if !writeBarrier.enabled {
		    // 如果不能打开写锁，那么把将旧的 slice 的底层数组中的元素拷贝到新的 slice 的底层数组中
			memmove(p, old.array, lenmem)
		} else {
		    // 循环拷贝旧的 slice 的值
			for i := uintptr(0); i < lenmem; i += et.size {
				typedmemmove(et, add(p, i), add(old.array, i))
			}
		}
	}
    // 返回：一个新的 slice，
    // 这个 slice 的 capacity 的最小值为传入的 cap，并且会将旧的 slice 中的元素拷贝到这个新的 slice 中。
    // 这个 slice 的 length 会被设置成旧的 slice 的 length，而不是新的所需的 capacity。
    // 这样做的目的是出于代码生成的方便。而在 append 期间，这个 length 是会随着新元素的写入而发生变化的。
	return slice{p, old.len, newcap}
}

拷贝

golang 提供了一个内置函数 copy 来进行 slice 拷贝。函数定义如下：

func copy(dst, src []Type) int

这个函数会将源 slice src 中的元素拷贝到目标 slice dst 中（有一个特殊场景：它还会将一个字符串中的字节拷贝到一个 bytes slice 中）。源和目标可能会发生重叠。 该函数返回拷贝的元素个数，即 min(len(src), len(dst)。

slice 的拷贝是通过以下函数实现的：

func slicecopy(to, fm slice, width uintptr) int {
    // 如果源 slice 或者目标 slice 的 length 为 0，则无需拷贝，直接返回
	if fm.len == 0 || to.len == 0 {
		return 0
	}
    // 记录源 slice 和目标 slice 之间最短的 length
	n := fm.len
	if to.len < n {
		n = to.len
	}

	if width == 0 {
		return n
	}
    
	if raceenabled { // 开启了竞争检测
		callerpc := getcallerpc()
		pc := funcPC(slicecopy)
		racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
		racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
	}
	if msanenabled { // 开启了 the memory sanitizer
		msanwrite(to.array, uintptr(n*int(width)))
		msanread(fm.array, uintptr(n*int(width)))
	}

	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)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
	} else {
		memmove(to.array, fm.array, size)
	}
	return n
}

还有一个函数 func slicestringcopy(to []byte, fm string) int 实现了上面提到的特殊场景。实现跟 slicecopy 相似，这里不再赘述。

slice 使用注意事项

当 slice 作为函数参数，并且在函数中进行修改时……

来源：GopherCon 2018: Jon Bodner - Go Says WAT

考虑以下例子：

func grow(s []int) {
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
	s = append(s, 4, 5, 6)
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

func main() {
	s := []int{1, 2, 3}
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
	grow(s)
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

运行输出

value: [1 2 3], length: 3, capacity: 3, addr: 0xc00000a460
value: [1 2 3], length: 3, capacity: 3, addr: 0xc00000a460
value: [1 2 3 4 5 6], length: 6, capacity: 6, addr: 0xc00000c330
value: [1 2 3], length: 3, capacity: 3, addr: 0xc00000a460

为什么调用 grow() 之后得到的 s 是 [1 2 3]，而不是 [1 2 3 4 5 6] 呢？

因为在 append 的时候，s 没有足够的容量。因此，会创建一个新的 slice。可以从上面的打印看到，在 append 调用前后，s 的容量和地址都发生了改变。因此，append 并不会对 main 函数中的 s 作出任何修改。

那么，如果我们给 s 设置了一个足够大的 capacity 呢？

func grow(s []int) {
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
	s = append(s, 4, 5, 6)
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

func main() {
	s := make([]int, 0, 10)
	s = append(s, 1, 2, 3)
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
	grow(s)
	fmt.Printf("value: %v, length: %d, capacity: %d, addr: %p\n", s, len(s), cap(s), s)
}

运行输出：

value: [1 2 3], length: 3, capacity: 10, addr: 0xc00007e0a0
value: [1 2 3], length: 3, capacity: 10, addr: 0xc00007e0a0
value: [1 2 3 4 5 6], length: 6, capacity: 10, addr: 0xc00007e0a0
value: [1 2 3], length: 3, capacity: 10, addr: 0xc00007e0a0

结果是，调用 grow() 之后得到的 s 还是 [1 2 3]！

这是因为，上面提到了，一个 slice 是由 array，len 和 cap 一起标识的，并且在作为入参时是按值传递的。因此，无论是在 main 函数，还是在 grow 函数，s 指向的都是同一个底层数组。但是，在 grow 函数中，s 的 len 值发生了改变，而在 main 中，s 的 len 值还是保持了原样。

另一方面，Go 使用 reflect 包的 Value.Pointer 来获取指针，此时，得到的是底层数组的指针，而不是 slice 的指针。因此，打印出来的指针是同一个。

参考

• Effective go: slices
• The Go Programming Language Specification: slice type
• 深入解析 Go 中 Slice 底层实现