切片(Slice)作为Golang中的一个核心数据结构,在处理动态数据集合时起着至关重要的作用。
本文将从切片的基本概念出发,详细介绍切片的使用方法和底层原理,并深入探讨切片的截取、复制、数据引用、扩容原理以及截取原理,最后给出切片的完整复制方法,以帮助读者更深入地理解和使用切片。
切片是一个动态数组,由指针(Data)、长度(Len)和容量(Cap)组成。它提供了一种便捷的方式来操作数组,支持动态调整大小和共享底层数组。
// runtime/slice.go
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
指针指向切片元素对应的底层数组元素的地址。长度对应切片中元素的数目,长度不能超过容量。容量是从切片的开始位置到底层数据的结尾位置的长度。
内置的len和cap函数可以分别获取切片的长度和容量。
```Go
slice := make([]int, 5, 10)
l := len(slice) // 5
c := cap(slice) // 10
切片的声明与数组类似,但不需要指定大小。在只声明不赋初始值的情况下,切片的值为nil。切片的初始化需要使用make函数。在下面的例子中,slice1未指定容量,则默认其容量与长度相同
var slice1 []int // nil
slice2 := []int{1, 2, 3, 4, 5}
slice1 := make([]int, 5)
slice2 := make([]int, 5, 10)
当使用形如[]int{1, 2, 3, 4, 5}的字面量创建新的切片时,会创建一个array数组([5]int{1, 2, 3, 4, 5})存储于静态区中,并在堆区创建一个新的切片,在程序启动时将静态区的数据复制到堆区,这样可以加快切片的初始化过程。
如果使用 make
函数初始化一个太大的切片,该切片会逃逸到堆中;如果分配的是一个较小的切片,则会直接在栈中分配。这个临界值由 cmd/compile/internal/gc.maxImplicitStackVarSize
变量定义,默认值为 64KB
。可以通过在编译时指定 smallframes
标识来更新此值。因此,make([]int64, 1023)
与 make([]int64, 1024)
的实现细节是截然不同的。
如果发生了逃逸,那么运行时调用 runtime/slice.go
下的makeslice
函数会将切片分配在堆中。当切片的长度和容量小于int类型的最大值时,会调用 makeslice
函数,反之调用 makeslice64
函数创建切片。makeslice64
函数最终也调用了makeslice函数。
makeslice
函数会先判断要申请的内存大小是否超过了系统可以分配的内存,并判断长度是否小于容量,再调用 mallocgc
函数在堆中申请内存,申请的内存大小为类型大小×容量。
// runtime/slice.go
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 {
// NOTE: Produce a 'len out of range' error instead of a
// 'cap out of range' error when someone does make([]T, bignumber).
// 'cap out of range' is true too, but since the cap is only being
// supplied implicitly, saying len is clearer.
// See golang.org/issue/4085.
mem, overflow := math.MulUintptr(et.Size_, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
return mallocgc(mem, et, true)
}
func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
len := int(len64)
if int64(len) != len64 {
panicmakeslicelen()
}
cap := int(cap64)
if int64(cap) != cap64 {
panicmakeslicecap()
}
return makeslice(et, len, cap)
}
切片截取通过下标来实现,可以获取切片的子集。被截取后的切片,其长度和容量都发生了变化,但是被截取后的数组仍然指向原始切片的底层数据
slice := []int{1, 2, 3, 4, 5}
subSlice1 := slice[1:3] // 获取索引为1到2的元素,不包括3
subSlice2 := slice[:3] // 获取索引为0到2的元素,不包括3
subSlice3 := slice[3:] // 获取索引为3到末尾的元素
我们来分析 subSlice1
的长度和容量。
subSlice1
的长度由其元素数目决定。通过 [1:3]
的索引表达式,subSlice1
包含从索引 1 到索引 2 的元素(不包括索引 3 的元素)。所以,subSlice1
包含以下元素:
subSlice1 = slice[1:3] // {2, 3}
因此,subSlice1
的长度为 2。
切片的容量是从切片的起始位置到其底层数组的结尾之间的元素数量。在这个例子中,slice
的底层数组是 {1, 2, 3, 4, 5}
,subSlice1
的起始位置是索引 1,底层数组的长度是 5。所以,subSlice1
的容量是从索引 1 到数组末尾的元素数量。
具体地,subSlice1
的容量计算如下:
capacity = len(slice) - start_index_of_subSlice1
= 5 - 1
= 4
另外由于被截取后的数组仍然指向原始切片的底层数据,所以当修改 subSlice1[0]
号元素时,底层数据的对应元素也会跟着改变。
在Go中,数组的复制是值复制,对数组的副本修改不会影响到原数组。切片的复制虽然也是值复制,但这里的值复制指对于运行时SliceHeader结构的复制,底层指针(Data)仍然指向相同的底层数据的数组地址,因此可以理解为数据进行了引用传递。
slice := []int{1, 2, 3, 4, 5}
fmt.Println(slice) // [1 2 3 4 5]
slice1 := slice
fmt.Println(slice1) // [1 2 3 4 5]
slice1[0] = 9999
fmt.Println(slice) // [9999 2 3 4 5]
fmt.Println(slice1) // [9999 2 3 4 5]
当使用make函数初始化切片后,再通过copy函数复制,尽管他们拥有相同的元素,但是此时修改一个不会影响另一个。
slice1 := []int{1, 2, 3, 4, 5}
slice2 := make([]int, len(slice1))
copy(slice2, slice1)
复制的切片不会改变指向底层的数据源,但有些时候我们希望建一个新的数组,并且与旧数组不共享相同的数据源,这时可以使用copy函数,其逻辑是新建一个内存,并复制过去。
Go的append函数可以添加新的元素到切片的末尾,它可以接受可变长度的元素,并且可以自动扩容。扩容是一个动态的过程,当切片容量不足以容纳新元素时,会自动扩容。扩容规则通常是当前容量的两倍。
Go中切片扩容的策略为:
扩容的核心逻辑位于 runtime/slice.go
文件下的 growslice
函数,growslice
函数会根据切片的类型,分配不同大小的内存。为了对齐内存,申请的内存可能大于实际的类型大小×容量大小。growslice
函数还会判断切片类型是否是指针,根据判断执行不同逻辑。
...
var p unsafe.Pointer
if !et.Pointers() {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from oldLen to newLen.
// Only clear the part that will not be overwritten.
// The reflect_growslice() that calls growslice will manually clear
// the region not cleared here.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in oldPtr since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
//
// It's safe to pass a type to this function as an optimization because
// from and to only ever refer to memory representing whole values of
// type et. See the comment on bulkBarrierPreWrite.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
}
}
memmove(p, oldPtr, lenmem)
return slice{p, newLen, newcap}
memmove(p, oldPtr, lenmem)
函数用于将旧切片的值赋给新的切片。
如果切片需要扩容,那么最后需要到堆区申请内存。在大多数情况下,切片扩容时会分配一个新的、更大的底层数组,并将现有元素复制到新数组中。这会导致切片指向新的内存地址。但是如果切片的容量尚未达到其底层数组的物理容量限制,扩容时可以在现有的底层数组上进行调整。在这种情况下,切片指向的底层数组的内存地址不会改变。
在Go中,切片是基于数组的抽象数据结构。切片本质上包含三个属性:指向底层数组的指针、切片的长度以及切片的容量。当我们创建一个新的切片(例如 slice1 := slice[1:]),这个新切片仍然指向原来的底层数组,但其起始位置、长度和容量可能会有所不同。
slice := []int32{1, 2, 3, 4, 5}
slice1 := slice[1:] // 删除第一个元素
fmt.Printf("%p %p", slice, slice1) // 0xc00001ade0 0xc00001ade4
二者的地址正好相差4字节,这不是偶然的。在上面的代码中,slice
和 slice1
共享同一个底层数组,但它们的起始位置不同。
具体来说:slice
和 slice1
的内存地址(切片变量的地址)通常不会直接打印。这是因为切片是结构体,其内部包含一个指向底层数组的指针、长度和容量信息。这些信息存储在切片头部结构中,地址打印的是指向这些头部结构的指针。新切片 slice1
指向相同的底层数组,但它的起始位置是底层数组的第二个元素。而在底层数组中,int32 类型的每个元素占用 4 个字节。
删除切片的第一个和最后一个元素都很简单。如果要删除切片中间的某一段或某一个元素,可以通过截取删除元素前后的切片数组,再使用append函数拼接的方式实现。这种处理方式效率很高,因为它不会申请额外的内存空间。
slice := []int{1, 2, 3, 4, 5}
slice = slice[1:] // 删除第一个元素
fmt.Println(slice) // [2 3 4 5]
slice = slice[:len(slice)-1] // 删除最后一个元素
fmt.Println(slice) // [2 3 4]
point := len(slice) / 2
slice = append(slice[:point], slice[point+1:]...)
fmt.Println(slice) // [2 4]
切片在赋值拷贝与下标截断时引用了相同的底层数据。如果要完全拷贝切片,则使用copy函数。其逻辑是新建一个内存,并复制过去。在极端情况下需要考虑其对性能的影响。
切片字面量的初始化,会以数组的形式存储于静态区中。在使用make函数初始化时,如果make函数初始化了一个大于64KB的切片,那么这个切片会逃逸到堆中,在运行时调用makeslice函数创建切片,小于64KB的切片直接在栈中初始化。
Go语言中内置append函数用于添加元素,当容量超过了现有容量时,切片需要进行扩容,其策略是:
Comments