golang系列之-slice

发表于 更新于 本文字数： 1k 阅读时长 ≈ 4 分钟

slice/切片-动态数组，golang常用的数据结构之一，相对于数组，slice可以追加元素，在容量不足时自动扩容

当前go版本：1.24

数据结构

todo：文章图片待补充

slice数据结构如下所示

1
2
3
4
5
6
// src/runtime/slice.go
type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

其中

  • array - 指向一片连续内存区域的第一个元素
  • len - 已有元素数量
  • cap - 可容纳元素总数量

初始化

slice初始化方式有三种

  1. 使用字面量创建新切片
  2. 使用关键字make创建切片
  3. 通过下标获取数组或切片的一部份
1
2
3
4
5
6
// len=3 cap=3
var v1 = []int{1, 2, 3}
// len=10 cap=10
var v2 = make([]int, 10) // var v2 = make([]int, 0, 10)
// len=4 cap=9
var v3 = v2[1:5]

字面量

使用ssa包打印var v1 = []int{1, 2, 3}，得到结果如下所示

1
2
3
4
5
6
7
8
t0 = new [3]int (slicelit)                                      *[3]int
t1 = &t0[0:int]                                                    *int
*t1 = 1:int
t2 = &t0[1:int]                                                    *int
*t2 = 2:int
t3 = &t0[2:int]                                                    *int
*t3 = 3:int
t4 = slice t0[:]
  1. 根据字面量的数量创建一个数组t0
  2. 初始化数组元素t1/t2/t3
  3. 在t0基础上创建一个切片t4

src/cmd/compile/internal/walk/complit.goslicelit

关键字

使用ssa包打印var v2 = make([]int, 10)，得到结果如下所示

1
2
t0 = new [10]int (makeslice)                                   *[10]int
t1 = slice t0[:10:int]                                            []int
  1. 创建一个数组t0
  2. 在t0基础上创建一个切片t1

makeslice源代码如下，做了一些精简

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func makeslice(et *_type, len, cap int) unsafe.Pointer {
    // 1. mem（连续内存区域大小） = 元素类型占用大小(type_size)*容量大小(cap)
    // 2. overflow（是否溢出） = !(type_size|cap < 4GB or type_size=0 or cap > uint_max/type_size)
    mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))
    if overflow || mem > maxAlloc || len < 0 || len > cap {
        mem, overflow := math.MulUintptr(et.Size_, uintptr(len))
        if overflow || mem > maxAlloc || len < 0 {
            panicmakeslicelen()
        }
        panicmakeslicecap()
    }

    // 申请内存
    return mallocgc(mem, et, true)
}

使用下标

1
2
var v2 = make([]int, 10)
var v3 = v2[1:5]

使用ssa包打印上述代码，得到结果如下所示

1
2
3
t0 = new [10]int (makeslice)                                   *[10]int
t1 = slice t0[:10:int]                                            []int
t2 = slice t1[1:int:5:int]                                        []int
  1. 使用关键字make创建一个切片t1
  2. 在上一步基础上，创建一个切片t2，指定下标left=1 right=5

追加和扩容

1
2
var v1 = []int{1, 2, 3}
v1 = append(v1, 4, 5, 6)

slice使用append关键字实现追加操作，当数据量超过底层cap大小时，触发扩容，扩容代码精简后如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
    // ...
    // 根据当前cap以及新len计算新cap
    newcap := nextslicecap(newLen, oldCap)

    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    noscan := !et.Pointers() // 指针？
    switch {
    // ... （优化）
    // 以下是通用操作
    default:
        lenmem = uintptr(oldLen) * et.Size_
        newlenmem = uintptr(newLen) * et.Size_
        capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
        capmem = roundupsize(capmem, noscan)
        newcap = int(capmem / et.Size_)
        capmem = uintptr(newcap) * et.Size_
    }
    // ...
}

func nextslicecap(newLen, oldCap int) int {
    // 1. 双倍cap仍然小于newLen，直接返回newLen
    newcap := oldCap
    doublecap := newcap + newcap
    if newLen > doublecap {
        return newLen
    }

    // 2. 双倍cap小于512，返回双倍cap
    const threshold = 256
    if oldCap < threshold {
        return doublecap
    }
    for {
        // 3. 计算公式：x = 5/4*x + 192，直到x>=newLen
        newcap += (newcap + 3*threshold) >> 2
        if uint(newcap) >= uint(newLen) {
            break
        }
    }

    // 溢出？
    if newcap <= 0 {
        return newLen
    }
    return newcap
}

在1.18版本，Keith Randall对slice的growth factor进行了调整，使其增长更为平滑，详细见提交：https://github.com/golang/go/blob/2dda92ff6f9f07eeb110ecbf0fc2d7a0ddd27f9d/src/runtime/slice.go

不同cap对应的扩容因子如下

starting cap growth factor
256 2.0
512 1.63
1024 1.44
2048 1.35
4096 1.30

拷贝切片

切片的拷贝也归类于appendSlice，具体在src/cmd/compile/internal/walk/assign.go:appendSlice。

这里的copy可能与我们预期不一样，并不是浅层或深层拷贝，是拷贝与目标dst的len长度一致的数据，与容量cap无关

1
2
3
var v1 = []int{1, 2, 3}
var v2 []int // or `var v2 = make([]int, 0, 3)`
copy(v2, v1) // v2仍然是空切片

slicecopy函数具体如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
    // fromLen和toLen都为0，不处理
    if fromLen == 0 || toLen == 0 {
        return 0
    }

    // n=min(fromLen, toLen)
    n := fromLen
    if toLen < n {
        n = toLen
    }

    // type_size大小为0
    if width == 0 {
        return n
    }

    size := uintptr(n) * width
    // copy
    if size == 1 {
        *(*byte)(toPtr) = *(*byte)(fromPtr)
    } else {
        memmove(toPtr, fromPtr, size)
    }
    return n
}

参考文档

1. Memory Allocation Summary.md
3.2 切片
ssa
Go Slices: usage and internals
Arrays, Slices and Maps in Go