slice

下面我们对 go 的数据结构 slice 的操作和源码尝试解读，有点类似于 java 中的数组但是又不相同

数据结构

1
2
3
4
5
type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}
  1. array unsafe.Pointer 指针指向底层存放数据的起始地址
  2. len 切片的长度，切片所含数据的数量
  3. cap 切片的容量，表示从当前切片起点开始，到底层数组末尾为止最多还能看到多少个元素；创建时必须满足 cap >= len

创建切片

指定切片容量和长度的创建

1
2
s1 := make([]int, 2, 4)
s2 := make([]int, 2)

有两种方式：

  1. 显式初始 len 和 cap，此时为 s1分配了存放4个数据的空间，并且初始化前2个数据为零值
  2. s2此时在创建时会将 cap 设置为与 len 相等为2，此时分配了存放2个数据的空间，并且初始化2个数据为零值

声明切片 与 显式赋值初始化切片

1
2
3
var s3 []int 

s4 := []int{1,2}

s3 是定义的一个未初始化的切片变量，此时并未分配底层数组，值为 nil slice
s4 显式给一个切片赋值，此时完成切片初始化和数据赋值，并且 cap 和 len 都初始化为数据数量

下面展开叙述创建切片的流程

makeslice(et * _type, len, cap int)

1
2
3
4
5
6
7
8
9
10
11
12
func makeslice(et *_type, len, cap int) unsafe.Pointer {
	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)
}

方法主要是在调用 MulUintptr 计算出申请内存的大小，然后申请一片连续的地址

  1. 在方法内部会进行合法性判断，申请内存是否超限，以及 len 和 cap 的合法性

切片的截取

在探讨切片的截取前，我们首先了解如何获取一个切片指向的底层存放数据地址的方法

unsafe.SliceData()

1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
	s1 := make([]int, 2)
	fmt.Printf("%p\n", unsafe.SliceData(s1))
	
	var s2 []int
	fmt.Printf("%p\n", unsafe.SliceData(s2))
	
	s3 := make([]int, 0, 2)
	fmt.Printf("%p\n", unsafe.SliceData(s3))

	s4 := []int{}
	fmt.Printf("%p\n", unsafe.SliceData(s4))
}

该方法可以获取切片指向的底层数组地址，返回规则有三种：

  1. 如果 cap(slice) > 0，则返回底层数组首元素地址，也就是 &slice[:1][0]
  2. 如果 slice == nil，则返回 nil
  3. 其他情况（非 nil 但 cap == 0）返回一个非 nil 的未指定地址，不应该依赖它的具体值

上面的例子里：

  1. s1 的 cap > 0，因此返回底层数组首元素地址
  2. s2 是 nil slice，因此返回 nil
  3. s3 的 cap > 0，即使 len == 0，也仍然返回底层数组首元素地址；len == 0 只表示当前不能通过索引访问元素，不代表底层数组一定不存在
  4. s4 非 nil 但 cap == 0，因此返回一个非 nil 的未指定地址，不应该依赖它的具体值

下面正式讨论切片的截取

1
2
3
4
5
6
7
8
9
10
11
func main() {
	s1 := make([]int, 4, 5)
	fmt.Printf("%p\n", unsafe.SliceData(s1))

	s2 := s1[1:]
	fmt.Printf("%p\n", unsafe.SliceData(s2))

	s2 = append(s2, 1)
	fmt.Printf("%p %d %d\n ", unsafe.SliceData(s1), cap(s1), len(s1))
	fmt.Printf("%p %d %d\n", unsafe.SliceData(s2), cap(s2), len(s2))
}

对于切片的截取，通过 s1[a:b] 即可得到 s1 的一个子切片，该区间左闭右开，不会复制数据。
本质上底层复用的还是同一块内存，只不过是将 s2 的 array 指向 s1 的 array + 元素大小 * a 得到的地址。对于普通双下标切片，len(s2) = b - a，cap(s2) = cap(s1) - a。

s1 与 s2 的 len/cap 变化互不影响，但它们共享同一底层数组，因此对重叠数据的写入会互相可见。
但是每个切片当前能通过索引访问的范围仍然受自己的 len 限制。
如果子切片仍有足够容量，后续对它执行 append 也可能直接改写同一个底层数组中的尾部数据。

追加数据

向一个切片追加数据
append()

1
2
3
4
5
s5 := make([]int, 1, 2)
s5 = append(s5, 1, 2)

s6 := []int{2, 3, 4}
s6 = append(s6, s5...)

append 方法会返回更新后的切片，因此必须接收返回值，一般就是赋回原切片。

  1. 可以直接追加一个或多个同类型元素
  2. 追加另外一个切片时需要使用 ... 展开，例如 append(dst, src...)

在 append 的流程中，可能会出现 len(s) + n(追加数据数量) > cap(s), 此时追加数据超出容量，会调用 growslice 方法对切片进行扩容。

