Go Quiz: 从Go面试题看slice的底层原理和注意事项

面试题

最近Go 101的作者发布了11道Go面试题,非常有趣,打算写一个系列对每道题做详细解析。欢迎大家关注。

大家可以看下面这道关于slice的题目,通过这道题我们可以对slice的特性和注意事项有一个深入理解。

package main

import "fmt"

func main() {
    a := [...]int{0, 1, 2, 3}
    x := a[:1]
    y := a[2:]
    x = append(x, y...)
    x = append(x, y...)
    fmt.Println(a, x)
}
  • A: [0 1 2 3] [0 2 3 3 3]
  • B: [0 2 3 3] [0 2 3 3 3]
  • C: [0 1 2 3] [0 2 3 2 3]
  • D: [0 2 3 3] [0 2 3 2 3]

大家可以在评论区留下你们的答案。这道题有几个考点:

  1. slice的底层数据结构是什么?给slice赋值,到底赋了什么内容?
  2. 通过:操作得到的新slice和原slice是什么关系?新slice的长度和容量是多少?
  3. append在背后到底做了哪些事情?
  4. slice的扩容机制是什么?

解析

我们先逐个解答上面的问题。

slice的底层数据结构

talk is cheap, show me the code. 直接上slice的源码:

slice定义在src/runtime/slice.go第15行,源码地址:https://github.com/golang/go/...

Pointer定义在src/unsafe/unsafe.go第184行,源码地址:https://github.com/golang/go/...

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

type Pointer *ArbitraryType

slice实际上是一个结构体类型,包含3个字段,分别是

  • array: 是指针,指向一个数组,切片的数据实际都存储在这个数组里。
  • len: 切片的长度。
  • cap: 切片的容量,表示切片当前最多可以存储多少个元素,如果超过了现有容量会自动扩容。

因此给slice赋值,实际上都是给slice里的这3个字段赋值。看起来这像是一句正确的废话,但是相信我,记住这句话可以帮助你非常清晰地理解对slice做修改后slice里3个字段的值是怎么变的,slice 指向的底层数组的数据是怎么变的。

:分割操作符

:分割操作符有几个特点:

  1. :可以对数组或者slice做数据截取,:得到的结果是一个新slice
  2. slice结构体里的array指针指向原数组或者原slice的底层数组,新切片的长度是右边的数值减去左边的数值,新切片的容量是原切片的容量减去:左边的数值。
  3. :的左边如果没有写数字,默认是0,右边没有写数字,默认是被分割的数组或被分割的切片的长度。

    a := make([]int, 0, 4) // a的长度是0,容量是4
    b := a[:] // 等价于 b := a[0:0], b的长度是0,容量是4
    c := a[:1] // 等价于 c := a[0:1], b的长度是1,容量是4
    d := a[1:] // 编译报错 panic: runtime error: slice bounds out of range
    e := a[1:4] // e的长度3,容量3
  4. :分割操作符右边的数值有上限,上限有2种情况
  • 如果分割的是数组,那上限是是被分割的数组的长度。
  • 如果分割的是切片,那上限是被分割的切片的容量。注意,这个和下标操作不一样,如果使用下标索引访问切片,下标索引的最大值是(切片的长度-1),而不是切片的容量。

一图胜千言,我们通过下面的示例来讲解下切片分割的机制。

下图表示slice结构,ptr表示array指针,指向底层数组,lencap分别是切片的长度和容量。

Go Quiz: 从Go面试题看slice的底层原理和注意事项_第1张图片

step1: 我们通过代码s := make([]byte, 5, 5)来创建一个切片s,长度和容量都是5,结构示意如下:

Go Quiz: 从Go面试题看slice的底层原理和注意事项_第2张图片
step2: 现在对切片s做分割s2 := s[2:4],得到一个新切片s2,结构如下。

Go Quiz: 从Go面试题看slice的底层原理和注意事项_第3张图片

  • s2还是指向原切片s的底层数组,只不过指向的起始位置是下标索引为2的位置。
  • s2的长度len(s2)是2,因为s2 := s[2:4]只是截取了切片s下标索引为2和3的2个元素。
  • s2的容量cap(s2)是3,因为从s2指向的数组位置到底层数组末尾,可以存3个元素。
  • 因为长度是2,所以只有s2[0]s2[1]是有效的下标索引访问。但是,容量为3,s2[0:3]是一个有效的分割表达式。

