• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Go slice 扩容机制分析

开发技术 开发技术 4小时前 3次浏览

Go slice 扩容机制分析

前言

我们都知道 Go 语言中的 slice 具有动态扩容的机制(不知道的同学请先补课 Go 切片)

但是其底层机制是什么呢?本着知其然,知其所以然的探索精神去研究一番。还不是为了应试 手动狗头

go version go1.15.6 windows/amd64

扩容

既然是八股文,哪就先说结论,切片的扩容分两步:预估扩容后的容量,确定内存占用后得到最终的容量

下文给出了一个例子,读者可以先猜测一下结果,带着问题寻找答案。不然上来就看源码分析,还不得晕

s := []int32{1, 2}
s = append(s, 3, 4, 5)
fmt.Printf("len=%d, cap=%d", len(s), cap(s))

预估容量

删除一些边界检查,溢出检查,基于 cap 的预估算法非常简单

// src/runtime/slice.go
/* 
参数分析:
	old 是老切片
	cap 是新切片容量的最小值(即旧切片的容量加上新加入元素的数量),上面的例子中,cap 值为 5(2+3=5)
*/
func growslice(et *_type, old slice, cap int) slice {
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap { // 如果最小值大于旧切片容量的两倍,则新容量为最小值
		newcap = cap
	} else {
		if old.len < 1024 { // 如果旧切片长度小于 1024,则新容量为旧切片容量的 2 倍
			newcap = doublecap
		} else {
			for newcap < cap {
				newcap += newcap / 4 // 每次增长 25%,直到大于最小值
			}
		}
	}
}

按照这种算法,得出上个例子新切片的容量为 5(3+2 大于 2*2)

内存占用

内存占用 = 元素个数 * 元素类型大小。

不过,由于 Go 语言的内存分配是由其 runtime 来管理的,程序并不是直接和操作系统打交道。

在程序启动时,runtime 会提前向操作系统申请一批内存,按照不同的规格管理起来,如下所示(重点看 bytes/obj 这列):

// src/runtime/sizeclasses.go
// Code generated by mksizeclasses.go; DO NOT EDIT.
//go:generate go run mksizeclasses.go

package runtime

// class  bytes/obj  bytes/span  objects  tail waste  max waste
//     1          8        8192     1024           0     87.50%
//     2         16        8192      512           0     43.75%
//     3         32        8192      256           0     46.88%
//     4         48        8192      170          32     31.52%
//     5         64        8192      128           0     23.44%
//     6         80        8192      102          32     19.07%
//     7         96        8192       85          32     15.95%
//     8        112        8192       73          16     13.56%
//     9        128        8192       64           0     11.72%
//    10        144        8192       56         128     11.82%
//    11        160        8192       51          32      9.73%

//  ......

当程序向 runtime 申请内存时,它会匹配足够大,且最接近的规格

上例中,int32 占用 4 byte,总内存占用为 5 * 4=20 byte,则 runtime 实际分配的内存为 32 byte,最终的容量为 32 / 4(每个 int 32 占用大小) = 8

练习

s := []int64{1, 2}
s = append(s, 3, 4, 5)
fmt.Printf("len=%d, cap=%d", len(s), cap(s))
  1. 2(老容量)+ 3(新添加的元素)= 5,超出 4 (老容量的两倍),即预估容量为 5

  2. int64 占用 8 byte,总内存 5 * 8 = 40 byte,runtime 实际分配 48 byte,48 / 8 = 6

参考

slice类型存什么?make和new?slice和数组?扩容规则?

终于理解了Slice扩容机制


程序员灯塔
转载请注明原文链接:Go slice 扩容机制分析
喜欢 (0)