切片扩容

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
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
	oldLen := newLen - num
    //..
	if newLen < 0 {
		panic(errorString("growslice: len out of range"))
	}

	if et.Size_ == 0 {
		return slice{unsafe.Pointer(&zerobase), newLen, newLen}
	}

	newcap := nextslicecap(newLen, oldCap)

	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	
	noscan := !et.Pointers()
    // 基于容量，确定新数组容器所需要的内存空间大小 capmem
	switch {
    //数据大小 = 1 字节时，字节数 = 数据数， 对齐后 capmem 直接当作新容量
	case et.Size_ == 1:
		lenmem = uintptr(oldLen)
		newlenmem = uintptr(newLen)
		capmem = roundupsize(uintptr(newcap), noscan)
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
    //数据大小 = 指针大小，按指针大小计算字节数，对齐后再除回数据个数得到 newcap
	case et.Size_ == goarch.PtrSize:
		lenmem = uintptr(oldLen) * goarch.PtrSize
		newlenmem = uintptr(newLen) * goarch.PtrSize
		capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		newcap = int(capmem / goarch.PtrSize)
    //数据大小是 2 的幂。用位移代替乘除（更快）
	case isPowerOfTwo(et.Size_):
		var shift uintptr
		if goarch.PtrSize == 8 {
			shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
		} else {
			shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
		}
		lenmem = uintptr(oldLen) << shift
		newlenmem = uintptr(newLen) << shift
		capmem = roundupsize(uintptr(newcap)<<shift, noscan)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
		capmem = uintptr(newcap) << shift
    //普通乘法
	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_
	}

	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: len out of range"))
	}

    // 进行实际的切片初始化操作
	var p unsafe.Pointer
	if !et.Pointers() {
		p = mallocgc(capmem, nil, false)
	
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
		}
	}
    // 将切片的内容拷贝到扩容后的位置 p 
	memmove(p, oldPtr, lenmem)

	return slice{p, newLen, newcap}
}

在进入切片扩容后，首先计算出 oldlen

  1. 如果 newlen 不合法直接 panic
  2. 如果 et.Size_ == 0（例如：struct{}）在 append 之后 len 可能 > 0，但数据大小是 0，实际上不需要分配真实内存。但 Go 不希望出现“len>0 但指针是 nil” 的切片，所以返回一个指向 zerobase 的非 nil 指针。
  3. 接着调用 nextslicecap 计算目标容量，详细计算逻辑后面阐述
  4. 然后针对不同数据类型执行不同操作计算内存空间大小
  5. 在初始化新切片时先按数据是否含指针选择分配方式，然后拷贝旧数据并返回新切片
  6. 需要注意：nextslicecap 算出的只是目标容量，growslice 后续还会经过 roundupsize 按分配器大小级别对齐，所以最终实际的 cap 可能比这里算出来的更大

nextslicecap(newLen, oldCap int)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func nextslicecap(newLen, oldCap int) int {
	newcap := oldCap
	doublecap := newcap + newcap
	if newLen > doublecap {
		return newLen
	}

	const threshold = 256
	if oldCap < threshold {
		return doublecap
	}
	for {
		newcap += (newcap + 3*threshold) >> 2
		if uint(newcap) >= uint(newLen) {
			break
		}
	}
	if newcap <= 0 {
		return newLen
	}
	return newcap
}

nextslicecap 计算的是扩容时的目标容量，逻辑如下：

  1. 如果预期容量大于老容量二倍则直接为预期容量
  2. 如果老容量小于256，则直接为老容量二倍
  3. 如果老容量大于等于256，则使用 for 循环计算 newcap += (newcap + 3*threshold) / 4，让增长倍率从 2x 平滑过渡到接近 1.25x，直到新容量已经大于等于预期容量
  4. 如果在 for 循环计算预期容量是触发整型溢出，将 newcap 回绕为负数 or 0时则返回 newLen
  5. 返回目标容量；但在 growslice 中经过内存对齐后，最终实际容量可能还会更大

切片数据删除

1
2
3
4
5
6
func main() {
	s1 := make([]int, 4, 5)
	s1 = s1[1:]
    s1 = append(s1[:1], s1[2:]...)
    s1 = s1[:1]
}
  1. 删除 a 以前的数据，例如第二行 删除 s1切片 s1[1]之前的数据
  2. 删除中间的数据， 利用 append 和 切片截断的左闭右开区间，实现 s1[1]数据的删除
  3. 删除 b 及 b 以后的数据，例如第四行删除索引 1 及其之后的数据

这类“删除”通常只是重新切片或搬移元素，并不会主动缩容；如果元素类型里含有指针，而且希望让被删除元素尽快被 GC 回收，通常还需要把尾部不再使用的位置置零。

拷贝切片

1
2
3
4
5
6
7
func main() {
	s1 := make([]int, 4, 5)
    s2 := make([]int, len(s1))
	copy(s2, s1)

    s3 := s1
}

copy(dst, src) 是元素拷贝，把 min(len(dst), len(src)) 个元素复制到 dst 的底层数组里，源和目标切片允许重叠。
在上面的例子里，s2 是通过 make 新建出来的，因此 copy 之后它与 s1 的底层数组互相独立。
s3 := s1 这种写法只是复制切片头部的值（data/len/cap），不会复制底层元素，所以 s1 和 s3 仍然共享同一个底层数组，修改重叠部分时会互相影响。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。