Go slice扩容深度分析（来自掘金文章）

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)
复制代码

[]intb

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 = roundupsize(uintptr(newcap) * sys.PtrSize)

roundupsize(uintptr(newcap) * sys.PtrSize)capmem=48int(capmem / sys.PtrSize)

roundupsizeroundupsizesizeclasses.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%
//     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/objroundupsize

roundupsize

疑问

roundupsize

于是又测试了下

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后的容量不能容纳，直接使用预估的容量。

capmemcapmem

以上，全剧终，欢迎讨论~