Golang 中 slice cap 增长模式小记

h3l · 2020-01-13 00:43:30

在 Golang 中，我们知道数组是固定长度的。一般我们在使用时，大多数情况下使用的其实都是 slice，但是 slice 的底层的数据其实还是数组。所以我们在向 slice append 数据的时候，Golang 会检查底层的数组的长度是否已经不够，如果长度不够，Golang 则会新建一个数组，把原数组的数据拷贝过去，再将 slice 中的指向数组的指针指向新的数组。

但是，新数组的长度该如何确定呢？如果每次新数组长度只增加 1，那么每次 append 数据都需要新建一个数组。但是如果每次新增数组的长度太大的，又会造成内存的浪费。先写一个简单的代码看看内存如何增长。

package main

import (
    "fmt"
)

func main() {
    slice := make([]int, 0, 0)
    lastCapSize := 0
    for i := 0; i < 100000; i++ {
        slice = append(slice, 1)
        if lastCapSize != cap(slice) {
            if i != 0 {
                fmt.Println(i, cap(slice), float32(cap(slice))/float32(i))
            }
            lastCapSize = cap(slice)
        }
    }
}

结果如下：

last	current	percent
1	2	200.00%
2	4	200.00%
4	8	200.00%
8	16	200.00%
16	32	200.00%
32	64	200.00%
64	128	200.00%
128	256	200.00%
256	512	200.00%
512	1024	200.00%
1024	1280	125.00%
1280	1696	132.50%
1696	2304	135.85%
2304	3072	133.33%
3072	4096	133.33%
4096	5120	125.00%
5120	7168	140.00%
7168	9216	128.57%
9216	12288	133.33%
12288	15360	125.00%
15360	19456	126.67%

很明显的可以看到，在 cap 长度小于 1024 之前，每次新数组的长度都是旧数组的两倍。但是在 1024 之后增长的速度，最低增长 25%，最高能达到 40%。长度在 1024 之前的很容易理解，可是为什么在 1024 之后会出现这种情况我们就需要翻翻源码了。

slice 增加长度的源码在 src/runtime/slice.go 的 growslice 函数中。

关键代码如下：

func growslice(et *_type, old slice, cap int) slice {
    // et 是 slice 中元素的类型
    // old 是与老的 slice
    // cap 是增长之后需要的最小的 slice 的 cap 长度

    // 略过一部分代码

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        // 如果老的长度小于 1024，直接翻倍
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // 如果老的长度大于 1024，如果老的长度小于需求的最小长度，
            // 增加 25% 容量
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // 略过一部分代码

    switch {
    case et.size == 1:
        // 略
    case et.size == sys.PtrSize:
        lenmem = uintptr(old.len) * sys.PtrSize
        newlenmem = uintptr(cap) * sys.PtrSize

        // 主要部分是下面一句以及计算 newcap
        // roundupsize 函数根据新的 cap 计算所需要的内存进行对齐，
        // 从而最后导致 newcap 的不是原先的 125%，而是大于等于 125%

        // roundupsize 分配内存也会根据请求的内存大小选择去什么地
        // 方分配内存，这部分内容就不在本篇文章的叙述范围了。
        capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
        newcap = int(capmem / sys.PtrSize)
    case isPowerOfTwo(et.size):
        // 略
    default:
        // 略
    }
    // 略过一部分代码
}

最后总结一下：slice 在 cap 长度小于 1024 之前容量是翻倍增长，在 cap 长度大于 1024 之后，因为存在着内存对齐，slice 的容量增长方式是最小增加 25%。