Go中Slice性能与技巧

一个数组中的所有元素均存放在此数组的直接部分,一个切片的所有元素均存放在此切片的间接部分。

slice是Go语言中一个重要的数据类型,而且很好用,但是也有一些坑,需要我们对slice有深入的理解。

slice跟数组array很类似,可以使用下标进行访问,如果越界则会产生panic。

1、slice到底是个啥

为了更好地理解切片类型和和切片值,我们需要对切片内部结构有一个基本的认识。在Go语言中,切片类型的内部定义大致如下:

1
2
3
4
5
6
// runtime/slice.go
type slice struct {
  array unsafe.Pointer  // 引用着底层存储在间接部分上的元素
  len   int             // 长度
  cap   int             // 容量
}

通过定义我们可以看到slice有三个属性,分别:

  • 指针:指向底层数据
  • 长度:表示此切片当前元素的个数
  • 容量:表示底层数组元素的个数,容量>=长度

注意:底层数组array可以被多个slice引用,所以对一个slice的元素进行操作,可能会影响到其他slice。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7}
	s1 := a[:4]
	s2 := a[1:2]
	fmt.Printf("a %d\n", a)    // [1,2,3,4,5,6,7]
	fmt.Printf("s1 %d\n", s1)  // [1,2,3,4]
	fmt.Printf("s2 %d\n", s2)  // [2]
	s2 = append(s2, 50)
	fmt.Printf("a %d\n", a)    // [1,2,50,4,5,6,7]
	fmt.Printf("s1 %d\n", s1)  // [1,2,50,4]
	fmt.Printf("s2 %d\n", s2)  // [2, 50]
}

因为s1和s2共享底层数据,所以对s2进行追加操作,影响了底层数组a[2]位置上的元素,导致a[2], s1[2]都变成了50。

由此可以发现:

1)slice 的底层数据就是数组,slice是对数组的封装,描述一个数组的片段

2)slice 和 array 都可以通过下标访问

3)slice 更加灵活,可以动态扩容

2、slice的创建

创建slice有几种方式:

1,直接声明

1
var s []int

2,通过make内置函数,函数定义如下

1
func make([]T, len, cap) []T

第一个参数是[]T,T表示元素类型,第二个参数是长度len,即初始化的切片拥有多少个元素,第三个参数是容量cap,容量是可选参数,默认等于长度,即指定切片的容量。

容量是当前切片已经预分配的内存能够容纳的元素个数,如果不断想切片中增加元素,超过了当前切片的容量,就需要分配新的内存,将当前切片所有的元素拷贝到新的内存上,这就是扩容。

1
2
// 创建[]int切片,指定长度为0, 容量为1024
s := make([]int, 0, 1024)

3,字面量

1
s := []int{1,2,3,4}

4,从切片或者数组中截取

1
s = a[:len(a)]

3、slice的操作

3.1 Copy

1
2
b := make([]T, len(a))
copy(b, a)  // 将a中所有元素拷贝到b中

当然也可以使用下面的方式

1
2
b = append([]T(nil), a...)
b = append(a[:0:0], a...)

3.2 Append

1
b = append(b, a...)

append有两个场景:

  • 当append之后的长度小于等于容量时,直接利用此此切片原有的底层数组
  • 当append之后的长度大于容量时,则会分配更大的内存来存储新的底层数组

3.3 Delete

1
2
3
a = append(a[:i], a[i+1:])   // 删除下标i上的元素
// or
a = a[:i+copy(a[i:], a[i+1:])]

如果不关心切片中原有元素的顺序,也可以这样的删除:

1
2
a[i] = a[len(a)-1]
a = a[:len(a)-1]

注意:如果切片的元素类型是指针或带有指针的结构体,那么将需要垃圾回收,上面的Delete方式会产生内存泄漏,因为部分元素依旧被a引用着,不能够得到释放。下面的代码可以解决这个问题。

1
2
3
copy(a[i:], a[i+1:])
a[len(a)-1] = nil // zero of T
a = a[:len(a)-1]

如果不关心切片中原有元素的顺序,也可以这样的删除:

1
2
3
a[i] = a[len(a)-1]
a[len(a)-1] = nil // zero of T
a = a[:len(a)-1]

3.4 Expand

在位置i插入n个元素:

1
a = append(a[:i], append(make([]T, n), a[i:]...)...)

在尾部插入n个元素:

1
a = append(a, make([]T, n)...)

为了避免因插入n个元素导致内存重新分配,可以提前校验并扩容:

1
2
3
if cap(a) - len(a) < n {
  a = append(make([]T, 0, len(a)+n), a...)
}

