深入理解Go语言append函数的计算复杂度

    newcap := old.cap // 初始新容量为旧容量
    doublecap := newcap + newcap // 双倍容量
    if cap > doublecap { // 如果需要的容量大于双倍容量，则直接使用所需容量
        newcap = cap
    } else {
        if old.len < 1024 { // 如果旧长度小于1024，则容量翻倍
            newcap = doublecap
        } else { // 如果旧长度大于等于1024，则每次增长1/4
            for newcap < cap { // 循环直到新容量满足需求
                newcap += newcap / 4
            }
        }
    }

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) // 当前容量

        // 扩容逻辑与gc growslice类似
        if m+m < newcap { // 如果翻倍容量仍不足，直接使用所需容量
            m = newcap
        } else {
            for { // 否则，根据长度进行翻倍或1.25倍增长
                if len(s) < 1024 {
                    m += m // 小于1024时翻倍
                } else {
                    m += m / 4 // 大于等于1024时增长1/4
                }
                if !(m < newcap) { // 直到新容量满足需求
                    break
                }
            }
        }

        // 创建新切片，拷贝旧数据
        tmp := make([]int, len(s), m)
        copy(tmp, s)
        s = tmp
    }
    // 确保容量足够后，追加元素（这里为了简化，直接调用内置append）
    // 实际实现会直接将x追加到s的底层数组
    return append(s, x...)
}

// 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
    }
    return append(s, x...)
}

func main() {
    s := []int{0, 1, 2}
    x := []int{3, 4}
    fmt.Println("data    ", len(s), cap(s), s, len(x), cap(x), x)

    // 初始化三个切片，分别用于测试内置append、慷慨分配和吝啬分配
    a, c, v := s, s, s 

    // 循环追加大量元素
    for i := 0; i < 4096; i++ {
        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