GoSlice
Go
基本使用
SliceGoGo
var s []int // 声明一个整型切片
var s1 []string // 声明一个字符串切片
s :=[]int {1, 2, 3}
// 创建一个长度为3、容量为5的整形切片
slice := make([]int, 3, 5)
// 创建一个长度为3、容量为3的字符串切片
slice2 := make([]string, 3)
// 创建一个包含5个整数的数组
arr := [5]int{1, 2, 3, 4, 5}
// 创建一个从arr[1]开始到arr[3]结束的切片
slice1 := arr[1:4]
// 创建一个新切片,容量等于原始切片的长度
slice2 := slice1[:]
// 创建一个包含5个整数的数组
arr := [5]int{1, 2, 3, 4, 5}
slice1 := arr[1:4]
slice1[0] = 6
fmt.Println(arr) // 输出:[1 6 3 4 5]
fmt.Println(slice1) // 输出:[6 3 4]
// 创建一个包含3个元素的整数数组
arr := [3]int{1, 2, 3}
// 创建一个包含arr[1]和arr[2]的切片
slice := arr[1:3]
// 访问切片中的元素
fmt.Println(slice[0]) // 输出:2
fmt.Println(slice[1]) // 输出:3
// 创建一个空的切片
var slice []int
// 向切片中追加元素
slice = append(slice, 1, 2, 3)
// 输出切片中的元素
fmt.Println(slice) // 输出:[1 2 3]
// 向切片中追加元素
slice = append(slice, 4)
fmt.Println(slice) // 输出:[1 2 3 4]
// 创建一个包含5个整数的切片
s := []int{1, 2, 3, 4, 5}
// for循环遍历切片
for i := 0; i < len(s); i++ {
println(s[i])
}
// for range遍历切片
for key, value := range s {
println(key, value)
}
// 创建一个包含3个元素的整数数组
arr1 := [3]int{1, 2, 3}
// 创建一个包含arr1[1]和arr1[2]的切片
slice1 := arr1[1:3]
// 创建一个长度为2、容量为4的空切片
slice2 := make([]int, 2, 4)
// 将slice1中的元素复制到slice2中
copy(slice2, slice1)
// 输出slice2中的元素
fmt.Println(slice2) // 输出:[2 3]
// 创建一个包含5个元素的整数切片
slice := []int{5, 2, 6, 3, 1}
// 对切片进行排序
sort.Ints(slice)
// 输出排序后的切片
fmt.Println(slice) // 输出:[1 2 3 5 6]
// 创建一个包含重复元素的整数切片
slice := []int{1, 2, 3, 2, 1}
// 创建一个空的map,用于存储不重复的元素
m := make(map[int]bool)
// 遍历切片中的元素,并将其存储到map中
for _, v := range slice {
m[v] = true
}
// 将map中的元素存储到一个新的切片中
newSlice := []int{}
for k := range m {
newSlice = append(newSlice, k)
}
// 输出去重后的切片
fmt.Println(newSlice) // 输出:[1 2 3]
底层实现原理
数据结构
在前面说到过切片是建立在数组之上的,就像是文件描述符之于文件。数组退居幕后,承担起底层存储空间,而切片走向前台,给开发者一个更便捷使用数组的窗口。
来看看切片的底层类型定义:
//go 1.20.3 path: /src/runtime/slice.go
type slice struct {
array unsafe.Pointer
len int
cap int
}
arraylencap
Go
sliceSlicesliceGoGoslice
Slice
//go 1.20.3 path: /src/internal/unsafeheader/unsafeheader.go
type Slice struct {
Data unsafe.Pointer
Len int
Cap int
}
GoGo
SliceDataData
SliceHeaderruntime
//go 1.20.3 path: /src/reflect/value.go
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
DataLenCapGo
SliceHeaderCC
SliceHeader
func Foo(ptr unsafe.Pointer, len, cap int) {
// do something with ptr, len, cap
}
func main() {
s := []int{1, 2, 3, 4, 5}
header := (*reflect.SliceHeader)(unsafe.Pointer(&s))
Foo(unsafe.Pointer(header.Data), header.Len, header.Cap)
}
unsafe.Pointer*reflect.SliceHeaderSliceHeaderDataLenCapCFoo
SliceHeaderSliceHeaderData
声明
Go
var x []int
var y []interface{}
intinterface{}
所以我们需要有个对应的结构体来满足声明中的只定义类型的情况,这个切片在编译期间对应的结构体如下:
//go 1.20.3 path: /src/cmd/complie/internal/types/type.go
type Slice struct {
Elem *Type // element type
}
Go
Slice
具体地说,我们可以使用这个结构体来创建一个动态类型的切片,如下所示:
s := Slice{Elem: (*int)(nil)}
int
s.Elem = (*string)(nil)
stringGo
NewSliceSlice
func NewSlice(elem *Type) *Type {
if t := elem.Cache.slice; t != nil {
if t.Elem() != elem {
Fatalf("elem mismatch")
}
return t
}
t := New(TSLICE)
t.Extra = Slice{Elem: elem}
elem.Cache.slice = t
return t
}
ExtraExtra
初始化
Go 语言中包含三种初始化切片的方式:
slice := []int{1, 2, 3, 4, 5}
newSlice := slice[0:3]
package main
func newSlice() []int {
arr := [5]int{1, 2, 3, 4, 5}
slice := arr[0:3]
return slice
}
func main(){}
//创建并初始化一个slice
s := []string{"a", "b", "c"}
//基于slice创建一个新的slice:s1
s1 := s[0:1]
//基于slice创建一个新的slice:s2
s2 := s[:]
//获取s1,s2的SliceHeader结构
sc1 := (*reflect.SliceHeader)(unsafe.Pointer(&s1))
sc2 := (*reflect.SliceHeader)(unsafe.Pointer(&s2))
//输出s1,s2的底层数组指针、长度、容量
fmt.Println(sc1.Data, sc1.Len, sc1.Cap) //输出:824634322752 1 3
fmt.Println(sc2.Data, sc2.Len, sc2.Cap) //输出:824634322752 3 3
//创建并初始化一个slice
s := []string{"a", "b", "c"}
//基于slice创建一个新的slice:s1
s1 := s[0:1]
//基于slice创建一个新的slice:s2
s2 := s[:]
s1[0] = "d"
fmt.Println(s, s1, s2) //输出 [d b c] [d] [d b c]
slice := []int{1, 2, 3}
var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice := vauto[:]
slice := make([]int, 3, 3)
slice1 := make([]int, 3)
// go1.20.3 path:/src/cmd/compile/internal/walk/expr.go
func walkExpr1(n ir.Node, init *ir.Nodes) ir.Node {
switch n.Op() {
......
case ir.OMAKESLICE:
n := n.(*ir.MakeExpr)
return walkMakeSlice(n, init)
......
}
}
// go1.20.3 path:/src/cmd/compile/internal/walk/builtin.go
func walkMakeSlice(n *ir.MakeExpr, init *ir.Nodes) ir.Node {
//获取切片的长度
l := n.Len
//获取切片的容量
r := n.Cap
//如果容量为空,那么容量等于长度
if r == nil {
r = safeExpr(l, init)
l = r
}
// 获取切片的类型
t := n.Type()
// 判断元素类型是否不能在堆上分配内存
if t.Elem().NotInHeap() {
base.Errorf("%v can't be allocated in Go; it is incomplete (or unallocatable)", t.Elem())
}
//如果切片的逃逸状态为EscNone,即不逃逸,在栈上分配内存
if n.Esc() == ir.EscNone {
// 如果逃逸状态为EscNone,但是切片的逃逸状态为EscHeap,那么报错
if why := escape.HeapAllocReason(n); why != "" {
base.Fatalf("%v has EscNone, but %v", n, why)
}
//获取切片容量的值
i := typecheck.IndexConst(r)
if i < 0 {
base.Fatalf("walkExpr: invalid index %v", r)
}
/**
检查切片长度和容量是否合法,不合法则报错
*/
//判断切片的长度是否大于容量
nif := ir.NewIfStmt(base.Pos, ir.NewBinaryExpr(base.Pos, ir.OGT, typecheck.Conv(l, types.Types[types.TUINT64]), ir.NewInt(i)), nil, nil)
//判断切片的长度是否小于0
niflen := ir.NewIfStmt(base.Pos, ir.NewBinaryExpr(base.Pos, ir.OLT, l, ir.NewInt(0)), nil, nil)
niflen := ir.NewIfStmt(base.Pos, ir.NewBinaryExpr(base.Pos, ir.OLT, l, ir.NewInt(0)), nil, nil)
//如果切片长度小于0,那么报错
niflen.Body = []ir.Node{mkcall("panicmakeslicelen", nil, init)}
//如果切片的容量小于长度,那么报错
nif.Body.Append(niflen, mkcall("panicmakeslicecap", nil, init))
init.Append(typecheck.Stmt(nif))
//构造一个数组,类型为 [r]T
t = types.NewArray(t.Elem(), i)
//生成一个临时变量,类型为 [r]T
var_ := typecheck.Temp(t)
//将临时变量赋值为nil
appendWalkStmt(init, ir.NewAssignStmt(base.Pos, var_, nil)) // zero temp
//构造一个切片表达式,arr[:l]
r := ir.NewSliceExpr(base.Pos, ir.OSLICE, var_, nil, l, nil) // arr[:l]
//递归调用walkExpr,将切片表达式转换为语句
return walkExpr(typecheck.Expr(typecheck.Conv(r, n.Type())), init)
}
//获取切片的长度和容量
len, cap := l, r
//默认调用makeslice64函数
fnname := "makeslice64"
//默认参数类型为int64
argtype := types.Types[types.TINT64]
// 如果 len 和 cap 都是 ideal 类型(即编译器无法确定其具体类型),或者它们的大小小于或等于 uint 类型的大小,那么它们可以被转换为 int 类型,并用于调用 makeslice 函数
if (len.Type().IsKind(types.TIDEAL) || len.Type().Size() <= types.Types[types.TUINT].Size()) &&
(cap.Type().IsKind(types.TIDEAL) || cap.Type().Size() <= types.Types[types.TUINT].Size()) {
fnname = "makeslice"
argtype = types.Types[types.TINT]
}
// 根据函数名查找对应的runtime函数
fn := typecheck.LookupRuntime(fnname)
// 调用runtime函数进行slice初始化
ptr := mkcall1(fn, types.Types[types.TUNSAFEPTR], init, reflectdata.MakeSliceElemRType(base.Pos, n), typecheck.Conv(len, argtype), typecheck.Conv(cap, argtype))
// 标记slice的底层数组不为nil
ptr.MarkNonNil()
// 转换slice的长度为int类型
len = typecheck.Conv(len, types.Types[types.TINT])
// 转换slice的容量为int类型
cap = typecheck.Conv(cap, types.Types[types.TINT])
// 构造slice的头部信息
sh := ir.NewSliceHeaderExpr(base.Pos, t, ptr, len, cap)
// 返回对slice头部信息的处理结果
return walkExpr(typecheck.Expr(sh), init)
}
// go 1.20.3 path :/src/cmd/compile/internal/ir/cfg.go
var (
// MaxStackVarSize is the maximum size variable which we will allocate on the stack.
// This limit is for explicit variable declarations like "var x T" or "x := ...".
// Note: the flag smallframes can update this value.
MaxStackVarSize = int64(10 * 1024 * 1024)
// MaxImplicitStackVarSize is the maximum size of implicit variables that we will allocate on the stack.
// p := new(T) allocating T on the stack
// p := &T{} allocating T on the stack
// s := make([]T, n) allocating [n]T on the stack
// s := []byte("...") allocating [n]byte on the stack
// Note: the flag smallframes can update this value.
MaxImplicitStackVarSize = int64(64 * 1024)
)
// go 1.20.3 path :/src/runtime/slice.go
func makeslice(et *_type, len, cap int) unsafe.Pointer {
//计算 lice占用的内存大小,mem = element size * cap以及溢出检查
mem, overflow := math.MulUintptr(et.size, uintptr(cap))
// 如果溢出或者内存大小超过了 maxAlloc(最大可分配虚拟内存)或者如果len大于cap或者len小于0,则 panic
if overflow || mem > maxAlloc || len < 0 || len > cap {
//计算 slice 占用的内存大小,当容量不合法时会使用它来判断长度是否合法
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
// slice 长度或容量不合法时 panic
panicmakeslicelen()
}
// slice 长度或容量不合法时 panic
panicmakeslicecap()
}
//调用mallocgc 函数分配内存
return mallocgc(mem, et, true)
}
访问元素
lencap
slice := []int{1, 2, 3, 4, 5}
l := len(slice) //获取长度
c := cap(slice) //获取容量
OLENOCAPexprCheckPtrSSAOpSliceLenOpSliceCap
// go 1.20.3 path: /src/cmd/compile/internal/ssagen/ssa.go
func (s *state) exprCheckPtr(n ir.Node, checkPtrOK bool) *ssa.Value {
......
switch n.Op() {
case OLEN, OCAP:
switch {
case n.X.Type().IsSlice():
op := ssa.OpSliceLen
if n.Op() == ir.OCAP {
op = ssa.OpSliceCap
}
return s.newValue1(op, types.Types[types.TINT], s.expr(n.X))
......
}
......
}
}
len(slice)cap(slice)
(SlicePtr (SliceMake ptr _ _ )) -> ptr
(SliceLen (SliceMake _ len _)) -> len
(SliceCap (SliceMake _ _ cap)) -> cap
OINDEXOINDEX
func (s *state) exprCheckPtr(n ir.Node, checkPtrOK bool) *ssa.Value {
......
// 根据n的操作符进行分支
switch n.Op() {
......
//如果 n 的操作符是 OINDEX,表示切片索引访问
case ir.OINDEX:
// 将 n 转换为 IndexExpr 类型,表示一个索引表达式,例如 x[i]
n := n.(*ir.IndexExpr)
switch {
//如果 n.X 的类型为切片类型,则获取该切片的指针地址 p,并读取该地址中的元素值,作为最终的返回值
case n.X.Type().IsSlice():
p := s.addr(n)
return s.load(n.X.Type().Elem(), p)
}
......
}
......
}
复制
copy
s := []string{"a", "b", "c"}
s2 := make([]string, len(s))
copy(s2, s)
fmt.Println(s) //输出 [a b c]
fmt.Println(s2) //输出 [a b c]
slicecopy()memmove
// go 1.20.3 path: /src/runtime/slice.go
// 定义一个函数,接收两个切片的指针、长度和元素宽度,返回复制的元素个数
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
// 如果源切片或目标切片的长度为 0
if fromLen == 0 || toLen == 0 {
// 返回 0,表示没有复制任何元素
return 0
}
// 将 n 赋值为源切片的长度
n := fromLen
// 如果目标切片的长度小于 n
if toLen < n {
// 将 n 赋值为目标切片的长度
n = toLen
}
// 如果元素宽度为 0
if width == 0 {
// 返回 n,表示复制了 n 个元素,但实际上没有复制任何数据
return n
}
// 计算需要复制的数据的总大小,等于 n 乘以元素宽度
size := uintptr(n) * width
......
// 如果数据大小为 1
if size == 1 {
// 直接将源切片指针指向的字节赋值给目标切片指针指向的字节
*(*byte)(toPtr) = *(*byte)(fromPtr)
} else {
// 调用 memmove 函数,将源切片指针指向的 size 大小的数据移动到目标切片指针指向的位置
memmove(toPtr, fromPtr, size)
}
// 返回 n,表示复制了 n 个元素
return n
}
runtime.memmove
上述流程如下图:
扩容
append
s := []int{1, 2, 3, 4, 5}
s = append(s, 7, 8, 9)
fmt.Println("s:", s)
//output:
s: [1 2 3 4 5 7 8 9]
/src/cmd/compile/internal/ssagen/ssa.goappend
// If inplace is false, process as expression "append(s, e1, e2, e3)":
ptr, len, cap := s
len += 3
if uint(len) > uint(cap) {
ptr, len, cap = growslice(ptr, len, cap, 3, typ)
}
// with write barriers, if needed:
*(ptr+(len-3)) = e1
*(ptr+(len-2)) = e2
*(ptr+(len-1)) = e3
return makeslice(ptr, len, cap)
// If inplace is true, process as statement "s = append(s, e1, e2, e3)":
a := &s
ptr, len, cap := s
len += 3
if uint(len) > uint(cap) {
ptr, len, cap = growslice(ptr, len, cap, 3, typ)
vardef(a) // if necessary, advise liveness we are writing a new a
*a.cap = cap // write before ptr to avoid a spill
*a.ptr = ptr // with write barrier
}
*a.len = len
// with write barriers, if needed:
*(ptr+(len-3)) = e1
*(ptr+(len-2)) = e2
*(ptr+(len-1)) = e3
Go
runtime.growslice
//go 1.20.3 path: /src/runtime/slice.go
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
// 计算旧切片的长度,等于新切片的长度减去要添加的元素个数
oldLen := newLen - num
......
// 如果新切片的长度为负数,说明溢出了,直接panic
if newLen < 0 {
panic(errorString("growslice: len out of range"))
}
//如果元素类型的大小为0,说明是空切片,直接返回一个新的切片
if et.size == 0 {
return slice{unsafe.Pointer(&zerobase), newLen, newLen}
}
// 定义一个新的切片容量newcap,初始值为旧切片的容量
newcap := oldCap
//定义一个新的切片doublecap,初始值为旧切片容量的两倍
doublecap := newcap + newcap
if newLen > doublecap {
//如果新切片长度大于doublecap(旧切片容量的两倍),则新切片容量为新切片长度
newcap = newLen
} else {
//否则,定义一个常量threshold,等于256
const threshold = 256
if oldCap < threshold {
//如果旧切片容量小于256,则新切片容量为(doublecap)旧切片容量的两倍
newcap = doublecap
} else {
//循环增加新切片容量,直到大于或者等于新切片长度或者溢出
for 0 < newcap && newcap < newLen {
//每次增加新切片容量的四分之一
newcap += (newcap + 3*threshold) / 4
}
//如果新切片容量小于等于0,则新切片容量等于新切片长度
if newcap <= 0 {
newcap = newLen
}
}
}
......
}
这段代码是用来扩展切片的容量的,代码的逻辑如下:
oldLennewLen - num0
182
//go 1.20.3 path: /src/runtime/slice.go
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
......
//定义一个变量overflow,初始值为false,用来表示是否溢出
var overflow bool
//定义三个变量,分别表示旧切片、新切片、新切片的容量的内存大小
var lenmem, newlenmem, capmem uintptr
//根据元素类型的大小,计算旧切片的长度、新切片的长度、新切片的容量
switch {
/**
如果元素类型的大小为1
则旧切片长度内存大小等于旧切片长度
新切片长度内存大小等于新切片长度
新切片容量内存大小等于新容量向上取整到对齐边界
更新新容量为内存大小转换的整数类型
*/
case et.size == 1:
lenmem = uintptr(oldLen)
newlenmem = uintptr(newLen)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
/**
如果元素类型的大小等于指针的大小
则旧切片长度内存大小等于旧切片长度乘以指针的大小
新切片长度内存大小等于新切片长度乘以指针的大小
新切片容量内存大小等于新容量乘以指针的大小向上取整到对齐边界
更新新容量为新容量内存大小除以指针的大小的整数
*/
case et.size == goarch.PtrSize:
lenmem = uintptr(oldLen) * goarch.PtrSize
newlenmem = uintptr(newLen) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)
/**
如果元素类型的大小是2的幂次方
*/
case isPowerOfTwo(et.size):
//定义一个变量shift,用来表示左移或者右移的位数
var shift uintptr
//主要是区分32位和64位系统
if goarch.PtrSize == 8 {
//如果指针的大小是8,则shift等于元素类型的大小转换为64位无符号整数末尾0的个数,并与63进行与运算
shift = uintptr(sys.TrailingZeros64(uint64(et.size))) & 63
} else {
//否则,shift等于元素类型的大小转换为32位无符号整数末尾0的个数,并与31进行与运算
shift = uintptr(sys.TrailingZeros32(uint32(et.size))) & 31
}
//旧切片长度内存大小等于旧切片长度左移shift位
lenmem = uintptr(oldLen) << shift
//新切片长度内存大小等于新切片长度左移shift位
newlenmem = uintptr(newLen) << shift
//新切片容量内存大小等于新容量左移shift位向上取整到对齐边界
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
//更新新容量为新容量内存大小右移shift位
newcap = int(capmem >> shift)
//更新新容量内存大小为新容量左移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)
newcap = int(capmem / et.size)
capmem = uintptr(newcap) * et.size
}
//如果溢出或者新切片容量内存大小大于最大分配内存大小,则抛出异常
if overflow || capmem > maxAlloc {
panic(errorString("growslice: len out of range"))
}
......
}
Go
runtime.roundupsizeruntime.class_to_size
var class_to_size = [_NumSizeClasses]uint16{
0,
8,
16,
32,
48,
64,
80,
...,
}
确认完新切片长度容量后,接下来执行下面代码:
//go 1.20.3 path: /src/runtime/slice.go
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
......
//定义一个变量p,用来表示新切片的指针
var p unsafe.Pointer
/**
如果元素类型的指针数据为0;
则调用mallocgc函数,分配新切片的内存,不指定类型,不需要扫描;
调用memclrNoHeapPointers函数,清零新切片未使用的内存部分;
否则,调用mallocgc函数,分配新切片的内存,指定类型,需要扫描;
如果旧切片的内存大小大于0,并且写屏障开启
则调用bulkBarrierPreWriteSrcOnly函数,对新旧切片的内存进行写屏障处理
*/
if et.ptrdata == 0 {
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.ptrdata)
}
}
//调用memmove函数,将旧切片的内存内容复制到新切片的内存地址
memmove(p, oldPtr, lenmem)
//返回一个新的slice结构体,包含新切片的内存地址、长度和容量
return slice{p, newLen, newcap}
}
该段代码的作用是根据新切片的容量和元素类型,分配新切片的内存空间,并将旧切片的内容复制过去。它根据元素类型是否包含指针数据,采用不同的内存分配和清零策略,以提高内存安全性和效率。它还根据写屏障的状态,对新旧切片的内存进行必要的屏障处理,以保证垃圾回收的正确性。
小结
切片的使用和内部原理在Go语言中非常重要,因此有一些小结或者使用建议可以帮助我们更好地理解和使用切片,例如:
copyappend0appendmake
切片的很多功能都是由运行时实现的,无论是初始化切片,还是对切片进行追加或扩容都需要运行时的支持,需要注意的是在遇到大切片扩容或者复制时可能会发生大规模的内存拷贝,一定要减少类似操作避免影响程序的性能。
参考资料:
Draven https://draveness.me/golang/