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 )
7 func main() {
9 a := []byte{1, 0}
10 a = append(a, 1, 1, 1)
11 fmt.Println("cap of a is ", cap(a))
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 的容量。
备注