Slice详解

基础用法

slice定义，在runtime/slice.go中

1
2
3
4
5


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

slice拥有指针、长度、容量这几个字段，其底层是一个数组，用指针array指代
切片操作切片名[startIndex:endIndex:maxIndex]，其操作的区间是[startIndex, endIndex)，是左闭右开的，最多取到下标maxIndex-1处，endIndex<=maxIndex
注意与python区分:
- python的切片第二个冒号后是步长step，
- 不支持像python切片那样的支持逆置slice[::-1]以及slice[-1]，逆置只能手动写for循环；访问最后一个元素只能slice[len(slice)-1]

slice的5种创建方式：

1
2
3
4
5
6


var slice1 []int             // nil slice
slice2 := []int{1, 2, 3}     
slice3 := make([]int, 1, 2)  // 长度为1，容量为2，长度必须小于等于容量
slice4 := *new([]int)        // nil slice，注意取值运算*
slice5 := slice2[1:2]
slice6 := []struct{x, y int}{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

注意事项
- 使用make初始化slice时，必须指明长度
- 指向同一个底层数组的不同切片A和B，若使用A修改了A和B的公共部分，那么访问B时也会受到影响.
- 此外，还需要注意两个指向同一底层数组、但起始和结束位置以及容量大小不同的切片，经过一系列扩容操作后，可能不再指向同一底层数组。
- 使用make()创建新切片时，可以不指定容量，容量默认和长度相同。
- nil slice 不等于 empty slice：
  - nil slice指代的是和nil做==运算的结果是true，其len和cap都是0；
  - empty slicec虽然len和cap为0，但是和nil做==运算是false

扩容机制

代码在runtime/slice.go/growslice(et *_type, old slice, cap int)中
先大致计算新容量newcap，然后进行内存对齐得到最终的新容量。具体为：

记当前容量为oldcap，新增B个元素后为cap=oldcap + B
第一步计算大致新容量newcap：
- 如果 cap > 2*oldcap，那么新容量 newcap = cap
- 如果 cap <= 2*oldcap，且 oldcap<1024，那么新容量 newcap = 2 * oldcap
- 如果 cap <= 2*oldcap, 且 oldcap>=1024大于 1024 时，先令 newcap=oldcap, 循环操作：newcap=newcap*1.25，直至 newcap>=cap 或长度太大导致overflow时退出循环

第二步内存对齐：

首先，需要注意函数growslice()中，et指的是element type，即切片中元素的类型，_type类型的et是对切片类型的抽象和描述
然后，根据不同的切片元素类型进行处理，大致思路是计算申请et.size * newcap大小的内存，Go内存分配器计算需要的内存大小x=roundupsize(et.size * newcap)，切片最终容量newcap = x / et.size

计算lenmem, newlenmem, capmem, overflow, newcap的详细如下，根据切片每个元素大小的不同进行不同的计算：

 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


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)
}

src/runtime/msize/roundupsize()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// Returns size of the memory block that mallocgc will allocate if you ask for the size.
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)
}

注意注释：当我们请求size大小的内存块时，返回mallocgc将分配的实际内存块的大小。
里面的大致实现是利用提前计算好的数组，以O(1)的代价计算出结果

GC

slice = slice[:0], 将slice的len设置为0，保留分配的内存
slice = nil 将len和cap置为0，且触发GC回收内存（如果底层数组不存在其他引用）

slice的花式用法

Go中没有cpp中的vector，也没有python中的list，官方大概觉得slice可以实现这两个容器的所有功能….

用slice实现cpp中vector的主要功能

push_back()
push_front()
pop_back()
pop_front()
insert()
erase()
size()
capacity()
reverse()
copy()
clear()

 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


package main

import "fmt"

func print(arr []int){
	for i, x := range arr {
		fmt.Println(i, x)
	}
	fmt.Println("-----")
}

func main() {
	var vector []int
	vector = append(vector, 1)        // 类似于 vector.push_back(1)
	fmt.Println(vector)

	vector = append([]int{2}, vector...)     // 类似于 vector.push_front(2)
	fmt.Println(vector)

	vector = append(vector, []int{4, 5}...)  // 类似于python list.extend([4, 5])
	fmt.Println(vector)

	vector = vector[:len(vector)-1]         // 类似于 vector.pop_back()
	fmt.Println(vector)

	vector = vector[1:]                     // 类似于 vector.pop_front()
	fmt.Println(vector)

	vector = append(vector[:1], append([]int{2}, vector[1:]...)...)   // insert()
	fmt.Println(vector)

	vector = append(vector[:1], vector[2:]...)   // erase()
	fmt.Println(vector)

	size := len(vector)     // size()
	fmt.Println(size)

	capacity := cap(vector) // capacity()
	fmt.Println(capacity)

	// reverse() 没有builtin的支持，也没有一行的做法，只能写循环
	for i, j := 0, len(vector)-1; i<j; i, j = i+1, j-1{
		vector[i], vector[j] = vector[j], vector[i]
	}
	fmt.Println(vector)

	var backup []int      // 复制
	copy(backup, vector)
	fmt.Println(backup)

	vector = vector[:0]                            // clear()
	fmt.Println(len(vector), cap(vector), vector)  // cpp vector中的clear()只是将size()置为0, 并没有释放分配的内存

	vector = nil          // 全部释放
	fmt.Println(len(vector), cap(vector), vector)
}

其他：

slice应该不能实现resize() , 底层数组的改变不受用户自主控制
此外批量初始化，例如n个1，应该需要写循环

参考资料： https://ueokande.github.io/go-slice-tricks/

Slice详解#

基础用法#

扩容机制#

GC#

slice的花式用法#

用slice实现cpp中vector的主要功能#

Slice详解

基础用法

扩容机制

GC

slice的花式用法

用slice实现cpp中vector的主要功能