切片 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,会采用两种不同的增长策略。

引申一个想法

如果初始化切片设置的cap比较小,实际要存储的元素个数也比较小,我们如何评估影响呢?这让我联想到了时间复杂度,时间复杂度评估的就是耗时和数据量N的关系,关注的是一种变化,而非某个具体的N是多少。

所以,创建切片的时候,合理地预估容量非常重要。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 下的源代码:

对比一下上面我自己想的伪代码,有一些考虑不完善的地方。

  1. 缺少了 eCap 和2倍 oCap 容量的比较逻辑
  2. oCap值可能是负值,这回导致伪代码的 for 循环变成死循环
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 中的一个下标,将下标前的部分和下标后的部分颠倒?