Strcpy

Slice的初始化和扩容过程

源代码/数据集已上传到 Github - posts

切片和数组在go语言中都是非常常见的结构,很多刚开始使用go语言的开发者会混淆这两者的概念而留下不少隐藏的bug。本篇会从slice编译期、运行时来分析,以更好理解和掌握slice。

slice概述

slice表示一个拥有相同数据类型的可变长度的序列。
该序列通过一个较为简单的数据结构实现:https://github.com/golang/go/blob/master/src/runtime/slice.go#L15

1
2
3
4
5
type slice struct {
array unsafe.Pointer
len int
cap int
}

编译期逻辑

编译的整个过程另外开文章说,下面直接讲slice的编译过程。 感兴趣可以先看 src/cmd/compile/main.go

在slice的编译过程中,会调用NewSlice方法,该方法需传入类型为*Type的参数elem,并且返回一个*Type类型的结构体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// NewSlice returns the slice Type with element type elem.
func NewSlice(elem *Type) *Type {
if t := elem.cache.slice; t != nil {
if t.Elem() != elem {
base.Fatalf("elem mismatch")
}
if elem.HasShape() != t.HasShape() {
base.Fatalf("Incorrect HasShape flag for cached slice type")
}
return t
}

t := newType(TSLICE)
t.extra = Slice{Elem: elem}
elem.cache.slice = t
if elem.HasShape() {
t.SetHasShape(true)
}
return t
}

进入Slice{Elem: elem},slice的数据结构如下:

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
// Slice contains Type fields specific to slice types.
type Slice struct {
Elem *Type // element type
}

type Type struct {
// extra contains extra etype-specific fields.
// As an optimization, those etype-specific structs which contain exactly
// one pointer-shaped field are stored as values rather than pointers when possible.
//
// TMAP: *Map
// TFORW: *Forward
// TFUNC: *Func
// TSTRUCT: *Struct
// TINTER: *Interface
// TFUNCARGS: FuncArgs
// TCHANARGS: ChanArgs
// TCHAN: *Chan
// TPTR: Ptr
// TARRAY: *Array
// TSLICE: Slice
// TSSA: string
extra interface{}
……
}

从代码中可知,返回的*Type类型的结构体中 extra 字段是一个只包含切片内元素类型的结构(针对包含特定类型字段的结构体进行优化存储。如果这些结构体中包含恰好一个指针类型的字段,那么在可能的情况下会将其存储为值而不是指针)。所以在编译期时切片内元素的类型就确定下来了,在运行中往切片中塞入其他类型的数据就引发异常。

运行时(runtime)

创建一个新的切片

slice在运行时,会通过runtime.makeslice在内存上开辟一块连续的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)
}

如代码所示,通过math.MulUintptr函数计算出占用空间的大小,以及是否内存溢出。
他内部的计算公式为 et.size * cap。翻译一下就是开辟的内存大小 = slice内部元素的大小 * 容量作为起始的内存。

从代码里我们可以得知三个信息:

  1. 当数据长度超过slice容量时 或者长度小于0 会抛异常
  2. 当内存开辟超过最大可分配的内容时会抛异常
  3. 当内存溢出时会抛异常

所以在交叉编译时可能会引入一些跨平台/机器的问题。举个例子,假设以上三点在编译期就固定了。在32G内存的机器上编译了代码,输出了可执行文件。文件被复制到8G内存的机器上运行,当占用内存不断增长,超过8g将会出现内存溢出的问题。

在完成前置判断后程序开始开辟内存。开辟内存的方式逻辑如下,先初始化一个P,如果对象需要开辟的空间小于32768(32K),则直接在初始化在P上。而超过32K的,就在堆上开辟空间。(go里面内存开辟几乎都使用这个逻辑)

感兴趣可以查看 https://github.com/golang/go/blob/master/src/runtime/malloc.go#L909

另外,与makeslice类似的函数makeslice64,会在开辟较大空间的时候使用(较大空间是指超出了int范围)。需要注意的是makeslice64虽然在函数名上标记了int64的长度,实际上make([]int64,math.MaxInt64,math.MaxInt64)是会抛 panic: runtime error: makeslice: len out of range异常的。实际容量需要根据系统架构和元素大小情况计算。

