一篇文章彻底弄懂理解和高效运用切片(slice)

九路 等级 159 1 0

slice,中文多译为“切片”,是 Go 语言在数组之上提供的一个重要的抽象数据类型。在 Go 语言中,绝大多数需要使用数组的场合,切片都实现了完美替代。并且和数组相比,切片提供了更通用、功能更强大且便捷的数据序列访问接口。

1. 切片究竟是什么

在对切片一探究竟之前,我们先来简略了解一下 Go 语言中的数组。

Go 语言数组是一个固定长度的、容纳同构类型元素的连续序列。因此 Go 数组类型具有两个属性:元素类型和数组长度。但凡这两个属性相同的数组类型是等价的。比如下面变量 a、b、c 对应的数组类型是三个不同的数组类型:

var a [8]int 
var b [8]byte
var c [9]int 

变量 a、b 对应的数组类型长度属性相同,但元素类型不同(一个是 int,一个是 byte);变量 a、c 对应的数组类型的元素类型相同,都是 int,但数组类型的长度不(一个是 8,一个是 9)。

Go 的数组是值语义,这意味着一个数组变量表示的是整个数组,这点与 C 语言完全不同。在 C 语言中,数组变量可视为指向数组第一个元素的指针。因此,在 Go 语言中传递数组是纯粹的值拷贝,对于元素类型 Size 较大或元素个数较多的数组,如果直接以数组类型参数传递到函数中会有不小的性能损耗。这时很多人会使用数组指针类型来定义函数参数,然后将数组地址传进函数,这样做的确可以避免性能损耗,但这是 C 语言的惯用法,在 Go 语言中,更地道的方式是使用切片。

切片之于数组就像是文件描述符之于文件。在 Go 语言中,数组更多是“退居幕后”,承担的是底层存储空间的角色;而切片则走向“前台”,为底层的存储(数组)打开了一个访问的“窗口”。

image

因此,我们可以称切片是数组的“描述符”。切片之所以能在函数参数传递时避免较大性能损耗也是因为它是“描述符”的特性,切片这个描述符是固定大小的,无论底层的数组元素类型有多大和切片打开的窗口长度有多长。

下面是切片在 Go 运行时(runtime)层面的内部表示:

//$GOROOT/src/runtime/slice.go

type slice struct {
        array unsafe.Pointer
        len   int
        cap   int
}

我们看到每个切片包含三个字段:

  • array:是指向下层数组某元素的指针,该元素也是切片的起始元素;
  • len:是切片的长度,即切片中当前元素的个数;
  • cap:是切片的最大容量,cap >= len。

在运行时中,每个切片变量都是一个 runtime.slice 结构体的实例。我们用下面语句创建一个 slice 实例:

s := make([]byte, 5)

下面的图展示了切片的内部表示:

image

我们看到通过上述语句创建的切片,编译器会自动为切片建立一个底层数组,如果没有在 make 中指定 cap 参数,那么 cap = len,即编译器建立的数组长度为 len。

我们还可以创建对已存在数组进行操作的切片,这种语法 u[low:max] 称为数组的切片化:

