Go slice扩容分析之 不是double或1.25那么简单

l_sivan · · 263 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

本文主要是对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的容量。

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

本文来自:简书

感谢作者:l_sivan

查看原文:Go slice扩容分析之 不是double或1.25那么简单

入群交流(和以上内容无关):Go中文网 QQ 交流群:798786647 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

263 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传