Go 切片扩容底层实现
概述
切片
在使用过程中,值得注意的地方就是扩容导致的性能问题,实际开发中,我们一般会通过 容量预分配 来规避这个问题。
本文主要研究下 切片扩容
的内部实现。
内部实现
接下来,我们来探究一下 切片
的内部实现,文件路径为 $GOROOT/src/runtime/slice.go
,笔者的 Go 版本为 go1.19 linux/amd64
。
SliceHeader 结构体
切片
的运行时数据结构。
type SliceHeader struct {
Data uintptr // 引用数组的指针 (指向一片连续的内存)
Len int // 切片的长度
Cap int // 切片的容量
}
makeslice
切片
结构的运行时创建函数,编译器会将 切片的初始化操作
(不管是调用 make
函数还是字面量的方式) 转换为 makeslice
调用。
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 {
// 注意: 当调用 make([]T, bignumber) 是,产生 'len out of range', 而非 'cap out of range'
// 'cap out of range' 当然也是正确的,但是 cap 没有 len 提示更清晰
// 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) // 执行具体的内存分配
}
// 返回 a * b 的结果以及结果是否溢出
// 编译器会根据不同的目标平台计算对应的值
func MulUintptr(a, b uintptr) (uintptr, bool) {
if a|b < 1<<(4*goarch.PtrSize) || a == 0 {
return a * b, false
}
overflow := b > MaxUintptr/a
return a * b, overflow
}
growslice
growslice
函数主要用来处理调用 append
函数时引发的切片扩容。
// 它接收元素类型、旧的切片和新的【所需最小容量】,然后返回一个至少拥有【所需最小容量】的新切片,并将旧切片的数据复制到新切片中
// 新切片的 length 会被设置为旧切片的 length,而不是新请求的 capacity
// 这是为了方便编码,旧切片的长度可以立即用于:计算在追加过程中写入新值的索引位置
func growslice(et *_type, old slice, cap int) slice {
...
if cap < old.cap { // 不能缩容
panic(errorString("growslice: cap out of range"))
}
if et.size == 0 {
// append 不应该创建一个带有 nil 指针但是 len 长度非零的切片
// 假设 append 不需要保存 old.array
return slice{unsafe.Pointer(&zerobase), old.len, cap}
}
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
// 如果期望容量大于当前容量 2 倍,使用期望容量
newcap = cap
} else {
const threshold = 256
if old.cap < threshold {
// 如果当前容量小于 256,容量翻倍
newcap = doublecap
} else {
// 如果当前容量大于等于 256:
// 检查 0 < newcap 以检测溢出并防止无限循环
for 0 < newcap && newcap < cap {
// 平滑过度: 从 [小切片的容量翻倍扩容] 到 [大切片的 1.25 倍扩容]
// 也就是说,刚开始时 (容量小) 直接翻倍,慢慢地到后面 (容量越来越大), 最终扩容的倍数因子是 1.25
// 这个公式给出了两者之间的平滑过渡, 一直扩容到满足条件为止
newcap += (newcap + 3*threshold) / 4
}
// 当新的容量计算溢出时,将新容量设置为期望容量
if newcap <= 0 {
newcap = cap
}
}
}
// 上述代码片段仅会确定切片的大致容量,除此之外,还需要根据切片中的元素大小进行内存对齐
// 当切片元素所占字节大小为 1, 2, 8 的倍数时,运行时使用如下代码内存对齐
var overflow bool
var lenmem, newlenmem, capmem uintptr
// 专门用于 et.size 公共值
// 对于 1,不需要任何调整
// 对于 goarch.PtrSize (64 位是 8, 其他的以此类推), 编译器会将乘法/除法优化为一个常数的位移
// 对于 2 的幂,使用可变位移
switch {
case et.size == 1:
...
newcap = int(capmem)
case et.size == goarch.PtrSize:
...
newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.size):
...
newcap = int(capmem >> shift)
default:
...
newcap = int(capmem / et.size)
}
// 除了 capmem > maxAlloc 之外,还需要检查溢出,溢出用于触发 32 位体系结构上的段错误
// 示例程序如下
//
// type T [1<<27 + 1]int64
//
// var d T
// var s []T
//
// func main() {
// s = append(s, d, d, d, d)
// print(len(s), "\n")
// }
if overflow || capmem > maxAlloc {
panic(errorString("growslice: cap out of range"))
}
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// 调用 growslice 的 append() 将会覆盖 old.len 到 cap 之间的数据 (cap 将是新的长度)
// 仅仅清除不会被覆盖的部分
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// 注意: 不能使用 rawmem (可以避免内存转换为零值),因为这样 GC 可以扫描未初始化的内存
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// 只隐藏旧数组中的指针,因为知道目标切片 p 只包含 nil 指针 (因为它已经在分配期间被清除)
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
}
}
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
}
slicecopy
slicecopy
函数用于将无指针元素的切片或字符串复制到切片中。
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
if fromLen == 0 || toLen == 0 { // 源切片或者目标切片有一个长度为 0, 直接返回
return 0
}
n := fromLen // n 等于较短的切片长度
if toLen < n {
n = toLen
}
if width == 0 { // 无需拷贝
return n
}
size := uintptr(n) * width
...
if size == 1 {
// 如果只有 1 个元素,直接转换对应指针
*(*byte)(toPtr) = *(*byte)(fromPtr)
} else {
memmove(toPtr, fromPtr, size)
}
return n
}
小结
切片
使用append
函数进行追加操作时,可能会引发扩容操作,对于潜在的引发多次扩容场景,初始化切片时一定要使用预分配
机制。
切片的扩容计算方式如下:
- 如果期望容量大于当前容量
2
倍,使用期望容量 - 否则
- 如果当前容量小于
256
,容量翻倍 - 如果当前容量大于等于
256
, 平滑扩容过渡,最终扩容的倍数因子是1.25
- 如果当前容量小于