蛮荆

Go 切片扩容底层实现

2023-03-10

概述

切片 在使用过程中,值得注意的地方就是扩容导致的性能问题,实际开发中,我们一般会通过 容量预分配 来规避这个问题。

本文主要研究下 切片扩容 的内部实现。

内部实现

接下来,我们来探究一下 切片 的内部实现,文件路径为 $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

扩展阅读

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可,转载时请注明原文链接,图片在使用时请保留全部内容,商业转载请联系作者获得授权。