切片的容量

[5]int[]int
arraylencapmake([]int, len)capmake([]int, len, cap)capcap=lenarray
append

 

a := make([]int, 5)
b := a[0:4]
a = append(a, 1)
a[1] = 5
fmt.Println(b)
// [0 0 0 0]
fmt.Println(a)
// [0 5 0 0 0 1]</pre>
aabab

试比较

 

a := make([]int, 5, 6)
b := a[0:4]
a = append(a, 1)
a[1] = 5
fmt.Println(a, b)
// [0 5 0 0 0 1] [0 5 0 0]
aappendarrayab

扩容机制

a := []int{}

 

a := []int{}
for i := 0; i < 16; i++ {
    a = append(a, i)
    fmt.Print(cap(a), " ")
}
// 1 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16
append

如果一次添加多个元素,容量又会怎样变化呢?试比较下面两个例子:

 

a := []int{}
for i := 0; i < 16; i++ {
    a = append(a, 1, 2, 3, 4, 5)
    fmt.Print(cap(a), " ")
}
// 6 12 24 24 48 48 48 48 48 96 96 96 96 96 96 96 </pre>

<pre class="cm-s-default" style="box-sizing: border-box; font-size: inherit; font-family: inherit; margin: 0px; overflow: visible; padding: 0px; border-radius: 0px; border-width: 0px; background: transparent; white-space: pre; overflow-wrap: normal; line-height: inherit; color: inherit; z-index: 2; position: relative; -webkit-tap-highlight-color: transparent; font-variant-ligatures: contextual;">a := []int{}
for i := 0; i < 16; i++ {
    a = append(a, 1, 2, 3, 4, 5, 6)
    fmt.Print(cap(a), " ")
}
// 6 12 24 24 48 48 48 48 96 96 96 96 96 96 96 96
2n-12n

 

// int8
a := []int8{}
for i := 0; i < 16; i++ {
    a = append(a, 1, 2, 3, 4, 5, 6)
    fmt.Print(cap(a), " ")
}
// 8 16 32 32 32 64 64 64 64 64 128 128 128 128 128 128

// int16
fmt.Println()
b := []int16{}
for i := 0; i < 16; i++ {
    b = append(b, 1, 2, 3, 4, 5)
    fmt.Print(cap(b), " ")
}
// 8 16 32 32 32 64 64 64 64 64 128 128 128 128 128 128

// bool
fmt.Println()
c := []bool{}
for i := 0; i < 16; i++ {
    c = append(c, true, false, true, false, false)
    fmt.Print(cap(c), " ")
}
// 8 16 32 32 32 64 64 64 64 64 128 128 128 128 128 128

// float32
fmt.Println()
d := []float32{}
for i := 0; i < 16; i++ {
    d = append(d, 1.1, 2.2, 3.3, 4.4, 5.5)
    fmt.Print(cap(d), " ")
}
// 8 16 16 32 32 32 64 64 64 64 64 64 128 128 128 128 

// float64
fmt.Println()
e := []float64{}
for i := 0; i < 16; i++ {
    e = append(e, 1.1, 2.2, 3.3, 4.4, 5.5)
    fmt.Print(cap(e), " ")
}
// 6 12 24 24 48 48 48 48 48 96 96 96 96 96 96 96 

// string
fmt.Println()
f := []string{}
for i := 0; i < 16; i++ {
    f = append(f, "1.1", "2.2", "3.3", "4.4", "5.5")
    fmt.Print(cap(f), " ")
}
// 5 10 20 20 40 40 40 40 80 80 80 80 80 80 80 80 

// []int
fmt.Println()
g := [][]int{}
g1 := []int{1, 2, 3, 4, 5}
for i := 0; i < 16; i++ {
    g = append(g, g1, g1, g1, g1, g1)
    fmt.Print(cap(g), " ")
}
// 5 10 20 20 42 42 42 42 85 85 85 85 85 85 85 85

可以看到,根据切片对应数据类型的不同,容量增长的方式也有很大的区别。相关的源码包括:src/runtime/msize.go,src/runtime/mksizeclasses.go等。

我们再看看切片初始非空的情形。

 

a := []int{1, 2, 3}
fmt.Println(cap(a))
// 3
for i := 0; i < 16; i++ {
    a = append(a, 1, 2)
    fmt.Print(cap(a), " ")
}
// 6 12 12 12 24 24 24 24 24 24 48 48 48 48 48 48

可以看到,与刚刚向空切片添加5个int的情况一致,向有3个int的切片中添加2个int,容量增长为6。

append

 

a := []int{1, 2, 3, 4}
fmt.Println(cap(a))
// 4
for i := 0; i < 20; i++ {
    a = append(a, a...)
    fmt.Print(cap(a), " ")
}
// 8 16 32 64 128 256 512 1024 2560 5120 10240 20480 40960 80896 158720 310272 606208 1184768 2314240 4520960
src/runtime/slice.gogrowslice

 

// src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
// ...省略部分
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
// ...省略部分
}
  • 当需要的容量超过原切片容量的两倍时,会使用需要的容量作为新容量。
  • 当原切片长度小于1024时,新切片的容量会直接翻倍。而当原切片的容量大于等于1024时,会反复地增加25%,直到新容量超过所需要的容量。

结论

GoLang中的切片扩容机制,与切片的数据类型、原本切片的容量、所需要的容量都有关系,比较复杂。对于常见数据类型,在元素数量较少时,大致可以认为扩容是按照翻倍进行的。但具体情况需要具体分析。

copy

参考文献