2.1 slice 扩容后容量及内存如何计算?¶
1. 扩容后预估容量¶
假设现在有一个长度为 2 的切片,对其进行扩容,增加三个元素
sli := []int{1,2}
sli = append(sli, 3, 4, 5)
对于扩容后的切片,长度为 5,这一点没有任何争议。
但容量呢?难道也是 5?
经过运行验证,实际的容量为 6 。
什么情况?这 6 是如何计算出来的呢?
这就不得不去 Go 源代码中一探究竟,在 runtime/slice.go
关于 slice
扩容增长的代码如下:
newcap := old.cap
if newcap+newcap < cap {
newcap = cap
} else {
for {
if old.len < 1024 {
newcap += newcap
} else {
newcap += newcap / 4
}
if newcap >= cap {
break
}
}
}
对于这段代码,只要理解前两行,其他的就不攻自破了
第一行的 old.cap:扩容前的容量,对于此例,就是 2
第二行的 cap:扩容前容量加上扩容的元素数量,对于此例,就是 2+3
整段代码的核心就是要计算出扩容后的预估容量,也就是 newcap,计算的具体逻辑是:
若 old.cap * 2 小于 cap,那 newcap 就取大的 cap
若 old.cap * 2 大于 cap,并且old.cap 小于 1024,那 newcap 还是取大,也即 newcap = old.cap * 2
若 old.cap * 2 大于 cap,但是old.cap 大于 1024,那两倍冗余可能就有点大了,系数换成 1.25,也即 newcap = old.cap * 1.25
但 newcap 只是预估容量,并不是最终的容量,要计算最终的容量,还需要参考另一个维度,也就是内存分配。
2. 内存的分配规律¶
举个现实中的例子来说
你家里有五个人,每个人都想吃绿豆糕,因此你的需求就是 5,对应上例中的 cap ,于是你就到超市里去买。
但超市并不是你家开的,绿豆糕都是整盒整盒的卖,没有卖散的,每盒的数量是 6 个,因此你最少买 6 个。
每次购买的最少数量,就可以类比做 Go 的内存分配规律。
只有了解了 Go 的内存分配规律,我们才能准确的计算出我们最少得买多少的绿豆糕(得申请多少的内存,分配多少的容量)。
关于内存管理模块的代码,在 runtime/sizeclasses.go
// 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%
...
// 17 256 8192 32 0 5.86%
// 18 288 8192 28 128 12.16%
// 19 320 8192 25 192 11.80%
// 20 352 8192 23 96 9.88%
// 21 384 8192 21 128 9.51%
// 22 416 8192 19 288 10.71%
// 23 448 8192 18 128 8.37%
// 24 480 8192 17 32 6.82%
// 25 512 8192 16 0 6.05%
...
// 66 32768 32768 1 0 12.50%
从上面这个表格中,可以总结出一些规律。
在小于16字节时,每次以8个字节增加
当大于16小于2^8时,每次以16字节增加
当大于28小于29时以32字节增加
依此规律…
3. 匹配到合适的内存¶
第一节中我们例子中,主人公是一个元素类型为 int 的切片,每个 int 占用为 8 个字节,由于我们计算出的 newcap 为 5,因此新的切片,最少最少要占用 5*8 = 40 个字节。
再到第二节中的表格中查看,发现离 40 byte 最接近的是 32 和 48 两个档位。
如果是 32 byte,就是不够用了,
因此 只能选择 48 这个档位去分配内存。
有了实际分配的内存,再反回去计算容量,就是扩容后真实的切片容量,也就是
48/8 = 6