深入理解Go语言append函数的计算复杂度与性能优化

func growslice(et *_type, old slice, cap int) slice {
    // ...
    newcap := old.cap
    doublecap := newcap + newcap // 尝试将容量翻倍
    if cap > doublecap {
        // 如果所需容量（cap）大于当前容量的两倍，则直接使用所需容量
        newcap = cap
    } else {
        if old.len < 1024 {
            // 如果旧切片长度小于1024，容量直接翻倍
            newcap = doublecap
        } else {
            // 如果旧切片长度大于等于1024，容量每次增加25%，直到满足需求
            for newcap < cap {
                newcap += newcap / 4
            }
        }
    }
    // ...
    // 根据newcap分配新内存并复制数据
}

package main

import "fmt"

// Generous reallocation (模拟Go gc的慷慨策略)
func constant(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        newcap := len(s) + len(x)
        m := cap(s)
        if m+m < newcap { // 如果当前容量翻倍仍不足
            m = newcap // 直接扩容到所需容量
        } else {
            for { // 否则按Go的策略扩容
                if len(s) < 1024 {
                    m += m // 小切片翻倍
                } else {
                    m += m / 4 // 大切片增加25%
                }
                if !(m < newcap) {
                    break
                }
            }
        }
        tmp := make([]int, len(s), m) // 创建新切片，容量为m
        copy(tmp, s)                  // 复制旧数据
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable") // 确保容量足够
    }
    return append(s, x...) // 使用Go内置append完成实际添加（此时容量已足够）
}

// Parsimonious reallocation (吝啬策略)
func variable(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        // 每次只扩容到刚好满足需求的容量
        tmp := make([]int, len(s), len(s)+len(x))
        copy(tmp, s)
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable")
    }
    return append(s, x...) // 使用Go内置append完成实际添加
}

func main() {
    s := []int{0, 1, 2}
    x := []int{3, 4}
    fmt.Println("data    ", len(s), cap(s), s, len(x), cap(x), x)
    a, c, v := s, s, s
    for i := 0; i < 4096; i++ { // 循环append多次
        a = append(a, x...)
        c = constant(c, x...)
        v = variable(v, x...)
    }
    fmt.Println("append  ", len(a), cap(a), len(x))
    fmt.Println("constant", len(c), cap(c), len(x))
    fmt.Println("variable", len(v), cap(v), len(x))
}

data     3 3 [0 1 2] 2 2 [3 4]
append   8195 9152 2
constant 8195 9152 2
variable 8195 8195 2