golang slice internal

golang, programming

golang slice internal

说到 slice 首先绕不开的话题是 array. array 是 go 中的一个基本类型，他拥有两个属性，一个是长度，另一个是实际的数据。和 C 类似，array 的长度在编译期就需要确定，或者说，不同的长度和变量类型的组合可以看作不同的 array 的类型，比如 [4]int, [10]int64, [5]interface{} 都是不同类型的 array. 不同于 C 的是，这里的 array 不是 pointer，他就是一个 value, 在函数传参过程中会被完整的拷贝，我们可以将其理解成一个 struct value, 如 Go Slices: usage and internals 描述的：

Go’s arrays are values. An array variable denotes the entire array; it is not a pointer to the first array element (as would be the case in C). This means that when you assign or pass around an array value you will make a copy of its contents. (To avoid the copy you could pass a pointer to the array, but then that’s a pointer to an array, not an array.) One way to think about arrays is as a sort of struct but with indexed rather than named fields: a fixed-size composite value.

下一个绕不开的话题是 array 的初始化，尽管 go 中提供了不同的初始化方法，但是我们仍然秉承 KISS 原则，介绍两种最常用的方法

1
2
3
4
// 1. ready-to-use, elements will be init to "zero" in certain context
var a [2]int
// 2. array literal
b := [2]int{99, 23}

下面我们可以进入 slice 的领域了，正如上文所述的，array 有点笨，又要提前确定长度，还不能看成指针，显得过于死板。而 slice 也是 go 的一个基础类型，它基于 array 之上，提供了动态长度，传参不拷贝等功能，他才是我们在 go 语言中经常见到的 container 类型。不同于 array 的类型，slice 的类型中不含有长度，只有 element 类型，表现为 []int, []float64, []interface{}. 我们也来看看 slice 常用的五种初始化方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 1. nil slice, len=0, cap=0, still ready-to-use with append, len, cap
var a []int
// 2. initialized slice with given value, len=5, cap=5
b := []int{1, 2, 3, 4, 5}
// 3. initialized slice with "zero", len=5, cap=10
c := make([]int, 5, 10)
//    empty slice, len=0, cap=0
d := make([]int, 0)
// 4. create from array
aa := [4]int{1, 2, 3, 4}
e := aa[1:3]
// 5. create from other slice, len=2, cap=4
f := b[1:3]

var a []int 和 d := make([]int, 0) 看起来都是创建了一个 len=0, cap=0 的 slice 但是他们有本质区别，a==nil 为 true, 和 d==nil 为 false, 所以我们将其区别为 nil slice 和 empty slice, 我们将在后文在详述二者的区别，我们先来看看 len 和 cap 是什么. 对于一个 slice 来说，我们可以用内置函数 len(a) 以及 cap(a) 来得到其 length 和 capacity, 注意这里的 length 和 array 的 length 不同，这里是一个运行时的概念。那么为什么还有 capacity 呢？因为 slice 是基于 array 之上的，它可以被视为

a descriptor of an array segment. It consists of a pointer to the array, the length of the segment, and its capacity (the maximum length of the segment)

slice 包括对 array 的一个指针，一段 segment 的长度，以及可供 slice 扩展的 segment 的最大长度。这也就能解释为什么传参一个 slice 不会造成数组元素的拷贝，因为我们仅仅复制了指向数组的一个指针。此时我们也能看到 a 和 d 的区别，a 内部的 pointer 并没有指向任何数组，而 d 内部指向了一个长度为0的数组. 仅仅看前三种初始化方法，似乎 len 和 cap 传达了同样的信息，即所指数组的元素数目，但别忘了我们还有第五种初始化方法，也就是 create from other slice, 此时 len 和 cap 就会产生差异。

go 支持类似 python 的切片语法，譬如 f := b[1:3], 那么一个正常的语义显然是 b 的长度变为2，但此时其指向的数组长度变成了4（如果你对 C 很熟悉，你应该会懂我在说什么），所以 f 的 len 为 2, 而 cap 为 4. 注意，f 的 cap 为 4 并不意味其下标可以访问到3，下标的访问以及 for range 仍由 len 决定。值得一提的是，此时 f 内部指针指向了 f, b 共同 array 的 1th 元素，亦即 f, b 底部的数组是一致的，所以对 f 的任何操作也会同时影响到 b.

