
golang 切片 append 扩容性能分析
很多时候,我们对这个功能点不够重视,经常也会写一些没有声明 cap 容量的变量声明,然后直接调用 append,逻辑上是没有问题的,但是当 append 的数量足够多的时候,性能问题就突出来了。
切片 append 是比较常规的操作,但存在一个隐患,当初始cap设置的比较小,而实际要存储的元素非常多时,性能损耗就会比较突出。比如下面这个例子,当 for 循环的次数足够多时,就会触发到性能瓶颈
func main() {
elems := make([]string, 0)
for i := 0; i < 1000; i++ {
elems = append(elems, strings.Repeat("跑马灯 ", 100))
}
}
基于这个例子,我们用单测来验证一下,在单测中保存 cpu profile 数据到文件 cpu.p中,在开始执行测试之前,使用 ResetTimer重置时间,取消创建文件的性能开销
下面是分析的结果,我们把焦点集中在 growslice上,这个单测有点缺陷,就是每次 for 循环都会调用一次 string.Repeat 函数,导致 Repeat 函数的 cpu 消耗反客为主了。但不重要,能说明问题。
但很多时候,我们对这个功能点不够重视,业务中经常也会写一些没有声明 cap 容量的变量声明,然后直接调用 append,逻辑上是没有问题的,只有当 append 的数量足够多的时候,性能问题才会突出来了。
live := make([]BigObject, 0) // 缺少声明cap
live = append(live, BigObject{})
在初始化切片时设置了cap为2,但实际上元素有600个,这时切片容量的增长就称为了一个性能的损耗点。这种情况,底层会按照2倍的扩容方式,2、4、8、16…,总共会扩容9次,每次扩容过程,旧数据内存都会拷贝到新数据的空间。
这种2倍的增长模式,也不是固定的,具体的增长算法,依赖我们预期(这里我叫 eCap,expect capacity)的值,当达到阈值1024,会采用两种不同的增长策略。
实际扩容的次数
基于对扩容的策略分析,在实际的操作上,系统究竟进行了多少次内存分配呢?我们先来看 go1.15 的扩容方式,假设这样的场景,创建一个长度和容量都为0的元素,通过 append 的方式来向切片中添加元素,添加 100 次,在这个过程中切片做了多少次扩容呢?
func appendSelf() {
s := make([]int, 0)
for i := 0; i < 100; i++ {
s = append(s, i)
}
}
源码给的参考
从源码的角度来分析,我们可以预估一个值,但需要一个求证的过程,验证预估值和实际值是不是相同。我有时候会觉得,阅读源码是最笨的方式,忽略过程看结果是最直接的方式。学习阶段,还是需要搞清楚现象背后的原理,处理问题阶段,就是要快速的解决问题。
这算得上 go1.15.7/src/runtime/slice.go:144
真正扩容的逻辑了,看样子里,可以很容易解决我们上面提出的问题,如果当前切片的容量小于 1024的话,会按照 2 倍的容量进行扩容。但是呢,我们通过 make 创建切片时,指定的长度和容量都是 0 ,套用到下面的代码,old.cap
是 0,2倍扩容之后还是 0,这就有些尴尬了。
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 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
}
}
}
初始化长度为0的切片
再小心求证一下,我们还是通过下面的 demo 就可以知道扩容的结果,因为输出结果是 1,所以初始扩容是 1。紧随代码之后的截图是汇编的源码,目前我还不能准确的解释这些指令的奥义…但这个过程调用了 growslice 是铁板钉钉的事实。
func main() {
s := make([]int, 0)
s = append(s, 0)
fmt.Println(len(s))
}
解这道题
回到前面,从一个长度为0的切片,append 到长度为100,第一次 growslice 是 0 -> 1,后面就简单了,一次是 2、4、8、16、32、64、128
总共需要扩容 8 次,另外,我们是不是也可以利用 benchmark 来验证扩容的次数呢?
因为带有 -benchmem
属性的单测结果,会输出程序单次执行的内存分配、内存申请次数。通过 benchmark
数据的结果,和我们通过源码预测的结果,会是一致的结果吗?我也很好奇另一个事情,benchmem
统计的内存分配次数有没有做一些细致的区分,比方说,只统计了在内存栈或者堆上分配的结果,还是两者都统计了?
func BenchmarkName(b *testing.B) {
for i := 0; i < b.N; i++ {
appendSelf()
}
}
单测的结果显示,每次 appendSelf
操作都做了 8 次内存分配,和我们预测的结果是一致的。如果有同志还是不放心,可以多执行几次。毕竟,我们不可能穷举所有的情况,更重要的是,我们无法确保我们就穷举了所有的情况
benchmem
统计的内存分配是在堆还是栈上进行的
这要去思考“逃逸分析”的情况,这里不想在继续漫无目的的东扯西扯了,会在内存分配的文章中在来瞎说会。有时候,有一些我也无法保证内容正确的博客,设置成仅粉丝可以查看会比较稳妥…
用下面的 benchmark 例子,执行之后,单次操作的内存申请次数是多少呢?如果将 128 扩大到 12800,内存申请次数是多少呢?前者是 0, 后者是 1。这也回应了前文堆栈内存分配的争论。
func BenchmarkName(b *testing.B) {
for i := 0; i < b.N; i++ {
// appendSelf()
_ = make([]int, 0, 128)
}
}
性能问题
如果初始化切片设置的cap比较小,实际要存储的元素个数也比较小,我们如何评估影响呢?最好的情况当然是准确地评估切片的容量,在初始化的时候直接一次性申请完成。但现实世界就是很复杂,我们需要根据接收到的数据动态来申请切片的大小。那我们将扩容次数限制在多少内就可以忽略对性能的影响呢?
如果是单测的算法,往往只需要评估两个关键指标:时间复杂度和空间复杂度。而且,在比较算法性能时,也只需要考虑数据量近乎无穷大的情况,计算机是为计算大量数据的而设计的,数据量太小不符合设计初衷,也没有意义。算法评估的结果大部分也只包含两类,一类是不随数据量变化的因素,一类是随数据量变化的因素。
但 append 这个性能就让人有些迷,显然,贴近现实世界中的业务几乎不怎么处理大数,如果正常业务的每个请求,业务逻辑中都有做 10000 次 append 的操作(这里只是说 10000 次有些大了),那性能也不需要评估,拍着脑袋就知道性能上不去。
但是吧,append 性能还不能局限在 growslice 进行了多少次扩容,为什么呢?因为长度为10和长度为200的 growslice
扩容代价可能是不一样的。至少现在,我没有想到一个合理的评估方式。如果那次想到了,会及时更新过来。
所以,创建切片的时候,合理地预估容量非常重要。slice底层的切片扩容机制这里简单说明一下:
扩容的参考依据有两个,当前切片的容量,这里称为 oCap(old capacity)。满足当前切片需求的最小容量,这里称为 eCap。当 oCap 小于 1024时,按照 2 倍 oCap进行扩容,当容量大于 1024时,按照 1/4 oCap的容量增长,这里的 1/4 是具有叠加效应的。我们来实现一下伪代码,假设新的切片容量为 nCap:
if oCap < 1024 {
nCap = 2 * oCap
} else {
nCap = oCap
for oCap < eCap {
nCap = 1/4 * nCap + nCap
}
}
新版本的扩容
对比的看一下 go1.18 下的源代码,从go1.15
到这里的go1.18
跨度确实有些大了,写切片这种主题的文章本就是老调重弹,没啥新意。如果能从新版本中看到一些不同寻常的优化,也能算是捡到了宝贝。以前那种拍脑袋的扩容策略,完全就是一种落后的技术水平。
有些失望,只是在阈值上做了一些调整,go1.15
在 1024 容量前都是以2倍当前容量扩容的,go1.18
将阈值降低到了 256。go1.15
在 1024 容量之后会按照当前容的 1/4 倍进行扩容,go1.18
在256 之后,会按照当前容量的 1/4倍外加 3/4
倍的 threshold 常量进行扩容。
go1.18
扩容比较含蓄了,TODO 扩容策略补充
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
}
}
}
思考题
切片的扩容逻辑比较简单,也没有什么高深的地方。留一个思考题,指定 slice 中的一个下标,将下标前的部分和下标后的部分颠倒?尽量使用切片的 copy 函数完成。
更多推荐
所有评论(0)