step3: 对切片s做分割s3 := s2[:cap(s2)],得到一个新切片s3,结构如下:

Go Quiz: 从Go面试题看slice的底层原理和注意事项_第4张图片

  • s3指向切片s2的底层数组,同样也是s的底层数组,指向的起始位置是s2的起始位置,对应数组下标索引为2的位置。
  • s3的长度len(s3)是3,因为s3 := s2[:cap(s2)]截取了切片s2 下标索引为0,1,2的3个元素。
  • s3的容量cap(s3)是3,因为从s3指向的数组位置到底层数组末尾,可以存3个元素。

因此,对数组或者切片做:分割操作产生的新切片还是指向原来的底层数组,并不会把原底层数组的元素拷贝一份到新的内存空间里。

正是因为他们指向同一块内存空间,所以对原数组或者原切片的修改会影响分割后的新切片的值,反之亦然。

append机制

要了解append的机制,直接看源码说明。

// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
//    slice = append(slice, elem1, elem2)
//    slice = append(slice, anotherSlice...)
// As a special case, it is legal to append a string to a byte slice, like this:
//    slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type
  • append函数返回的是一个切片,append在原切片的末尾添加新元素,这个末尾是切片长度的末尾,不是切片容量的末尾。

    func test() {
        a := make([]int, 0, 4)
        b := append(a, 1) // b=[1], a指向的底层数组的首元素为1,但是a的长度和容量不变
        c := append(a, 2) // a的长度还是0,c=[2], a指向的底层数组的首元素变为2
        fmt.Println(a, b, c) // [] [2] [2]
    }
  • 如果原切片的容量足以包含新增加的元素,那append函数返回的切片结构里3个字段的值是:

    • array指针字段的值不变,和原切片的array指针的值相同,也就是append是在原切片的底层数组返回的切片还是指向原切片的底层数组
    • len长度字段的值做相应增加,增加了N个元素,长度就增加N
    • cap容量不变
  • 如果原切片的容量不够存储append新增加的元素,Go会先分配一块容量更大的新内存,然后把原切片里的所有元素拷贝过来,最后在新的内存里添加新元素。append函数返回的切片结构里的3个字段的值是:

    • array指针字段的值变了,不再指向原切片的底层数组了,会指向一块新的内存空间
    • len长度字段的值做相应增加,增加了N个元素,长度就增加N
    • cap容量会增加

注意:append不会改变原切片的值,原切片的长度和容量都不变,除非把append的返回值赋值给原切片。

那么问题来了,新切片的容量是按照什么规则计算得出来的呢?

slice扩容机制

slice的扩容机制随着Go的版本迭代,是有变化的。目前网上大部分的说法是下面这个:

当原 slice 容量小于 1024 的时候,新 slice 容量变成原来的 2 倍;原 slice 容量超过 1024,新 slice 容量变成原来的 1.25倍。

这里明确告诉大家,这个结论是错误的。

slice扩容的源码实现在src/runtime/slice.go里的growslice函数,源码地址:https://github.com/golang/go/...

Go 1.18的扩容实现代码如下,et是切片里的元素类型,old是原切片,cap等于原切片的长度+append新增的元素个数。

