Golang数据类型之 slice 源码实现

golang 中的 slice 源码

Slice的数据结构

切片是对数组的一个连续片段的引用,所以切片是一个引用类型,一个长度可变的数组。 源码中的数据结构定义如下:

源码位置: src/runtime/slice.go#L22

1
2
3
4
5
type slice struct {
 array unsafe.Pointer  // 引用的底层数组指针
 len   int             // 切片的长度
 cap   int             // 切片的容量
}

slice-structure

创建切片

创建方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func main() {
 // 1. 通过关键字 var 声明,此时未初始化,无法对s1[i]进行取值、赋值
 var s1 []int

 // 2. 使用 new() 创建,由于 new()返回的是一个指针,通过 *获取指针的值,未初始化,同样也无法对s2[i]进行取值赋值
 s2 := *new([]int)

 // 3. 直接创建并初始化,已初始化,因此可以对s3[i]进行取值赋值
 s3 := []int{1, 2, 3}

 // 4. make() 创建,第一个参数指定类型,第二个参数为长度,第三个参数为容量(可不指定,默认为长度值)
 s4 := make([]int, 4, 5)

 // 5. 通过截取数组或切片
 array := [7]int{1, 2, 3, 4, 5, 6, 7}
 s5 := array[3:5] // (左闭右开),输出 [4,5],引用数组 array 的部分片段
}

创建逻辑

src/runtime/slice.go#L88

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// input: et: slice类型元信息,slice长度,slice容量
func makeslice(et *_type, len, cap int) unsafe.Pointer {
   // 调用MulUintptr函数:获取创建该切片需要的内存,是否溢出(超过2^64)
    // 2^64是64位机能够表示的最大内存地址
 mem, overflow := math.MulUintptr(et.size, uintptr(cap))
 if overflow || mem > maxAlloc || len < 0 || len > cap {

  mem, overflow := math.MulUintptr(et.size, uintptr(len))
    // 如果溢出或超过能够分配的最大内存(2^32 - 1) | 非法输入, 报错并返回
  if overflow || mem > maxAlloc || len < 0 {
   panicmakeslicelen()
  }
  panicmakeslicecap()
 }

  // 调用mallocgc函数分配一块连续内存并返回该内存的首地址
  // 该函数实现涉及到了go语言内存管理,比较复杂,不是本文的主题
  // 关于 mallocgc 逻辑后续再讲
 return mallocgc(mem, et, true)
}
  • 根据slice的类型和长度以及容量,计算出所需要的内存空间大小,
  • 如果合法则调用mallocgc函数申请相应的连续内存并返回首地址,

下面来看一下是如何计算所需要的内存大小的

src\runtime\internal\math\math.go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// MulUintptr returns a * b and whether the multiplication overflowed.
// On supported platforms this is an intrinsic lowered by the compiler.
func MulUintptr(a, b uintptr) (uintptr, bool) {
    // 如果slice类型大小为0(如struct{}类型) 或 (a | b) < 2 ^ 32,肯定不会发生溢出
    // sys.PtrSize = 8
 if a|b < 1<<(4*sys.PtrSize) || a == 0 {
  return a * b, false
 }
  // 如果a * b > MaxUintptr,即类型大小 * 切片容量 > MaxUintPtr,则说明发生了溢出
  // MaxUintptr = ^uintptr(0) = 2 ^ 64
 overflow := b > MaxUintptr/a
 return a * b, overflow
}

追加元素

append()

src/reflect/value.go

 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
// Append appends the values x to a slice s and returns the resulting slice.
// As in Go, each x's value must be assignable to the slice's element type.
func Append(s Value, x ...Value) Value {
 s.mustBe(Slice)
 s, i0, i1 := grow(s, len(x))
 for i, j := i0, 0; i < i1; i, j = i+1, j+1 {
  s.Index(i).Set(x[j])
 }
 return s
}

// grow grows the slice s so that it can hold extra more values, allocating
// more capacity if needed. It also returns the old and new slice lengths.
func grow(s Value, extra int) (Value, int, int) {
 i0 := s.Len()
 i1 := i0 + extra
 if i1 < i0 {
  panic("reflect.Append: slice overflow")
 }
 m := s.Cap()
 if i1 <= m {
  return s.Slice(0, i1), i0, i1
 }
 if m == 0 {
  m = extra
 } else {
  // const threshold = 256  // 1.18增加
  for m < i1 {
   if i0 < 1024 {
    m += m
   } else {
    m += m / 4
   }
  }
 }
 t := MakeSlice(s.Type(), i1, m)
 Copy(t, s)
 return t, i0, i1
}

追加元素流程如下:

  • 计算当前slice长度i0与追加元素的长度总和i1,若i1 < i0(追加后的slice长度小于当前的slice长度),则直接抛出异常
  • 若当前切片容量为0,则将容量改为追加元素的长度
  • 循环遍历增加容量,
  • 若追加的元素长度小于阈值(v1.18之前是1024,从v1.18开始改为256),则容量成倍增长,
  • 否则容量每次增加1/4,(注:v1.18开始计算逻辑改为 m = (m + 3 * threshold) / 4) ,
  • 创建新的切片,并将当前切片拷贝到新的切片中,返回新的切片
  • 将追加的元素存储到新的切片指定位置

切片的扩容逻辑:

  • 原cap扩充一倍,即doublecap
  • 如果指定cap(追加元素后的切片长度) 大于 doublecap,则取cap,否则如下:
      • cap 小于1024,取doublecap
      • 每次增长 1/4,直至不小于cap
皖ICP备20014602号
Built with Hugo
Theme Stack designed by Jimmy