golang 切片扩容

容量计算

在 golang 中,当切片中元素个数大于其容量时,该切片会触发切片扩容.那么扩容后,切片的容量是多少呢?我们应该如何计算呢?

现有如下代码,以 int32 与 int64 为例分别计算切片扩容后的长度和容量.

import (
 "flag"
 "fmt"
)

func main() {
 var arr32 []int32
 var arr64 []int64
 var num = flag.Int("num", 0, "append element num")
 flag.Parse()
 for i := 0; i < *num; i++ {
  arr32 = append(arr32, int32(i))
 }
 fmt.Println(len(arr32), cap(arr32))

 for i := 0; i < *num; i++ {
  arr64 = append(arr64, int64(i))
 }
 fmt.Println(len(arr64), cap(arr64))
}

上述代码在 go/1.18.1 版本之前执行结果如下:

# go version before 1.18.1

# go run main.go -num 513
513 1024
513 1024

# go run main.go -num  1025
1025 1344
1025 1280

在 go/1.18.1 版本之后执行结果如下:

# go version after 1.18.1

# go run main.go -num 257
257 512
257 512

# go run main.go -num 513
513 864
513 848

# go run main.go -num 1024
1024 1344
1024 1280

可以看到切片的扩容后容量大小与 golang 版本及切片中元素类型(主要是元素所占的 bytes 数)有一定的关系.

源码阅读

下面我们通过阅读 golang 切片相关源码来搞清楚产生上述差异的原因

1.18 之前

以 go/1.17.10 为例,我们来尝试阅读切片扩容的逻辑

func growslice(et *_type, old slice, cap int) slice {
    // 省略部分代码,扩容开始
    // 1. 主要是计算 newcap 的值
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        // 1.1 当 cap 小于 1024 时,扩容为双倍
        if old.cap < 1024 {
            newcap = doublecap
        } else {
            // 1.2 当 cap 大于 1024 时,扩容为之前的 1.25 倍
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // 1.3 当 newcap 溢出时,设置为当前的容量
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // 2. 内存对齐.大概计算公式如下:
    // 2.1 计算保存扩容后切片所需的所有 bit 数,计算公式为 `capmem = newcap * element_size`
    // 2.2 将 `capmem` 带入 `roundupsize` 函数,根据此函数取得对应数组中对应的值,该值即内存对齐后该切片所需的最小字节数. `roundupsize` 函数的计算结果可以在 `runtime/sizeclasses.go` 中的注释表中查到,计算结果为表中 `bytes/obj` 列不小于 `capmem` 的最小值
    // 2.3 最后将所需字节数 / element_size 即为扩容后切片的容量
    switch {
    // ... 省略部分代码
    default:
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }

    // 3. 分配内存,并将原来的元素移到新的切片中
    // ... 省略部分代码
    memmove(p, old.array, lenmem)

    return slice{p, old.len, newcap}
}

因此计算步骤大致可以总结如下:

根据计算公式获取应该扩容的容量.
1. 如果当前切片容量小于 1024,扩容切片容量 newcap = oldcap * 2
2. 如果当前切片容量大于等于 1024,扩容切片容量 newcap = oldcap * 1.25
内存对齐
1. 根据上一步得到的容量及元素计算出所需要的字节数 newcap * element_size.如 bytes= newcap * 4(int32), bytes=newcap * 8(int64).
2. 通过 runtime/sizeclasses.go 查表,找到 bytes/obj 列中大于该 bytes 的最小值.
3. 使用该值除以 element_size 即为扩容后的容量大小

1.18 之后

func growslice(et *_type, old slice, cap int) slice {
    // 省略部分代码
    // 1. 与之前的版本类似,同样是计算 newcap 的值,只是在计算公式上有所变动
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        // 1.1 当容量 <256 时,默认为 2 倍扩容
        const threshold = 256
        if old.cap < threshold {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                // 1.2 当旧切片容量不小于 256 时,按照如下公式扩容.这样保证可以在容量较小时双倍扩容,在容量较大时,少量扩容
                newcap += (newcap + 3*threshold) / 4
            }
            // 1.3 同样的,当 newcap 溢出时,设置为当前的容量
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // 2. 与 1.18.1 之前一样,做内存对齐
    // ...省略部分代码
    switch {
    
    default:
        // 对齐方式与之前一样,不再赘述
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }

    //3. 分配内存,并将原来的元素移到新的切片中
    // ... 省略部分代码
    memmove(p, old.array, lenmem)

    return slice{p, old.len, newcap}
}