func growslice(et *_type, old slice, cap int) slice {
    // ...
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
        if old.cap < threshold {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                // Transition from growing 2x for small slices
                // to growing 1.25x for large slices. This formula
                // gives a smooth-ish transition between the two.
                newcap += (newcap + 3*threshold) / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    // Specialize for common values of et.size.
    // For 1 we don't need any division/multiplication.
    // For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
    // For powers of 2, use a variable shift.
    switch {
    case et.size == 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        overflow = uintptr(newcap) > maxAlloc
        newcap = int(capmem)
    case et.size == goarch.PtrSize:
        lenmem = uintptr(old.len) * goarch.PtrSize
        newlenmem = uintptr(cap) * goarch.PtrSize
        capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
        newcap = int(capmem / goarch.PtrSize)
    case isPowerOfTwo(et.size):
        var shift uintptr
        if goarch.PtrSize == 8 {
            // Mask shift for better code generation.
            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
        } else {
            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
        }
        lenmem = uintptr(old.len) << shift
        newlenmem = uintptr(cap) << shift
        capmem = roundupsize(uintptr(newcap) << shift)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }
    // ...
    return slice{p, old.len, newcap}
}

newcap是扩容后的容量,先根据原切片的长度、容量和要添加的元素个数确定newcap大小,最后再对newcap做内存对齐得到最后的newcap。

答案

我们回到本文最开始的题目,逐行解析每行代码的执行结果。

代码 切片对应结果
a := [...]int{0, 1, 2, 3} a是一个数组,长度是4,值是[ 0 1 2 3]
x := a[:1] x是一个切片,切片里的指针指向数组a的首元素,值是[0],长度1,容量4
y := a[2:] y是一个切片,切片里的指针指向数组a的第2个元素,值是[2 3],长度2,容量2
x = append(x, y...) x的剩余容量还有3个,足以存储y里的2个元素,所以x不会扩容,x的值是[0 2 3],长度3,容量4。因为x, a, y都指向同一块内存空间,所以x的修改影响了a和y。
a的值变为[0 2 3 3],长度4,容量4
y的值变为[3 3],长度2,容量2
x = append(x, y...) x的剩余容量只有1个,不足以存储y里的2个元素,所以要扩容。append(x, y)的结果是得到一个新切片,值是[0 2 3 3 3],长度5,容量8。
append的返回值赋值给x,所以切片x会指向扩容后的新内存。
fmt.Println(a, x) a的值还是[0 2 3 3]没有变化,所以打印结果是[0 2 3 3] [0 2 3 3 3 3 ],答案是B

加餐:copy机制

Go的内置函数copy可以把一个切片里的元素拷贝到另一个切片,源码定义在src/builtin/builtin.go,代码如下:

// The copy built-in function copies elements from a source slice into a
// destination slice. (As a special case, it also will copy bytes from a
// string to a slice of bytes.) The source and destination may overlap. Copy
// returns the number of elements copied, which will be the minimum of
// len(src) and len(dst).
func copy(dst, src []Type) int

copy会从原切片src拷贝 min(len(dst), len(src))个元素到目标切片dst

因为拷贝的元素个数min(len(dst), len(src))不会超过目标切片的长度len(dst),所以copy执行后,目标切片的长度不会变,容量不会变。

注意:原切片和目标切片的内存空间可能会有重合,copy后可能会改变原切片的值,参考下例。

package main

import "fmt"

func main() {
    a := []int{1, 2, 3}
    b := a[1:] // [2 3]
    copy(a, b) // a和b内存空间有重叠
    fmt.Println(a, b) // [2 3 3] [3 3]
}

总结

对于slice,时刻想着对slice做了修改后,slice里的3个字段:指针,长度,容量是怎么变的。
  • slice是一个结构体类型,里面包含3个字段:指向数组的array指针,长度len和容量cap。给slice赋值是对slice里的指针,长度和容量3个字段分别赋值。
  • :分割操作符的结果是一个新切片,slice结构体里的array指针指向原数组或者原slice的底层数组,新切片的长度是右边的数值减去左边的数值,新切片的容量是原切片的容量减去:左边的数值。
  • :分割操作符右边的数值上限有2种情况:

    • 如果分割的是数组,那上限是是被分割的数组的长度。
    • 如果分割的是切片,那上限是被分割的切片的容量。注意,这个和下标操作不一样,如果使用下标索引访问切片,下标索引的最大值是(切片的长度-1),而不是切片的容量。
  • 对于append操作和copy操作,要清楚背后的执行逻辑。
  • 打印slice时,是根据slice的长度来打印的

    a := make([]int, 1, 4) // a的长度是1,容量是4
    b := append(a, 1) // 往a的末尾添加元素1,b=[0 1], a的长度还是1,a和b指向同一个底层数组
    fmt.Println(a, b) // [0] [0 1]
  • Go在函数传参时,没有传引用这个说法,只有传值。网上有些文章写Go的slicemapchannel作为参数是传引用,这是错误的,可以参考我之前的文章Go有引用变量和引用传递么?

开源地址

文章和示例代码开源地址在GitHub: https://github.com/jincheng9/...

公众号:coding进阶

个人网站:https://jincheng9.github.io/

思考题

留下2道思考题,欢迎大家在评论区留下你们的答案。

  • 题目1:

    package main
    
    import "fmt"
    
    func main() {
        a := []int{1, 2}
        b := append(a, 3)
    
        c := append(b, 4)
        d := append(b, 5)
    
        fmt.Println(a, b, c[3], d[3])
    }
  • 题目2

    package main
    
    import "fmt"
    
    func main() {
        s := []int{1, 2}
        s = append(s, 4, 5, 6)
        fmt.Println(len(s), cap(s))
    }

References

你可能感兴趣的