Golang学习 - 切片（slice）
hanpy
  2022-12-13 19:27:19 2022-12-13 19:27   2022-12-13 19:23:19    

Go 语言中数组和切片都属于集合类的类型，它们的值也都可以用来存储某一种类型的值（或者说元素）。数组类型的值的长度是固定的，而切片类型的值（以下简称切片）是可变长的。数组的长度在声明它的时候就必须给定，并且之后不会再改变。而切片的类型字面量中只有元素的类型，而没有长度。切片的长度可以自动地随着其中元素数量的增长而增长，但不会随着元素数量的减少而减小。

切片的底层数据结构

数组就是一片连续的内存， slice 实际上是一个结构体，包含三个字段：长度、容量、底层数组。
go/src/runtime/slice.go

1
2
3
4
5
type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

array：指向底层数据的一个指针,(底层数组是可以被多个slice同时指向的，因此对一个slice的元素进行操作是有可能影响到其他slice的)
len：切片的长度
cap：切片是容量

切片的初始化

切片有长度和容量的区别，可以在初始化时指定。由于切片具有可扩展性，所以当它的容量比长度大时，意味着为切片元素的增长预留了内存空间。初始化的时候如果不指定长度，则默认其容量与长度相同。

三种初始化切片的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//1. 通过下标的方式获得数组或者切片的一部分
arr := [...]int{1, 2, 3, 4, 5}
s := []int{1, 2, 3, 4, 5}
newS1 := arr[0:3]
newS2 := s[0:3]
fmt.Println(newS1)
fmt.Println(newS2)

//2. 使用字面量初始化新的切片
s1 := []int{1, 2, 3}
fmt.Println(s1)

//3. 使用关键字 `make` 创建切片：
s2 := make([]int, 3, 5)	// len=3，cap=5
fmt.Println(s2)

使用下标初始化

使用下标初始化切片也是发生在编译期间，编译器会将 arr[0:3] 或者 slice[0:3] 等语句转换成 OpSliceMake 操作

image

SliceMake 操作会接受四个参数创建新的切片，元素类型、数组指针、切片大小和容量，这也是我们在数据结构一节中提到的切片的几个字段 ，需要注意的是使用下标初始化切片不会拷贝原数组或者原切片中的数据，它只会创建一个指向原数组的切片结构体，所以修改新切片的数据也会修改原切片。

字面量初始化

字面量初始化主要是发生在编译期间，当使用形如[]int{1，2，3}的字面量创建新的切片时，会创建一个array数组([3]int{1，2，3})存储于静态区中，并在堆区创建一个新的切片，在程序启动时将静态区的数据复制到堆区，核心逻辑在 /usr/local/go/src/cmd/compile/internal/walk/complit.go | slicelit

《Go语言设计与实现》和《Go语言底层原理剖析》两本书都说核心逻辑在cmd/compile/internal/gc.slicelit中，但是没有找到，应该是迁移了，因为把分支切换到1.17的时候文件就找不到了

make初始化

对形如make([]int，3，4)的初始化切片。在类型检查阶段 typecheck1函数中，节点Node的Op操作为OMAKESLICE，并且左节点存 储长度为3，右节点存储容量为4。

go/src/cmd/compile/internal/typecheck/typecheck.go | typecheck1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func typecheck1(n ir.Node, top int) ir.Node {
    if n, ok := n.(*ir.Name); ok {
        typecheckdef(n)
    }

    switch n.Op() {
        default:
        ir.Dump("typecheck", n)
        base.Fatalf("typecheck %v", n.Op())
        panic("unreachable")
        // ... 省略代码

        case ir.OMAKE:
        n := n.(*ir.CallExpr)
        return tcMake(n)

        // ... 省略代码
    }
}

/usr/local/go/src/cmd/compile/internal/typecheck/func.go | tcMake

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
func tcMake(n *ir.CallExpr) ir.Node {
        // --- 省略代码 ---
    case types.TSLICE:
        if i >= len(args) {
            base.Errorf("missing len argument to make(%v)", t)
            n.SetType(nil)
            return n
        }
        l = args[i]
        i++
        l = Expr(l)
        var r ir.Node
        if i < len(args) {
            r = args[i]
            i++
            r = Expr(r)
        }

        if l.Type() == nil || (r != nil && r.Type() == nil) {
            n.SetType(nil)
            return n
        }
        if !checkmake(t, "len", &l) || r != nil && !checkmake(t, "cap", &r) {
            n.SetType(nil)
            return n
        }
        if ir.IsConst(l, constant.Int) && r != nil && ir.IsConst(r, constant.Int) && constant.Compare(l.Val(), token.GTR, r.Val()) {
            base.Errorf("len larger than cap in make(%v)", t)
            n.SetType(nil)
            return n
        }
        nn = ir.NewMakeExpr(n.Pos(), ir.OMAKESLICE, l, r)
        // --- 省略代码 ---
    }
    // --- 省略代码 ---
    nn.SetType(t)
    return nn
}

