go-slice

数组是面向过程的编程语言里最重要的概念之一。

一、翻车现场

在短暂的 Go 语言学习使用中，已经连续两次踩进了下面这个坑

1
2
3
4
5
6
7
8
9
vals := make([]int, 5)
for i := 0; i < 5; i++ {
  vals = append(vals, i)
}
fmt.Println(vals)
// Playground: https://play.golang.org/p/7PgUqBdZ6Z

输出结果是 [0 0 0 0 0 0 1 2 3 4]

回顾一下翻车现场：

  1. 开始是通过 var vals []int 来进行变量声明

  2. 后续逻辑开发完成，自测完成，一切 ok，发布上线，一切 ok

  3. 某天在项目里跑了一下 golangci-lint，发现了一吨报错，其中有：

1
2
3
Consider preallocating `vals` (prealloc)
        var vals []int
        ^

  1. 遂修改为 vals := make([]int, 5)，再改完那一吨报错，基本都是关于写法的修正，lint 不再报错，提交发布

  2. 线上，Duang💥💥💥（看用在哪里啦。。很有可能也不会💥，只会是一个隐秘的 Bug）

挺刺激的。第一次遇到这个问题的时候其实已经有个印象不能这么声明 slice，再 append 了，但还是被打的不够疼，又有了第二次。

所以还是来学习理解一下具体是怎么回事吧。

二、Array vs Slice

Go 语言中有数组 array，也有切片 slice。二者有很多区别，但是本次想讨论的主要是，array 的大小是固定的且不会改变，其 length 就是其类型的一部分，而 slice 的大小是动态变化的，因为 slice 是 array 的 wrapper。

1
2
aArray := [2]string{"Tom", "Jerry"}
fmt.Printf("%T\n", aArray) // Print "[2]string"

所以说，声明一个数组：var a [10]int a 的大小就已经固定，不会改变。调用 len(a) 的结果永远为 10。如果想要再向数组里添加、删除任何元素，都必须要重新声明一个新的类型。

这种固定大小的数组设计在某些场景下是非常有用的（官方文档的举例是矩阵变换），但是大多数情况下，工程中还是需要一个可变大小可增删的数组容器。而这就是设计 Slice 的原因。

切片 Slice 是基于数组实现的，它描述了数组的一个连续片段，所以叫切片还是很生动形象的。切片其实就是动态数组，它的长度并不固定，可以追加元素并会在切片容量不足时进行扩容。

img

如上图，Slice 的结构本质上是：

1
2
3
4
5
type SliceHeader struct {
    Ptr uintptr
    Len  int
    Cap  int
}

Ptr 作为一个指针指向数组的第一个元素，其实就是指向一片连续的内存空间，这片内存空间可以用于存储切片中保存的全部元素，数组其实就是一片连续的内存空间，数组中的元素只是逻辑上的概念，底层存储其实都是连续的，所以我们可以将切片理解成一片连续的内存空间加上长度与容量标识。

Length 是 slice 中所包含的元素个数，而Capacity则记录了其底层数组的大小（从切片指针引用的元素开始，直到底层数组的最后一个元素）。因此，必然会有 Capacity >= Length 。试图把切片扩展到超出容量就会和访问超出数组/切片范围的索引一样，导致 panic。

因此如果我们声明 slice := iBuffer[0:0]，其 header 则为：

1
2
3
4
5
slice := SliceHeader{
    Len:  0,
    Cap:  10,
    Ptr: &iBuffer[0],
}

引入 slice header 的这个概念非常有助于理解 slice 的特点和一些坑。

再来看看几种声明 slice 的方式：

1
2
3
4
5
6
7
8
9
// 字面量
letters := []string{"a", "b", "c", "d"}
// make
func make([]T, len, cap) []T
s := make([]byte, 5)
// re-slice
s = s[2:4]

第三种 re-slice 方式并没有拷贝原 slice 中的数据，它只是创建了一个新的切片，并将其指针指向同一个底层数组。

如果更改了 slice 中某些元素的值，实际上是在改变 slice 所指向的数组元素的值。因此，在下面这种通过 re-slice 生成了子切片，又通过索引修改元素值的行为，会导致所有指向这个底层数组的 slice 的值都发生改变。即 Slice 的结构会导致多个 slice 实际引用的是同一个数组，要谨慎修改 slice 中元素的值。

1
2
3
4
5
6
7
foo = make([]int, 5) // 被初始化为 [0 0 0 0 0]
foo[3] = 42
foo[4] = 100
bar  := foo[1:4]
bar[1] = 99
fmt.Println(foo) // [0 0 99 42 100]
fmt.Println(bar) // [0 99 42]

修改 Slice 中元素的值与 header

修改这两者的方法并不一样。

