理解 Go 的 Array 和 slice

Table of Contents

今早 磊磊 在 Twitter 上看到一条消息,大致意思是问下面代码的执行结果是什么:

package main

import "fmt"

func four(s []int) {
    s = append(s, 4)
}

func main() {
    s := []int{1, 2, 3}
    four(s)
    fmt.Println(s)
}

可选的结果是:

  1. [1, 2, 3, 4]
  2. [4]
  3. [1, 2, 3]
  4. compile error

乍一看结果是 =[1, 2, 3, 4]=,毕竟向 s 中添加了一个元素。我对 Go 的细节了解不多,所以是按照已有的 C 的 Array 和 C++ 的 vector 的知识来理解 Go 的 slice。 本以为像 Go这样一个比较「先进」的语言,自然会规避这种深浅拷贝的问题,但实际上并没有,所以对这道题有点迷糊。于是就花时间研究了一下 Go 中的 Array 和 Slice。

1 Array

Go 中的 Array 是通过 [n]int 这种样式来声明的,一如数据结构学到的那样,Array 必须是固定长度的。Go 的 Array(我一直拿 C 的 Array 类比)可以理解成一个像 int 一样的内置类型,是一块连续的内存结构,比较好理解。

2 Slice

实际编码过程中, Array 逐渐满足不了需求,比如一个解析 HTTP 请求的 body 体或者从文件读入内容,不好提前知道内容的长度,所以大部分时候都需要变长的 Array 。 slice 就是实现了「可变长度的 Array 」的抽象,类似 C++ 中的 vector。

一个 slice 的实现通常有三部分组成:

  • buffer: 指向实际存数据的 buffer,定长,可以用 Array 来实现
  • len: 当前以使用的 buffer 长度
  • cap: 当前 buffer 的容量,当 len 大于等于 =cap=时,即容量不足,则需要触发扩容:
    1. 重新声明一个足量的 buffer
    2. 把现有的 buffer 内容拷贝过去
    3. 修改 buffer 指向
    4. 修改 cap 的值

C++ 中的 vector 也是类似的实现,只不过它提供了拷贝构造函数(copy contructor),而 Go 没有提供类似的机制。

再回到刚才之前的问题上,当把 s 传递给 four 的时候是一次浅拷贝,为了没有命名歧义,four 中的传入的 s 先叫成 sc。传参类似于做了 sc = s 的操作:

sc.buffer = s.buffer
sc.len = s.len
sc.cap = s.cap

len 和 cap 是内置类型,而 buffer 是一个指针。换句话说,修改 sc 中的 len 和 cap 不会影响 s 的 len 和 cap,但是修改 buffer 的内容则会影响外部的 s。

当执行 append(s, 4) 的时候, sc.buffer 容量不足,触发了扩容操作,扩容结束之后 sc.buffer 则指向了一个新的内容空间,自此 sc 和 s 就再无瓜葛了。

所以说,广义上这道题的答案是函数内部修改是否会影响外部,取决于 buffer 的容量是否足够,是否引起 slice 的扩容操作,狭义上的答案是 [1, 2, 3]

再看一段代码:

package main

import "fmt"

func five(s []int) {
    s = append(s, 5)
}

func main() {
    s := []int{1, 2, 3}
    s = append(s, 4)
    fmt.Printf("cap=%d\n", cap(s))

    five(s)
    fmt.Println(s)
}

输出的结果是: [1 2 3 4] 而不是 [1 2 3 4 5] 。那么问题来了,在容量充足的情况下,内部的 buffer 和外部的 buffer 相同,那么 append 的之后,s 怎么没有发生变化呢?

答案很简单,因为扩展长度之后 five 外部的 s 的 len 并没有发生变化,只是内存中的 buffer 修改了值而已,外部 s 输出的时候,会按照 len 做限制。

两种办法可以验证这个想法,第一种是把内存的的数据打印出来:

package main

import (
    "fmt"
    "unsafe"
)

func five(s []int) {
    s = append(s, 5)
}

