Strcpy

Slice的初始化和扩容过程

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

切片和数组数组在go语言中都是非常常见的结构。很多刚开始使用go语言的开发者会混淆这两者的概念。

本篇会从slice的编译期、运行时来分析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方法,这个方法支持传入一个参数elem,指定类型为*Type,并且返回一个*Type类型的结构体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 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 {
Fatalf("elem mismatch")
}
return t
}

t := New(TSLICE)
t.Extra = Slice{Elem: elem}
elem.Cache.slice = t
return t
}

进入Slice{Elem: elem},可以知道在编译期,slice的数据结构如下:

1
2
3
4
// Slice contains Type fields specific to slice types.
type Slice struct {
Elem *Type // element type
}

由此可知,返回的*Type类型的结构体中的 Extra 字段是一个只包含切片内元素类型的结构。所以在编译期时,切片内元素的类型就确定下来了,而不是在运行时数据被添加进去的时候。

运行时(runtime)

创建一个新的切片

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

1
2
3
4
5
6
7
8
9
10
11
12
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 {
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
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,则进行双倍扩容
  3. 当当前容量大于1024(既>=2048),则新容量是当前容量的1.25倍
  4. 当新容量溢出了,则不进行扩容

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

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

切片拷贝

切片拷贝在切片的几个方法中算使用频率教低的一个方式。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 2022-07-22

Big Image