Go语言append操作的时间复杂度深度解析

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap { // 如果所需容量直接超过了翻倍后的容量，则直接使用所需容量
        newcap = cap
    } else {
        if old.len < 1024 { // 小容量切片，容量翻倍
            newcap = doublecap
        } else { // 大容量切片，按1/4比例增长
            for newcap < cap { // 循环直到新容量足够
                newcap += newcap / 4
            }
        }
    }

package main

import "fmt"

// constant 函数模拟了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 { // 否则，按照gc的策略进行扩容
            for {
                if len(s) < 1024 { // 小容量翻倍
                    m += m
                } else { // 大容量按1/4增长
                    m += m / 4
                }
                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")
    }
    // 使用Go内置append完成实际添加，因为此时容量已足够
    return append(s, x...)
}

// variable 函数模拟了吝啬扩容策略，每次只分配刚好够用的内存
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")
    }
    // 使用Go内置append完成实际添加，因为此时容量已足够
    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)

    a, c, v := s, s, s // 初始化三个切片，分别用于测试append, constant, variable

    // 进行大量append操作，观察容量变化
    for i := 0; i < 4096; i++ {
        a = append(a, x...)      // Go内置append
        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