Go slice扩容深度分析
本文主要是对go slice的扩容机制进行了一些分析。环境，64位centos的docker镜像+go1.12.1。
常规操作
扩容会发生在slice append的时候，当slice的cap不足以容纳新元素，就会进行growSlice
比如对于下方的代码
slice1 := make([]int,1,)
fmt.Println("cap of slice1",cap(slice1))
slice1 = append(slice1,1)
fmt.Println("cap of slice1",cap(slice1))
slice1 = append(slice1,2)
fmt.Println("cap of slice1",cap(slice1))
fmt.Println()
slice1024 := make([]int,1024)
fmt.Println("cap of slice1024",cap(slice1024))
slice1024 = append(slice1024,1)
fmt.Println("cap of slice1024",cap(slice1024))
slice1024 = append(slice1024,2)
fmt.Println("cap of slice1024",cap(slice1024))
复制代码
输出
cap of slice1 1
cap of slice1 2
cap of slice1 4
cap of slice1024 1024
cap of slice1024 1280
cap of slice1024 1280
复制代码
网上很多博客也有提到，slice扩容，cap不够1024的，直接翻倍；cap超过1024的，新cap变为老cap的1.25倍。
这个说法的相关部分源码如下, 具体的代码在$GOROOT/src/runtime/slice.go
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 {
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
}
}
}
// 省略一些后续...
}
复制代码
眼尖的朋友可能看到了问题，上文说的扩容机制其实对应的是源码中的一个分支，换句话说，其实扩容机制不一定是这样的，那到底是怎样的呢？带着疑问进入下一节
非常规操作
上面的操作是每次append一个元素，考虑另一种情形，一次性append很多元素，会发生什么呢？比如下面的代码，容量各自是多少呢？
package main
import "fmt"
func main() {
a := []byte{1, 0}
a = append(a, 1, 1, 1)
fmt.Println("cap of a is ",cap(a))
b := []int{23, 51}
b = append(b, 4, 5, 6)
fmt.Println("cap of b is ",cap(b))
c := []int32{1, 23}
c = append(c, 2, 5, 6)
fmt.Println("cap of c is ",cap(c))
type D struct{
age byte
name string
}
d := []D{
{1,"123"},
{2,"234"},
}
d = append(d,D{4,"456"},D{5,"567"},D{6,"678"})
fmt.Println("cap of d is ",cap(d))
}
复制代码
应该是4个8？基于翻倍的思路，cap从2->4->8。
或者4个5？给4个5的猜测基于以下推测：如果在append多个元素的时候，一次扩容不足以满足元素的放置，如果我是设计者，我会先预估好需要多少容量才可以放置元素，然后再进行一次扩容，好处就是，不需要频繁申请新的底层数组，以及不需要频繁的数据copy。
但是结果有点出人意料。
cap of a is 8
cap of b is 6
cap of c is 8
cap of d is 5
复制代码
是否感觉一头雾水？"不，我知道是这样。" 独秀同志，你可以关闭这篇文章了。
为什么会出现这么奇怪的现象呢？上正文
gdb分析
光看源码已经没太大的进展了,只能借助一些辅助工具来看下运行情况，从而更好地分析下源码，恰好，GDB就是适合这样做的工具。
依旧是上面的代码，我们编译下，然后load进gdb
[root@a385d77a9056 jack]# go build -o jack
[root@a385d77a9056 jack]# ls
jack main.go
[root@a385d77a9056 jack]# gdb jack
GNU gdb (GDB) Red Hat Enterprise Linux 7.6.1-114.el7
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/goblog/src/jack/jack...done.
Loading Go Runtime support.
(gdb)
复制代码
在发生append那一行代码打上断点，然后开始运行程序，为了比较好的说明情况，断点打到扩容后容量为6的[]int型切片b的append上
gdb) l 10
5 )
6
7 func main() {
8
9 a := []byte{1, 0}
10 a = append(a, 1, 1, 1)
11 fmt.Println("cap of a is ", cap(a))
12
13 b := []int{23, 51}
14 b = append(b, 4, 5, 6)
(gdb) b 14
Breakpoint 2 at 0x4872d5: file /home/goblog/src/jack/main.go, line 14.
(gdb) r
Starting program: /home/goblog/src/jack/jack
cap of a is 8
Breakpoint 2, main.main () at /home/goblog/src/jack/main.go:14
14 b = append(b, 4, 5, 6)
复制代码
跳进去断点，看下执行情况
(gdb) s
runtime.growslice (et=0x497dc0, old=..., cap=5, ~r3=...) at /usr/local/src/go/src/runtime/slice.go:76
76 func growslice(et *_type, old slice, cap int) slice {
(gdb) p *et
$1 = {size = 8, ptrdata = 0, hash = 4149441018, tflag = 7 '\a', align = 8 '\b', fieldalign = 8 '\b', kind = 130 '\202', alg = 0x555df0 <runtime.algarray+80>,
gcdata = 0x4ce4f8 "\001\002\003\004\005\006\a\b\t\n\v\f\r\016\017\020\022\024\025\026\027\030\031\033\036\037\"%&,2568<BQUX\216\231\330\335\345\377", str = 987, ptrToThis = 45312}
(gdb) p old
$2 = {array = 0xc000074ec8, len = 2, cap = 2}
复制代码
比较复杂，一开始的时候唯一能看懂就是
一、传进来的cap是5，也就是上文提及到的思路目前来看是正确的，当append多个元素的时候，先预估好容量再进行扩容。 二、slice是一个struct，而struct是值类型。
直到后面大概了解了流程之后才知道，et是slice中元素的类型的一种元数据信息，就分析slice，et中只需要知道size就足够了，size代表的是，元素在计算机所占的字节大小。笔者用的是64位centos的docker镜像，int也就是int64，也就是大小为8个字节。
继续往下走，这一部分的分析涉及到了另外一部分的代码，先贴上
switch {
case et.size == 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.size == sys.PtrSize:
lenmem = uintptr(old.len) * sys.PtrSize
newlenmem = uintptr(cap) * sys.PtrSize
capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
newcap = int(capmem / sys.PtrSize)
case isPowerOfTwo(et.size):
var shift uintptr
if sys.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
} else {
shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
}
lenmem = uintptr(old.len) << shift
newlenmem = uintptr(cap) << shift
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
default:
lenmem = uintptr(old.len) * et.size
newlenmem = uintptr(cap) * et.size
capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / et.size)
}
复制代码
贴上gdb分析的情况，省略一些细枝末节，只摘取了部分较重要的流程
(gdb) n
96 doublecap := newcap + newcap // 结合常规操作列出的源码分析，newcap初始化为old.cap，即为2，doublecap为4
(gdb) n
97 if cap > doublecap { // cap是传进来的参数，值为5，比翻倍后的doublecap=4要大
(gdb) n
98 newcap = cap // 因而newcap赋值为计算后的容量5，而len<1024的分支则没走进去
(gdb) n
123 case et.size == 1:
(gdb) disp newcap // 打印newcap的值
3: newcap = 5
(gdb) n
129 case et.size == sys.PtrSize: // et.size即类型的字节数为8，刚好等于64位系统的指针大小
3: newcap = 5
(gdb) n
132 capmem = roundupsize(uintptr(newcap) * sys.PtrSize) // 得到的capmem是该容量所需的内存，核心步骤，下面重点分析，
3: newcap = 5
(gdb) disp capmem // 打印capmem，结合下面可以看到是48
4: capmem = <optimized out>
(gdb) n
134 newcap = int(capmem / sys.PtrSize) // 得到新的容量
4: capmem = 48
3: newcap = 5
(gdb) n
122 switch {
4: capmem = <optimized out>
3: newcap = 5
(gdb) n
169 if overflow || capmem > maxAlloc { // 这是跳出switch代码块之后的代码，不重要，但是我们已经看到想要的结果了，newcap容量刚好是6，也就是上文中得到的cap(b)
4: capmem = 48
3: newcap = 6
复制代码
后面的代码就是用capmem进行内存分配，然后将newcap作为新的slice的cap，我们来分析这一步capmem = roundupsize(uintptr(newcap) * sys.PtrSize)。
round-up，向上取整，roundupsize，向上取一个size。(uintptr(newcap) * sys.PtrSize)的乘积应该为58=40，经过向上取整之后得到了新的所需内存capmem=48，接着所需内存/类型大小int(capmem / sys.PtrSize)，得到了新的容量，也就是6.*
要明白roundupsize为什么会将40变为48，这里需要简单的引进go的内存管理。可以跟踪进roundupsize方法，然后再跟踪进sizeclasses.go文件，在这个文件的开头，给出了golang对象大小表，大体如下
// 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%
// ...
// 65 28672 57344 2 0 4.91%
// 66 32768 32768 1 0 12.50%
复制代码
其他的暂时不关心，我们先看bytes/obj的这一列，这一列就是go中预定义的对象大小，最小是8b，最大是32K，还有一类就是超出32K的，共67类（超出32K没列在这个文件的，66+1=67）。可以看到，并没有size为40的类型，于是40向上取整，取到了48，这就是发生在roundupsize的真相。这里有一个比较专业的名词，内存对齐。具体为什么需要这样设计？有兴趣的读者，可以细看golang的内存管理，这里篇幅有限，就不展开了。
非常规操作中还有其他类型的append，这里就不贴gdb的分析了，一样都有roundupsize的操作，大同小异，有兴趣的朋友可以自行玩一下。
疑问
在append时，roundupsize并不是一个特殊分支才有的操作，我感觉不可能一直都是双倍扩容和1.25倍扩容啊，怀疑网上挺多博客说的有问题。
于是又测试了下
e := []int32{1,2,3}
fmt.Println("cap of e before:",cap(e))
e = append(e,4)
fmt.Println("cap of e after:",cap(e))
f := []int{1,2,3}
fmt.Println("cap of f before:",cap(f))
f = append(f,4)
fmt.Println("cap of f after:",cap(f))
cap of e before: 3
cap of e after: 8
cap of f before: 3
cap of f after: 6
复制代码
哎，果不其然。扩容后的slice容量，还和类型有关呢。
summary
内容跳的有点乱，总结一下
append的时候发生扩容的动作
append单个元素，或者append少量的多个元素，这里的少量指double之后的容量能容纳，这样就会走以下扩容流程，不足1024，双倍扩容，超过1024的，1.25倍扩容。
若是append多个元素，且double后的容量不能容纳，直接使用预估的容量。
敲重点！！！！此外，以上两个分支得到新容量后，均需要根据slice的类型size，算出新的容量所需的内存情况capmem，然后再进行capmem向上取整，得到新的所需内存，除上类型size，得到真正的最终容量,作为新的slice的容量。
以上，全剧终，欢迎讨论~
有疑问加站长微信联系（非本文作者）