func main() {
    s := []int{1, 2, 3}
    s = append(s, 4)
    fmt.Printf("cap=%d\n", cap(s))

    five(s)

    start := unsafe.Pointer(&s[0])
    size := unsafe.Sizeof(int(0))
    s0 := *(*int)(unsafe.Pointer(uintptr(start)))
    s1 := *(*int)(unsafe.Pointer(uintptr(start) + size*uintptr(1)))
    s2 := *(*int)(unsafe.Pointer(uintptr(start) + size*uintptr(2)))
    s3 := *(*int)(unsafe.Pointer(uintptr(start) + size*uintptr(3)))
    s4 := *(*int)(unsafe.Pointer(uintptr(start) + size*uintptr(4)))
    fmt.Printf("%d %d %d %d %d\n", s0, s1, s2, s3, s4)
}

通过指针偏移的方式(比 C 真的麻烦不知道多少倍),获取内存中的值,输出结果为 1, 2, 3, 4, 5 。第二种验证想法的方式是,在 five 中不要 =append=,直接修改 s 的值,就会发现外部也发生的变化。

上面这些行为都是由于浅拷贝导致的,符合预期,也算不上什么陷阱,如果以前写过 C++ 的话,这是一个很常见的问题。

但是,Go 的 slice 的 slice,真有个使用上的陷阱。比如对一个 slice 做 slice 操作:

s = []{1, 2, 3, 4, 5, 6}
t := s[1:3]

s 和 t 虽然是两个不同的对象,但是完全共享同一块内存(s 的 buffer 包含 t 的 buffer),只不过他们的首地址指向不同,len 和 cap 也有可能不同。

除非 t 以后触发了容量扩展的操作,否则不论谁修改共享的内存块都会导致 s 和 t 的变更。

Go 有篇官方博客 中的 A possible "gotcha",说:因为这种设计,可能会导致内存的浪费。众所周知,Go 的有垃圾回收机制的,但是当做 slice 的 slice 时, 如果原有的 slice 很大,slice 之后的很小,因为小的 slice 一直占用内存,导致大的 buffer 一直无法释放,举个例子:

var digitRegexp = regexp.MustCompile("[0-9]+")

func FindDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    return digitRegexp.Find(b)
}

这会导致 FindDigits 返回的 []byte 一直占用整个文件内容相同大小的 buffer,直到 []byte 的变量释放。为了解决这个问题,在返回时新建一个所需实际大小的 buffer,然后拷贝过去,再返回。类似这样:

func CopyDigits(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    b = digitRegexp.Find(b)
    c := make([]byte, len(b))
    copy(c, b)
    return c
}

这也是浅拷贝的带来的问题,但是 Go 的这种设计是非常「糟糕」的。理论上来讲,完全可以在做 slice 的时候做一次深拷贝来规避这个问题,这也并不符合通常程序员对 slice 操作的预期。

3 总结

本文从一个问题入手讨论了 Go 的 Array 和 Slice 的区别、Slice 的设计以及浅拷贝可能会带来的「陷阱」。Go 官方博客有两篇博客 Go Slices: usage and internalsArrays, slices (and strings): The mechanics of 'append' 也对相关的实现和特性做了介绍,推荐阅读。


2018-07-24 16:55:03 更新:

看了 Effective Go 中的 Data 章节,描述了 Go 的数组与 C 的不同:

  • 数组是值,赋值时会把所有的数据拷贝一份
  • 如果把数组传递给函数,函数拿到的是数组的 copy ,而不是指针
  • 数组的大小是类型的一部分。 [10]int[20]int 是不同的

其实,Go 不仅仅是 C-safe language,很多的实现细节都不同,也并不是一门简单的语言。


2018-09-04 15:45:14 更新:

今天遇到个问题,默认初始化的 slices 被 json 序列化之后,值竟然是 nil 而不是 [] ,但是正常输出是却为 []

package main

import (
    "encoding/json"
    "fmt"
)

type T struct {
    Xxx []int `json:"xxx"`
}

func main() {
    var t T
    fmt.Printf("%v\n", t)

    x, _ := json.Marshal(t)
    fmt.Println(string(x))
}

输出结果为:

{[]}
{"xxx":null}

这个行为真的很奇怪,按说一个结果的输出结果和他 json 序列化的值应该是保持一致的。网上对这个讨论也比较多,比如这个 #issue,之前是 [] ,后来改成了 null,具体可以看这次 提交记录

可能是希望刻意的把空指针区分开,上面的例子中 Xxxmake([]int, 0) 初始化就可以了。

虽然我觉得这是个糟糕的设计(不过整个 Go 语言的设计思路就让人觉得很刻意,那我还能怎么办呢,当然是怎么设计怎么用啦)。

Date: 2018-07-18 15:15:24

Author: JerryZhang