2.2 Slice 性能及陷阱

1. 数组

1.1 类型

Golang 中的数组类型由两个因素确定：

1. 数组长度
2. 元素类型

只有两者均相同时，才是相同类型：

a := [2]int{1, 2}
b := [2]string{"a", "b"}
c := [3]int{1, 2, 3}

• a和b 长度相同但元素类型不同，不是同一类型
• a和c元素类型但数组长度不同，不是同一类型

1.2 赋值

数组类型的赋值会拷贝整个数组，若将大型数组作为参数应使用指针类型，以减小性能损耗。

2. 切片

切片的数据结构可以由reflect.SliceHeader表示：

type SliceHeader struct {
	Data uintptr
	Len  int
	Cap  int
}

• Data：指向底层数组

切片的赋值，不会拷贝底层数组，而是拷贝其指针，此时新旧切片会指向同一数组。

golang slice

3. 操作

3.1 copy

hpg-slice

3.2 append

hpg-slice

• append 之后长度小于等于容量，则利用底层数组的剩余空间
• append 之后长度大于容量，则进行扩容，将新旧数据拷贝过去； 若能预先知道容量，则能够减少扩容次数以提升性能

3.3 delete

hpg-slice

删除切片的某个元素之后，需要将后序元素向前移动一位，时间复杂度为 O(n)

3.4 delete (GC)

hpg-slice

将删除的元素置空，方便GC

3.5 insert

hpg-slice

在某个位置添加一个元素后，将该位置后面的元素再 append 回去。复杂度为 O(N)。

3.6 filter

hpg-slice

3.7 push

hpg-slice

在末尾追加元素，不考虑内存拷贝的情况，复杂度为 O(1)。

hpg-slice

在头部追加元素，时间和空间复杂度均为 O(N)。

3.8 pop

hpg-slice

尾部删除元素，复杂度 O(1)

hpg-slice

头部删除元素，复杂度为 O(1)。

需要注意的是，底层数组没有发生改变，第 0 个位置的内存仍旧没有释放。如果有大量这样的操作，头部的内存会一直被占用。

4. 性能陷阱

4.1 大量内存得不到释放

若在现有的 slice 上进行 re-slice 操作获取新的切片，不会创建新的底层数组，而是新切片直接指向原数组。

若频繁的进行 re-slice 操作，可能出现底层数组占用非常大的内存，而切片只引用其中的一小部分，并且数组无法被 GC 回收，造成内存浪费。

故因使用 copy 来取代 re-slice 操作。

func getLastElemsUsingReslice(a []int, n int) []int {
	return a[len(a)-n:]
}

func getLastElemsUsingCopy(a []int, n int) []int {
	res := make([]int, n)
	copy(res, a[len(a)-n:])
	return res
}

• getLastElemsUsingReslice：通过 re-slice 方式获取最后 n 个元素
• getLastElemsUsingCopy：通过 copy 方式获取最后 n 个元素

进行测试：

func printMem(t *testing.T) {
	t.Helper()
	var mstat runtime.MemStats
	runtime.ReadMemStats(&mstat)
	t.Logf("%.2f MB", float64(mstat.Alloc)/1024./1024.)
}

func TestGetSlice(t *testing.T) {
	tests := []struct {
		name string
		f    func([]int, int) []int
	}{
		{name: "UsingReslice", f: getLastElemsUsingReslice},
		{name: "UsingCopy", f: getLastElemsUsingCopy},
	}

	for _, tt := range tests {
		t.Run(fmt.Sprintf("%-20s", tt.name), func(t *testing.T) {
			var res [][]int
			for i := 0; i < 100; i++ {
				nums := genSliceWithCap(128 * 1024)
				res = append(res, tt.f(nums, 2))
			}
			printMem(t)
		})
	}
}

• t.Helper()：标识当前函数为辅助函数，当打印测试信息时（如文件，代码行位置）时会跳过辅助函数
• runtime.ReadMemStats(*runtime.MemStats)：读取当前的内存分配信息

=== RUN   TestGetSlice/UsingReslice________
    slice_test.go:42: 100.21 MB
=== RUN   TestGetSlice/UsingCopy___________
    slice_test.go:42: 3.22 MB

可以看出使用 reslice 操作之后，存在切片对原数组的引用时，原数组无法回收导致大量的内存占用。

若在测试中，手动调用 runtime.GC() 启动 GC，此时差距就更加的明显：

func TestGetSlice(t *testing.T) {
	tests := []struct {
		name string
		f    func([]int, int) []int
	}{
		{name: "UsingReslice", f: getLastElemsUsingReslice},
		{name: "UsingCopy", f: getLastElemsUsingCopy},
	}

	for _, tt := range tests {
		t.Run(fmt.Sprintf("%-20s", tt.name), func(t *testing.T) {
			var res [][]int
			for i := 0; i < 100; i++ {
				nums := genSliceWithCap(128 * 1024)
				res = append(res, tt.f(nums, 2))
				runtime.GC()
			}
			printMem(t)
		})
	}
// output
=== RUN   TestGetSlice/UsingReslice________
    slice_test.go:43: 100.21 MB
=== RUN   TestGetSlice/UsingCopy___________
    slice_test.go:43: 0.22 MB    

Reference

1. https://geektutu.com/post/hpg-slice.html

2. https://stackoverflow.com/questions/39194816/how-to-wrap-golang-test-functions

3. https://ueokande.github.io/go-slice-tricks/