编译时对于字面量的重要优化是判断变量应该被分配到栈中还是 应该逃逸到堆区。如果make函数初始化了一个太大的切片，则该切片会逃逸到堆中。如果分配了一个比较小的切片，则会直接在栈中分配。

这个临界值定义在go/src/cmd/compile/internal/ir/cfg.go中，默认大小是64KB

make([]int64，1023)与make([]int64，1024)实现的细节是截然 不同的。

切片的扩容

切片使用append函数添加元素的时候，如果新切片是长度超过现在的容量，就会进行扩容。这里需要注意的是调用append函数之后会返回新的切片（如果扩容）
切片的扩容规则：
1.18版本之前的规则
当原 slice 容量小于 1024的时候，新 slice 容量变成原来的 2 倍；原 slice 容量超过 1024，新 slice 容量变成原来的1.25倍。
1.18版本之后的规则
当原slice容量(oldcap)小于256的时候，新slice(newcap)容量为原来的2倍；原slice容量超过256，新slice容量newcap = oldcap+(oldcap+3*256)/4

不过还是有一个需要注意的地方，扩容的时候会根据切片的类型，分配不同大小的内存。为了对 齐内存，申请的内存可能大于实际的类型大小×容量大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main
import "fmt"
func main() {
    s := make([]int, 0)
    oldCap := cap(s)
    for i := 0; i < 2048; i++ {
        s = append(s, i)
        newCap := cap(s)
        if newCap != oldCap {
            fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
            oldCap = newCap
        }
    }
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

在老 slice 容量小于1024的时候，新 slice 的容量的确是老 slice 的2倍。目前还算正确。

但是，当老slice容量大于等于 1024 的时候，情况就有变化了。当向slice中添加元素1280 的时候，老slice的容量为 1280，之后变成了 1696，两者并不是 1.25 倍的关系（1696/1280=1.325）。添加完 1696 后，新的容量 2304 当然也不是 1696 的 1.25 倍。

扩容的时候会调用growslice函数

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// go/src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
    // ... 省略前面的
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.cap < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 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

    // 上面已经计算出来新的cap的长度,下面就是在进行内存补齐的操作,roundupsize这个函数就是
    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 == sys.PtrSize:
        lenmem = uintptr(old.len) * sys.PtrSize
        newlenmem = uintptr(cap) * sys.PtrSize
        capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
        newcap = int(capmem / sys.PtrSize)
        case isPowerOfTwo(et.size):
        var shift uintptr
        if sys.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}
}

// go/src/runtime/msize.go
func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= smallSizeMax-8 {
            return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
        } else {
            return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
        }
    }
    if size+_PageSize < size {
        return size
    }
    return alignUp(size, _PageSize)
}

切片的复制

切片是引用类型，如果用赋值的方式来进行复制，底层数据还是使用的一个。如果要完全的进行复制，需要使用copy函数来进行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
s := []int{1, 2, 3}
s1 := s
fmt.Println(s)                                  // 1,2,3
fmt.Println(s1)                                 // 1,2,3
fmt.Printf("s pointer %p,s1 pointer %p", s, s1) // s pointer 0xc000160000,s1 pointer 0xc000160000
s[0] = 100
fmt.Println(s)  // 100,2,3
fmt.Println(s1) // 100,2,3

ss := []int{1, 2, 3}
newS := make([]int, len(ss), cap(ss))
copy(newS, ss)
fmt.Println(ss)   // 1,2,3
fmt.Println(newS) // 1,2,3
fmt.Printf("ss pointer %p,newS pointer %p \n", ss, newS)
ss[0] = 100
fmt.Println(ss)   // 100,2,3
fmt.Println(newS) // 1,2,3
  1. 切片的底层数据结构
  2. 切片的初始化
    1. 三种初始化切片的方式
    2. 使用下标初始化
    3. 字面量初始化
    4. make初始化
  3. 切片的扩容
  4. 切片的复制