u := [10]byte{11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
s := u[3:7]

我们看到切片 s 为我们打开了一个操作数组 u 的窗口,我们通过 s 看到的第一个元素是 u[3],我们通过 s 能看到并操作的数组元素为 4 个(max-low)。切片的 cap 值取决于底层数组的长度。我们看到从切片 s 的第一个元素 s[0],即 u[3] 到数组末尾一共有 7 个元素,因此切片 s 的 cap 为 7。

我们可以为一个已存在数组建立多个操作数组的切片。

image

我们看到既然上图中的三个切片 s1、s2、s3 都是数组 u 的“描述符”,那么无论通过哪个切片对数组进行的修改操作都会反映到其他切片中。比如:将 s3[0] 置为 24,那么 s1[2] 也会变成 24,因为 s3[0]直接操作的是底层数组 u 的第四个元素 u[3]。

当切片作为函数参数传递给函数时,实际传递的就是切片的内部表示,也就是上面的 runtime.slice 结构体实例,因此无论切片“描述”的底层数组有多大,切片作为参数传递带来的性能损耗都是小到可以忽略不计的。这就是为什么函数在参数中多使用切片而不用数组指针的原因之一。当然另外一个原因就是切片可以提供比指针更为强大的功能,比如下标访问、边界溢出校验、动态扩容等。指针本身在 Go 语言中的功能也受到的限制,比如不支持指针算术运算。

2. 切片的高级特性:动态扩容

如果仅仅是提供通过下标值来操作元素的类数组操作接口,那么切片就不会在 Go 中占据重要的位置。Go 切片还支持一个重要的高级特性:动态扩容。尽量定义零值可用的类”一节中我们提到过切片类型是“部分”满足零值可用理念的,即零值切片也可以通过 append 预定义函数进行元素赋值操作:

var s []byte // s被赋予零值nil
s = append(s, 1) 

由于初值为零值,s 这个“描述符”并没有绑定对应的底层数组。而经过 append 操作后,s 显然已经“绑定”了属于它的底层数组。为了方便查看切片是如何动态扩容的,我们打印出每次 append 后的 s 的 len 和 cap 值:

// slice_append.go
var s []int  // s被赋予零值nil
s = append(s, 11) 
fmt.Println(len(s), cap(s)) //1 1
s = append(s, 12) 
fmt.Println(len(s), cap(s)) //2 2
s = append(s, 13) 
fmt.Println(len(s), cap(s)) //3 4
s = append(s, 14) 
fmt.Println(len(s), cap(s)) //4 4
s = append(s, 15) 
fmt.Println(len(s), cap(s)) //5 8

我们看到 s 的 len 值是线性增长的,但 cap 值却呈现出不规则的变化。通过下图我们可以更容易看清楚多次 append 操作究竟是如何让 slice 进行动态扩容的。

image

我们看到 append 会根据 slice 对底层数组容量的需求对底层数组进行动态调整:

  • 最初 s 初值为零值(nil),此时 s 没有“绑定”底层数组;
  • 通过 append 操作向切片 s 添加一个元素 11,此时 append 会首先分配底层数组 u1(数组长度 1),然后将 s 内部表示中的 array 指向 u1,并设置 len = 1, cap = 1;
  • 通过 append 操作向切片 s 再添加一个元素 12,此时 len(s) = 1,cap(s) = 1,append 判断底层数组剩余空间不足以满足添加新元素的要求,于是创建了一个新的底层数组 u2,长度为 2(u1 数组长度的 2 倍),并将 u1 中的元素拷贝到 u2 中,最后将 s 内部表示中的 array 指向 u2,并设置 len = 2, cap = 2;
  • 通过 append 操作向切片 s 再添加一个元素 13,此时 len(s) = 2,cap(s) = 2,append 判断底层数组剩余空间不足以满足添加新元素的要求,于是创建了一个新的底层数组 u3,长度为 4(u2 数组长度的 2 倍),并将 u2 中的元素拷贝到 u3 中,最后将 s 内部表示中的 array 指向 u3,并设置 len = 3, cap 为 u3 数组长度,即 4 ;
  • 通过 append 操作向切片 s 再添加一个元素 14,此时 len(s) = 3, cap(s) = 4,append 判断底层数组剩余空间可以满足添加新元素的要求,于是将 14 放在下一个元素的位置(数组 u3 末尾),并将 s 内部表示中的 len 加 1,变为 4;
  • 通过 append 操作向切片 s 添加最后一个元素 15,此时 len(s) = 4,cap(s) = 4,append 判断底层数组剩余空间不足以满足添加新元素的要求,于是创建了一个新的底层数组 u4,长度为 8(u3 数组长度的 2 倍),并将 u3 中的元素拷贝到 u4 中,最后将 s 内部表示中的 array 指向 u4,并设置 len = 5, cap 为 u4 数组长度,即 8。

我们看到 append 会根据 slice 的需要,在当前底层数组容量无法满足的情况下,动态分配新的数组,新数组长度会按一定规律扩展(这里针对元素是 int 型的数组,新数组的容量为当前数组的 2 倍。其他类型的扩展系数可能有所不同),新数组建立后,append 会把旧数组中的数据 copy 到新数组中,之后新数组便成为了 slice 的底层数组,旧数组会被垃圾回收掉。

append 操作有些时候会给 Gopher 带来一些困惑,比如通过语法 u[low:max] 形式进行数组切片化而创建的切片,一旦切片 cap 触碰到数组的上界,再对切片进行 append,切片就会和原数组的解除“绑定”:

package main

import "fmt"

func main() {
        u := []int{11, 12, 13, 14, 15}
        fmt.Println("array:", u) // [11, 12, 13, 14, 15]
        s := u[1:3]
        fmt.Printf("slice(len=%d, cap=%d): %v\n", len(s), cap(s), s) // [12, 13]
        s = append(s, 24)
        fmt.Println("after append 24, array:", u)
        fmt.Printf("after append 24, slice(len=%d, cap=%d): %v\n", len(s), cap(s), s)
        s = append(s, 25)
        fmt.Println("after append 25, array:", u)
        fmt.Printf("after append 25, slice(len=%d, cap=%d): %v\n", len(s), cap(s), s)
        s = append(s, 26)
        fmt.Println("after append 26, array:", u)
        fmt.Printf("after append 26, slice(len=%d, cap=%d): %v\n", len(s), cap(s), s)

        s[0] = 22
        fmt.Println("after reassign 1st elem of slice, array:", u)
        fmt.Printf("after reassign 1st elem of slice, slice(len=%d, cap=%d): %v\n", len(s), cap(s), s)
}

运行这段代码,我们得到如下结果:

array: [11 12 13 14 15]
slice(len=2, cap=4): [12 13]
after append 24, array: [11 12 13 24 15]
after append 24, slice(len=3, cap=4): [12 13 24]
after append 25, array: [11 12 13 24 25]
after append 25, slice(len=4, cap=4): [12 13 24 25]
after append 26, array: [11 12 13 24 25]
after append 26, slice(len=5, cap=8): [12 13 24 25 26]
after reassign 1st elem of slice, array: [11 12 13 24 25]
after reassign 1st elem of slice, slice(len=5, cap=8): [22 13 24 25 26]

我们看到当 append 25 之后,切片的元素已经触碰到了底层数组 u 的边界;此后再 append 26 后,append 发现底层数组已经无法满足 append 的要求,于是新创建了一个底层数组(数组长度为 cap(s)的 2 倍,即 8),并将 slice 的元素拷贝到新数组中了。这之后,我们即便再修改 slice 的第一个元素值,原数组 u 的元素也没有发生任何改变了,因为此时切片 s 与数组 u 已经解除了“绑定关系”,s 已经不再是数组 u 的“描述符”了。

3. 尽量使用 cap 参数创建 slice

我们看到 append 操作是一并利器,它让 slice 类型部分满足了“零值可用”的理念。但从 append 的原理中我们也能看到重新分配底层数组并拷贝元素的操作代价还是蛮大的,尤其是当元素较多的情况下。那么如何减少或避免为过多内存分配和拷贝付出的代价呢?一种有效的方法就是根据 slice 的使用场景在为新创建的 slice 赋初值时使用 cap 参数。

s := make([]T, 0, cap)

下面是一个使用 cap 和不使用 cap 参数的 slice 的基准测试:

package main

import "testing"

const sliceSize = 10000

func BenchmarkSliceInitWithoutCap(b *testing.B) {
        for n := 0; n < b.N; n++ {
                sl := make([]int, 0)
                for i := 0; i < sliceSize; i++ {
                        sl = append(sl, i)
                }
        }
}

func BenchmarkSliceInitWithCap(b *testing.B) {
        for n := 0; n < b.N; n++ {
                sl := make([]int, 0, sliceSize)
                for i := 0; i < sliceSize; i++ {
                        sl = append(sl, i)
                }
        }
}

下面是基本测试运行的结果(go 1.12.7,macbook pro i5 8 核,16G 内存):

goos: darwin
goarch: amd64
BenchmarkSliceInitWithoutCap-8          50000         36484 ns/op      386297 B/op          20 allocs/op
BenchmarkSliceInitWithCap-8            200000          9250 ns/op       81920 B/op           1 allocs/op
PASS
ok      command-line-arguments    4.163s

通过结果我们看到,使用 cap 参数创建的 slice 进行 append 操作的平均性能(9250ns)是不带 cap 参数的 slice(36484ns)的 4 倍左右,并且每操作平均仅需一次内存分配。

因此,如果可以预估出切片底层数组需要承载的元素数量,强烈建议在创建 slice 时带上 cap 参数。

4. 小结

切片是 Go 语言提供的重要数据类型,也是 Gopher 日常 Go 编码是最常使用的类型之一。切片是数组的“描述符”,在大多数场合替代了数组,并减少了数组指针作为函数参数的使用。

append 在切片上的运用让切片类型部分支持了零值可用的理念,并且 append 对 slice 的动态扩充将 Gopher 们从手工管理底层存储的工作中解放了出来。

在可以预估出元素容量的前提下,使用 cap 参数创建 slice 可以提升 append 的平均操作性能,减少或消除因动态扩容带来的性能损耗。

预览图
收藏
评论区