Golang Slice 的 append 扩容

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

首先之前关于 slice 的 append 理解:

每次 append 操作都会检查 slice 是否有足够的容量,如果足够会直接在原始数组上追加元素并返回一个新的 slice,底层数组不变
而若容量不够,会创建一个新的容量足够的底层数组,先将之前数组的元素复制过来,再将新元素追加到后面,然后返回新的 slice,底层数组改变
而这里对新数组的容量定义是按 乘以2 的机制增加

而今天看到关于 Golang 切片的底层结构即 reflect.SliceHeader 时,发现 append 的扩容并不完全是2倍增长,源码如下(Go version 1.13):

// grow grows the slice s so that it can hold extra more values, allocating
// more capacity if needed. It also returns the old and new slice lengths.
func grow(s Value, extra int) (Value, int, int) {
    i0 := s.Len()
    i1 := i0 + extra
    if i1 < i0 {
        panic("reflect.Append: slice overflow")
    }
    m := s.Cap()
    if i1 <= m {
        return s.Slice(0, i1), i0, i1
    }
    if m == 0 {
        m = extra
    } else {
        for m < i1 {
            if i0 < 1024 {
                m += m
            } else {
                m += m / 4
            }
        }
    }
    t := MakeSlice(s.Type(), i1, m)
    Copy(t, s)
    return t, i0, i1
}

// Append appends the values x to a slice s and returns the resulting slice.
// As in Go, each x's value must be assignable to the slice's element type.
func Append(s Value, x ...Value) Value {
    s.mustBe(Slice)
    s, i0, i1 := grow(s, len(x))
    for i, j := i0, 0; i < i1; i, j = i+1, j+1 {
        s.Index(i).Set(x[j])
    }
    return s
}

首先 Append 判断类型是否 slice,然后调用 grow 扩容,从 l1 <= m 的判断可以发现确实容量足够的情况下,只是对原始数组建立一个新的 slice

但当容量不足时,可以看到只有在当前元素 i0 小于1024时,才是按2倍速度正常,否则其实每次只增长25%,代码验证如下:

func main() {
    str := make([]int, 1023)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
}

输出:
1023 1023
1024 2048
1025 2048

初始容量已经达到1024后,只增长了256

func main() {
    str := make([]int, 1024)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
    str = append(str, 1)
    fmt.Println(len(str), cap(str))
}
输出:
1024 1024
1025 1280
1026 1280

当然这里还有个疑惑在于,初始容量为1023时,并不是按1023×2,而是直接1024×2,测试初始500扩容也是直接按512×2,猜测更底层在动态调整时总会补充为2的n次方,目前builtin包下只看到 append 的定义说明,还有待继续挖掘


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:邹友

查看原文:Golang Slice 的 append 扩容

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

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