Example1: 将 slice 作为参数传入函数，修改 slice 中元素的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func AddOneToEachElement(slice []) {
    for i := range slice {
        slice[i]++
    }
}
func main() {
    slice := make([]int, 5)
    fmt.Println("before", slice)
    AddOneToEachElement(slice)
    fmt.Println("after", slice)
}
// before [0 0 0 0 0]
// after [1 1 1 1 1]

修改成功。虽然作为函数参数所传递的只是 slice 的值，但是其实在函数中我们所操作修改的是指向同一底层数组的 newSlice，底层数组的元素被修改，因此当函数执行完毕，修改后的元素值可由原 slice 访问到。

Example2: 将 slice 作为参数传入函数，修改 slice 的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func SubtractOneFromLength(slice []int) []int {
    slice = slice[0 : len(slice)-1]
    return slice
}
func main() {
    slice := make([]int, 5)
    fmt.Println("Before: len(slice) =", len(slice))
    newSlice := SubtractOneFromLength(slice)
    fmt.Println("After:  len(slice) =", len(slice))
    fmt.Println("After:  len(newSlice) =", len(newSlice))
}
// Before: len(slice) = 5
// After:  len(slice) = 5
// After:  len(newSlice) = 4

储存在 slice header 中的 length 属性并不会被函数修改，传入函数的只是其拷贝。 如果我们想通过一个函数来修改 slice 的 header 的话，必须通过把修改过的返回结果重新赋值给待修改的 slice。

Example3: 将 slice 的指针作为参数传入函数，修改其 header

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func PtrSubtractOneFromLength(slicePtr *[]int) {
	slice := *slicePtr
	*slicePtr = slice[0 : len(slice)-1]
}
func main() {
	slice := make([]int, 5)
	fmt.Println("Before: len(slice) =", len(slice))
	PtrSubtractOneFromLength(&slice)
	fmt.Println("After:  len(slice) =", len(slice))
}
// Before: len(slice) = 5
// After:  len(slice) = 4

三、Append

内置的 append方法有这几个功能特点：

  1. 向 slice 附加一个或多个元素
  2. 分配足够大的 slice （如果 append 后的长度超出了现有的容量）
  3. 总会成功，除非机器内存耗光
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 这是官方实现的用来说明功能特性的版本，并不是源码
// Append appends the elements to the slice.
// Efficient version.
func Append(slice []int, elements ...int) []int {
    n := len(slice)
    total := len(slice) + len(elements)
    if total > cap(slice) {
        // Reallocate. Grow to 1.5 times the new size, so we can still grow.
        // 一次分配更多的内存通常都比多次分配少量内存的开销更小且速度更快
        newSize := total*3/2 + 1
        newSlice := make([]int, total, newSize)
        copy(newSlice, slice)
        slice = newSlice
    }
    slice = slice[:total]
    copy(slice[n:], elements)
    return slice
}

四、回顾一下翻车现场

回到我们一开始演示翻车现场的代码示例：

1
2
3
4
5
vals := make([]int, 5)
for i := 0; i < 5; i++ {
  vals = append(vals, i)
}
fmt.Println(vals)

在声明 vals 的时候，把它的 length 和 capacity都设置为5，它被初始化为空值 slice : [0 0 0 0 0]，再进行 append 操作，它假设我们是想在初始的 5 个元素后添加新元素，因此得到的结果是 [0 0 0 0 0 0 1 2 3 4]。

那在 golang-lint 要求我们必须通过 prealloc 的方式初始化 vals，或是我们为了避免每个循环中都 re-allocate 造成的过大开销，或是我们并不能确定执行append 后的切片大小的情况下，要怎么避免这种翻车情况呢？

有两种方式：

1. 直接通过索引对切片元素赋值（只针对遍历操作后的数组大小已知的情况）

1
2
3
4
5
vals := make([]int, 5)
for i := 0; i < 5; i++ {
  vals[i] = i
}
fmt.Println(vals)

这种方案并不难理解。

2. 设置长度为 0，指定切片的 Capacity

并不是所有场景下我们都可以精确一一对应到每个索引下该存储的元素是什么，比如说：

1
2
3
4
5
6
vals := make([]int, 5)
for i := 0; i < 5; i++ {
  items := getItems(i)
  vals = append(vals, items...)
}
fmt.Println(vals)

每次将一个不定长度的 slice 铺平追加到切片，最终得到的切片的长度无法提前确定。

那只能通过设置长度为 0，指定切片的容量来解决了。即：

1
2
3
4
5
6
vals := make([]int, 0, 5)
for i := 0; i < 5; i++ {
  items := getItems(i)
  vals = append(vals, items...)
}
fmt.Println(vals)

当然我们初始化时指定的容量5很有可能比最终切片长度小，循环过程中还是会发生 re-allocate，但这样已经避免了前面的翻车现场，也减少了 re-allocate 次数，可以作为这种场景下的折中解决方案了。

参考文档