3.5 Insert

方式1:

1
a = append(a[i:], append([]T{x}, a[i:]...)...)

注意,以上的插入方式,第二个append实际上创建了一个新的切片,并且拥有自己的底层存储空间,并将a[i:]元素拷贝到次切片;然后再通过第一个append将新切片的元素拷贝到原来a切片的后面。

这种插入方式会产生很多内存垃圾,因为第二个append创建的切片值使用了一次,再没有任何对象引用的时候需要GC回收。

但是,下面的方式2能够很好地避免这种情况

方式2:

s = append(s, 0) // use the zero value of the element type
copy(s[i+1:], s[i:])
s[i] = x

方式2先在后面追加一个零值元素,然后将a[i:]元素拷贝到位置a[i+1],空出a[i]位置,最后对a[i]赋值完成插入操作。

此方式没有产生内存垃圾,更值得推荐

3.6 Filter, in place

1
2
3
4
5
6
7
8
j := 0
for i, v := range a {
  if keep(v) {
    a[j] = v
    j++
  }
}
a = a[:j]

3.7 Push

1
a = append(a, x)

push front

1
a = append([]T{x}, a...)

3.8 Pop

1
2
x := a[len(a)-1]
a = a[:len(a)-1]

pop front

1
2
x := a[0]
a = a[1:]

4 性能陷阱

4.1 部分场景中大量内存得不到释放

在已有的切片上进行切片操作,如果没有超过切片的容量,那么其底层数组就不会发生变化,内存一直占用着。所以很可能出现这样一种情况:原切片有大量的元素,但某个时刻我们在原切片的基础上进行切片,只是用很小的一段,但底层数组在内存中依然占据着很大的内存,得不到释放,从而造成内存浪费。

这种情况下我们可以使用copy替代re-slice确保不再需要的数据能够及时得到释放。

下面我们验证下这个情况:

我们需要两个函数分别以copyre-slice方式取得原切片的最后两个元素;还需要一个随机生产函数,能够产生指定大小的切片;最后通过runtime内置的ReadMemStats获取当前系统运行时所使用的内存大小。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func lastNumsBySlice(origin []int) []int {
	return origin[len(origin)-2:]
}

func lastNumsByCopy(origin []int) []int {
	result := make([]int, 2)
	copy(result, origin[len(origin)-2:])
	return result
}

func randomSlice(n int) []int {
	rand.Seed(time.Now().UnixNano())
	nums := make([]int, 0, n)
	for i := 0; i < n; i++ {
		nums = append(nums, rand.Int())
	}
	return nums
}

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

最后我们还需要两个测试函数:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func testLastNums(t *testing.T, f func([]int) []int) {
	t.Helper()
	ans := make([][]int, 0)
	for k := 0; k < 100; k++ {
		origin := generateWithCap(128 * 1024)
		ans = append(ans, f(origin))
	}
	printMem(t)
	_ = ans
}

func TestLast2NumsBySlice(t *testing.T) {
	testLastNums(t, lastNumsBySlice)
}

func TestLast2NumsByCopy(t *testing.T)  {
	testLastNums(t, lastNumsByCopy)
}

运行结果如下:

1
2
3
4
5
6
=== RUN   TestLast2NumsBySlice
    subond_test.go:20: 100.19 MB
--- PASS: TestLast2NumsBySlice (0.24s)
=== RUN   TestLast2NumsByCopy
    subond_test.go:24: 3.19 MB
--- PASS: TestLast2NumsByCopy (0.22s)

通过结果可以看到两者的差异还是挺大的。虽然切片只使用最后两个元素,但是re-slice的方式获得的新切片被保存在ans中,导致原切片中的元素一直被引用着,无法被释放,因此占用了很多内存;而copy方式得到的新切片拥有自己的底层数组,且只包含2个元素,当原切片不在被引用后,内存能够被及时GC。

如果我们在循环中,显式地调用runtime.GC(),效果更加明显。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func testLastNums(t *testing.T, f func([]int) []int) {
	t.Helper()
	ans := make([][]int, 0)
	for k := 0; k < 100; k++ {
		origin := generateWithCap(128 * 1024)
		ans = append(ans, f(origin))
    runtime.GC()
	}
	printMem(t)
	_ = ans
}

运行结果如下:

1
2
3
4
5
6
=== RUN   TestLast2NumsBySlice
    subond_test.go:21: 100.19 MB
--- PASS: TestLast2NumsBySlice (0.26s)
=== RUN   TestLast2NumsByCopy
    subond_test.go:25: 0.19 MB
--- PASS: TestLast2NumsByCopy (0.22s)

附:推荐与参考