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.gogrowslice 函数中。

关键代码如下:

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%。

back