尽管下标访问不能超过 len, 但是正如 capacity 的定义 the maximum length of the segment, 一个 slice 可以重新被 re-slice 到其最大长度，f = f[:cap(f)] 后 len(f)=4, cap(f)=4. 但是我们不能超出 capacity 的范围，比如 b[:100] 会造成 runtime panic, 我们也不能用负数来 slice，f[-1:cap(f)] 是非法的，re-slice 是一个单方向买卖。

从上面的描述来看，slice 的 capacity 是一个一锤子买卖，因为不管 slice 怎么玩，其下的 array 都是定死的，而 array 本身就有长度。所以想增加 slice 的 capacity 唯一的方法就是创建一个更大的 cap 的 slice, 然后把原先 slice 的数据拷贝过去. 这实际上就是 append 函数在某些条件下做的事情，所以不要过于依赖 append, 在 capacity 需要增长的 append 下执行效率会很低，涉及大量的拷贝。如果我们自己有拷贝 slice 的需求，也尽量用 内置的 copy 函数，一方面代码简洁，另一方面 copy 可以帮我们 handle 两个 slice 有 overlap 的场景。

1
2
3
a := []int{1}  // len=1, cap=1
a = append(a, 2, 3, 4) // len=4, cap=4
a = append(a, 5, 6) // len=6, cap=8

在 cap 不够的情况下 append 会创建新的 slice(基础的 array 是重新分配的)，但是 cap 够的情况下，append 实际上直接对 slice 进行下标赋值并返回，此时会造成底部 array 的变动，可能会出现我们意想不到的副作用：

1
2
3
4
5
6
7
8
9
                    //    len,  cap,  elements
a := []int{1}       //    1,    1,    [1]
a = append(a, 2, 3) //    3,    4,    [1, 2, 3]  
b := a[:2]          //    2,    4,    [1, 2]
b = append(b, 233)  // b: 3,    4,    [1, 2, 233]
                    // a: 3,    4,    [1, 2, 233] affected by append!
a = append(a, 5, 6) //    5,    8,    [1, 2, 233, 5, 6]
b[0] = 233          // b: 3,    4,    [233, 2, 233]
                    // a: 5,    8,    [1, 2, 233, 5, 6] not affected!

想要避免这种 subtlety 一个可用的 trick 是 full slice expression. a[low : high : max] 最终 slice 的 capcity 为 max-low. 通过指定 max 使得 slice 下一个 append 一定触发内存的重新分配:

1
2
3
4
5
6
                    //    len,  cap,  elements
a := []int{1}       //    1,    1,    [1]
a = append(a, 2, 3) //    3,    4,    [1, 2, 3]  
b := a[:2:2]          //    2,    4,    [1, 2]
b = append(b, 233)  // b: 3,    4,    [1, 2, 233]
                    // a: 3,    4,    [1, 2, 3] not affected by append!

总结一下，在 golang 中我们可以用 slice 来充当一个支持 re-slice, 无拷贝传参，动态长度的数组，slice 内部包含了对 array 的指针，re-slice 的过程就是对指针的操作 + length 的语义限制

简单来说：

  • slice = pointer to array + length + capacity
  • re-slice = pointer 移动 + length 语义限制
  • append = 原地址赋值 if len < capacity else 重新分配内存

总的来说，我们也能同时总结出一些编程时需要注意的点：

  • re-slice, slice 作为函数参数是两个高效操作

  • slice 会导致对底层 array 的引用，GC 就不会回收这个 array, 可能出现一个 tiny slice on top of a huge array 的情况，导致资源的浪费。

  • 利用 copy 函数进行两个 slice 的批量拷贝

  • re-slice 后牢记指向的数组是同一个数组

  • append 可能涉及大量的拷贝以及意想不到的副作用

    • 如果 capacity 足以容纳待 append 的元素，那么返回的 slice 和传入 slice 指向同一个数组
    • 否则，返回的 slice 指向的数组是一个新的数组

  • s = s[0:0] 是一个常用用法，我们可以获得一个 len=0, cap 不变的 slice, 此时进行 append 操作是高效的；

  • links