Golang

Go Slice自动扩容机制

Posted by Qiuyu Zhang on 2023-08-15

以下内容仅个人理解整理，仅供参考

在go1.18版本之后(含1.18)go slice append相比之前版本growslice函数已经发生变化,
在Go 1.18 Release Notes中提到
The built-in function append now uses a slightly different formula when deciding how much to grow a slice when it must allocate a new underlying array. The new formula is less prone to sudden transitions in allocation behavior.

以下是1.18中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
25
26
27
28
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 {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
				// 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) / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
	//...
}

以下是1.17版本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
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
			}
		}
	}
  //...
}

可以看出在 Go 1.18 中，扩容策略 (不考虑内存对齐的情况下) 变成了：
如果期望容量大于当前容量的两倍就会使用期望容量
如果当前切片的长度小于 256 就会将容量翻倍
如果当前切片的长度大于 256 就会每次增加 25% 的同时再增加 192(256 的 3/4)，直到新容量大于期望容量
按照注释的说法是新的公式 newcap += (newcap + 3*threshold) / 4 会使得容量的变化更加平滑。
我们可以看到1.17版本采用的公式是而且临界值是1024 newcap += newcap / 4

FEATURED TAGS
Golang