golang slice 增长公式

当切片容量不足时，会调用Go标准库 runtime.growslice 函数为切片扩容
这里只关注增长公式

第一步 确定容量

go 1.18 之前

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 检测溢出并防止无限循环
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

  ......
}

在这里可以得出
若申请的容量为原来容量的两倍以上, 则直接确定新容量为申请的容量, 否则
在容量小于1024之前增长因子为2, 即容量翻倍
容量大于1024之后增长因子为1.25, 即容量增加25%, 直到大于申请的容量

go 1.18之后

func growslice(et *_type, old slice, cap int) slice {
  ......

  newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		const threshold = 256
		if old.cap < threshold {
			newcap = doublecap
		} else {
			for 0 < newcap && newcap < cap {
				newcap += (newcap + 3*threshold) / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

  ......
}

阈值变小了, 为了让小切片到大切片的增长因子有平滑的过度进行了改进(commit)
在容量小于256之前增长因子为2, 即容量翻倍, 与之前相同
在容量大于256之后, 公式等于 新容量 = 旧容量 + (旧容量 + 3 * 256) / 4
等于 新容量 = 1.25 * 旧容量 + 192
因此当容量大于256时, 增长因子为1.25, 加上固定容量192
随着容量增长, 增长因子因此逐渐靠近1.25

starting cap    growth factor
256             2.0
512             1.63
1024            1.44
2048            1.35
4096            1.30

第二步 内存对齐

代码紧接上一步

func growslice(et *_type, old slice, cap int) slice {
  ......

	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == goarch.PtrSize:
		lenmem = uintptr(old.len) * goarch.PtrSize
		newlenmem = uintptr(cap) * goarch.PtrSize
		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		newcap = int(capmem / goarch.PtrSize)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if goarch.PtrSize == 8 {
			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}

  ......
}

由于本文主要关注增长相关问题, 所以这里忽略其他
这部分主要使用使用 roundupsize 函数处理内存对齐 最终可能导致newcap变大

示例

func main() {
	// 运行于 go 1.19.2
	s1 := []uint8{1, 2, 3}
	fmt.Printf("s1 len:%d, cap: %d \n", len(s1), cap(s1))
	// 3 + 4 大于两倍, 直接使用 7
	// 内存对齐 8
	s1 = append(s1, 4, 5, 6, 7)
	fmt.Printf("s1 len:%d, cap: %d \n", len(s1), cap(s1))

	s2 := make([]int, 256)
	fmt.Printf("s2 len:%d, cap: %d \n", len(s2), cap(s2))
	//   256 + (256 + 3 * 256) / 4
	// = 512
	s2 = append(s2, 1, 2, 3, 4)
	fmt.Printf("s2 len:%d, cap: %d \n", len(s2), cap(s2))
}

输出

s1 len:3, cap: 3
s1 len:7, cap: 8
s2 len:256, cap: 256
s2 len:260, cap: 512

总结

由此可以看出所有决定容量的步骤

  • 当申请容量大于当前容量两倍则直接使用申请容量
  • 当容量小于容量阈值, 增长因子为2, 即容量翻倍
  • go 1.18 之前, 当容量大于容量阈值, 增长因子为1.25, 即容量增加 25%, 直到满足申请容量
  • go 1.18 和之后, 在容量增加 25% 之外还额外增加固定 192
  • 进行内存对齐

容量阈值go 1.18之前为1024
容量阈值go 1.18和之后为256, 编辑日期2022年11月7日