切片扩容

slice是一个可变长度的序列的,支持append方法往里面新增数据。当数据量达到了当前切片最大容量时,就不得不进行扩容。

在进行数据新增并且新增后超出容量时就会调用函数runtime.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

// 小于1.22版本
func growslice(et *_type, old slice, cap int) slice {
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.cap < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
}

扩容逻辑如下:

  1. 当目标容量大于当前容量的2倍,则使用目标容量
  2. 当前容量小于1024,则进行双倍扩容(注意1.18后时256)
  3. 当当前容量大于1024(既>=2048),则新容量是当前容量的1.25倍(注意1.18后时256,>=512)
  4. 当新容量溢出了,则不进行扩容

确认了最新容量后,则进行内存对齐。通过对元素的大小(et.size)的判断,对了内存对齐。通过数组class_to_size拿到对齐的值。

然后通过对齐后的值进行内存开辟,复制原内存内的数据到新开辟的内存上,再内存地址放到新的Slice结构体上返回。

review代码看到1.18版本后将1024调整为256。在1.22版本抽象了计算新容量的方法 nextslicecap

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
// 1.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 {
// Transition from growing 2x for small slices
// to growing 1.25x for large slices. This formula
// gives a smooth-ish transition between the two.
newcap += (newcap + 3*threshold) >> 2

// We need to check `newcap >= newLen` and whether `newcap` overflowed.
// newLen is guaranteed to be larger than zero, hence
// when newcap overflows then `uint(newcap) > uint(newLen)`.
// This allows to check for both with the same comparison.
if uint(newcap) >= uint(newLen) {
break
}
}

// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
return newLen
}
return newcap
}

在1.22版本后切片的扩容机制变更为

  1. 初始化变量:函数接受两个参数,newLen 表示切片的新长度,oldCap 表示切片的旧容量。开始时将 newcap 初始化为 oldCap。

  2. 判断是否需要直接扩容至新长度:首先计算 doublecap,即旧容量的两倍。如果新长度大于 doublecap,则直接返回新长度,因为此时直接扩容到新长度即可。

  3. 阈值判断:定义了一个阈值常量 threshold,其值为 256。如果旧容量小于该阈值,那么新容量直接设置为 doublecap。

  4. 循环计算新容量:对于大于等于阈值的旧容量,采用一种新的扩容策略,即每次增加 newcap 的 1.25 倍,直到 newcap 大于等于 newLen。

  5. 溢出检查:通过将 newcap 强制转换为 uint 类型进行溢出检查。如果 newcap 溢出,则直接返回新长度。

  6. 返回新容量:最后返回新容量,如果新容量小于等于 0,则返回新长度,以防溢出。

这个机制在处理切片扩容时,尤其是针对大容量的切片,可以更加有效地管理内存,避免频繁的内存分配和拷贝操作,从而提高性能。

切片拷贝

切片拷贝在切片的几个方法中算使用频率较低的一个方式。func copy(dst, src []Type) int

在数据发生复制时,通过调用slicecopy就可以实现数据复制。而slicecopy方法的实现,也比初始化和扩容简单很多。如果原数据大小只有1,则直接进行了指针赋值。其他情况则时调用了memmove执行了内存数据复制。

1
2
3
4
5
6
if size == 1 { // common case worth about 2x to do here
// TODO: is this still worth it with new memmove impl?
*(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
} else {
memmove(toPtr, fromPtr, size)
}

相比于循环遍历切片,再往新的切片上复制,memmove性能上占据了更大的优势。但是在较大容量的切片复制上,通过此方法会开辟出大量的内存空间。在使用的时候需要注意对内存性能的影响。

总结

slice因为是动态序列,不管是初始化切片,新增切片,扩容切片,复制切片都是依赖于运行时(runtime)。在运行时发生的行为,需要注意切片在扩容和拷贝过程中发生内存大规模的开辟,避免对程序的性能造成太大的影响。


edit this page last updated at 2024-02-27

Big Image