这篇文章我们结合go的源码探究下slice的扩容机制。
golang中slice的扩容算法在1.18中修改过一次，我们可以从go1.18的release notes中看到。https://go.dev/doc/go1.18
“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.”
文中提到了一个说法叫做”sudden transitions“，说新的算法比老的算法在sudden transitions上做的更好（less prone）。
什么是sudden transitions呢？
我们可以先看看go1.18之前slice的扩容算法是什么样子的。直接看源码（go1.17）。
https://github.com/golang/go/blob/release-branch.go1.17/src/runtime/slice.go#L181
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
}
}
}我们看到其实golang的slice扩容的算法很简单（不考虑roundup）。
1. 如果需要的容量大于2倍的当前容量，则直接分配成新的容量，不会进行额外的容量分配。
2. 如果需要的容量小于2倍的当前容量，还要分情况进行讨论：
a. 如果当前容量小于1024，则实际分配的新的容量等于当前容量的2倍
b. 如果当前容量大于1024，则按照1.25的系数对当前容量进行扩增，直到扩增完的容量大于需要的容量，然后这个值作为新的容量大小
我们可以发现一个问题，就是当前容量小于1024的时候是按照2倍的系数进行容量扩增的，而当前容量大于1024的时候是按照1.25倍的系数进行扩增的。这就是我们上面提到的sudden transitions，扩增系数突然发生了较大的改变。
除了sudden transitions，这种扩容策略还有一个问题，就是新的容量相对于旧容量不是单调递增的。
举个例子，如果不考虑roundup，当旧容量是1000的时候，扩容后的新容量是2000，但是当旧容量是1024的时候，扩容后的容量是1024+1024/4 = 1280。旧容量1024大于1000，但是扩容后的容量1280反而比2000要小。
为了解决上面提到的问题，我们看看go1.18中是如何做的？
https://github.com/golang/go/blob/release-branch.go1.18/src/runtime/slice.go#L188
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
}
}
}可以看到go1.18中的扩容策略如下：
1. 如果需要的容量大于2倍的当前容量，则直接分配成新的容量，不会进行额外的容量分配。
2. 如果需要的容量小于2倍的当前容量，还要分情况进行讨论：
a. 如果当前容量小于256，则实际分配的新的容量等于当前容量的2倍
b. 如果当前容量大于256，则按照公式newcap += (newcap + 3*threshold) / 4进行扩增，直到newcap满足需要的容量
按照这种方式进行容量扩增的话，扩增的系数不是一个定值，而是会和旧的容量的大小有关系，介于2和1.25之间。如果旧的容量等于256，扩增系数就是2，如果旧的容量很大，扩增系数会无限趋近于1.25。
下面是旧容量大小和扩增系数之间的一些关系：
starting cap growth factor
256 2.0
512 1.63
1024 1.44
2048 1.35
4096 1.30更多详细内容可见：
https://github.com/golang/go/commit/2dda92ff6f9f07eeb110ecbf0fc2d7a0ddd27f9d