Go 语言切片是如何扩容的？

在 Go 语言中，有一个很常用的数据结构，那就是切片（Slice）。

切片是一个拥有相同类型元素的可变长度的序列，它是基于数组类型做的一层封装。它非常灵活，支持自动扩容。

切片是一种引用类型，它有三个属性：指针，长度和容量。

slict1.png

底层源码定义如下：

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

指针： 指向 slice 可以访问到的第一个元素。
长度： slice 中元素个数。
容量： slice 起始元素到底层数组最后一个元素间的元素个数。

比如使用 make([]byte, 5) 创建一个切片，它看起来是这样的：

slice2.png

声明和初始化

切片的使用还是比较简单的，这里举一个例子，直接看代码吧。

func main() {
    var nums []int  // 声明切片
    fmt.Println(len(nums), cap(nums)) // 0 0
    nums = append(nums, 1)   // 初始化
    fmt.Println(len(nums), cap(nums)) // 1 1

    nums1 := []int{1,2,3,4}    // 声明并初始化
    fmt.Println(len(nums1), cap(nums1))    // 4 4

    nums2 := make([]int,3,5)   // 使用make()函数构造切片
    fmt.Println(len(nums2), cap(nums2))    // 3 5
}

扩容时机

当切片的长度超过其容量时，切片会自动扩容。这通常发生在使用 append 函数向切片中添加元素时。

扩容时，Go 运行时会分配一个新的底层数组，并将原始切片中的元素复制到新数组中。然后，原始切片将指向新数组，并更新其长度和容量。

需要注意的是，由于扩容会分配新数组并复制元素，因此可能会影响性能。如果你知道要添加多少元素，可以使用 make 函数预先分配足够大的切片来避免频繁扩容。

接下来看看 append 函数，签名如下：

func Append(slice []int, items ...int) []int

append 函数参数长度可变，可以追加多个值，还可以直接追加一个切片。使用起来比较简单，分别看两个例子：

追加多个值：

package main

import "fmt"

func main() {
    s := []int{1, 2, 3}
    fmt.Println("初始切片:", s)

    s = append(s, 4, 5, 6)
    fmt.Println("追加多个值后的切片:", s)
}

输出结果为：

初始切片: [1 2 3]
追加多个值后的切片: [1 2 3 4 5 6]

再来看一下直接追加一个切片：

package main

import "fmt"

func main() {
    s1 := []int{1, 2, 3}
    fmt.Println("初始切片:", s1)

    s2 := []int{4, 5, 6}
    s1 = append(s1, s2...)
    fmt.Println("追加另一个切片后的切片:", s1)
}

输出结果为：

初始切片: [1 2 3]
追加另一个切片后的切片: [1 2 3 4 5 6]

再来看一个发生扩容的例子：

package main

import "fmt"

func main() {
    s := make([]int, 0, 3) // 创建一个长度为0，容量为3的切片
    fmt.Printf("初始状态: len=%d cap=%d %v\n", len(s), cap(s), s)

    for i := 1; i <= 5; i++ {
        s = append(s, i) // 向切片中添加元素
        fmt.Printf("添加元素%d: len=%d cap=%d %v\n", i, len(s), cap(s), s)
    }
}

输出结果为：

初始状态: len=0 cap=3 []
添加元素1: len=1 cap=3 [1]
添加元素2: len=2 cap=3 [1 2]
添加元素3: len=3 cap=3 [1 2 3]
添加元素4: len=4 cap=6 [1 2 3 4]
添加元素5: len=5 cap=6 [1 2 3 4 5]

在这个例子中，我们创建了一个长度为 0，容量为 3 的切片。然后，我们使用 append 函数向切片中添加 5 个元素。

当我们添加第 4 个元素时，切片的长度超过了其容量。此时，切片会自动扩容。新的容量是原始容量的两倍，即 6。

表面现象已经看到了，接下来，我们就深入到源码层面，看看切片的扩容机制到底是什么样的。

源码分析

在 Go 语言的源码中，切片扩容通常是在进行切片的 append 操作时触发的。在进行 append 操作时，如果切片容量不足以容纳新的元素，就需要对切片进行扩容，此时就会调用 growslice 函数进行扩容。

growslice 函数定义在 Go 语言的 runtime 包中，它的调用是在编译后的代码中实现的。具体来说，当执行 append 操作时，编译器会将其转换为类似下面的代码：

slice = append(slice, elem)

在上述代码中，如果切片容量不足以容纳新的元素，则会调用 growslice 函数进行扩容。所以 growslice 函数的调用是由编译器在生成的机器码中实现的，而不是在源代码中显式调用的。

切片扩容策略有两个阶段，go1.18 之前和之后是不同的，这一点在 go1.18 的 release notes 中有说明。

下面我用 go1.17 和 go1.18 两个版本来分开说明。先通过一段测试代码，直观感受一下两个版本在扩容上的区别。

package main

import "fmt"

func main() {
    s := make([]int, 0)

    oldCap := cap(s)

    for i := 0; i < 2048; i++ {
        s = append(s, i)

        newCap := cap(s)

        if newCap != oldCap {
            fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
            oldCap = newCap
        }
    }
}

上述代码先创建了一个空的 slice，然后在一个循环里不断往里面 append 新元素。

然后记录容量的变化，每当容量发生变化的时候，记录下老的容量，添加的元素，以及添加完元素之后的容量。

这样就可以观察，新老 slice 的容量变化情况，从而找出规律。

运行结果（1.17 版本）：

[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

运行结果（1.18 版本）：

[0 ->   -1] cap = 0     |  after append 0     cap = 1
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 848 
[0 ->  847] cap = 848   |  after append 848   cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1792
[0 -> 1791] cap = 1792  |  after append 1792  cap = 2560

根据上面的结果还是能看到区别的，具体扩容策略下面边看源码边说明。

go1.17

扩容调用的是 growslice 函数，我复制了其中计算新容量部分的代码。

// 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.cap < 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
            }
        }
    }

    // ...

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

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

如果期望容量大于当前容量的两倍就会使用期望容量；
如果当前切片的长度小于 1024 就会将容量翻倍；
如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

go1.18

// 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 {
        const threshold = 256
        if old.cap < threshold {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                // Transition from growing 2x for small slices
                // to growing 1.25x for large slices. This formula
                // gives a smooth-ish transition between the two.
                newcap += (newcap + 3*threshold) / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

    // ...

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

和之前版本的区别，主要在扩容阈值，以及这行代码：newcap += (newcap + 3*threshold) / 4。

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

如果期望容量大于当前容量的两倍就会使用期望容量；
如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；

内存对齐

分析完两个版本的扩容策略之后，再看前面的那段测试代码，就会发现扩容之后的容量并不是严格按照这个策略的。

那是为什么呢？

实际上，growslice 的后半部分还有更进一步的优化（内存对齐等），靠的是 roundupsize 函数，在计算完 newcap 值之后，还会有一个步骤计算最终的容量：

capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)

这个函数的实现就不在这里深入了，先挖一个坑，以后再来补上。

总结

切片扩容通常是在进行切片的 append 操作时触发的。在进行 append 操作时，如果切片容量不足以容纳新的元素，就需要对切片进行扩容，此时就会调用 growslice 函数进行扩容。

切片扩容分两个阶段，分为 go1.18 之前和之后：

一、go1.18 之前：

如果期望容量大于当前容量的两倍就会使用期望容量；
如果当前切片的长度小于 1024 就会将容量翻倍；
如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

二、go1.18 之后：

如果期望容量大于当前容量的两倍就会使用期望容量；
如果当前切片的长度小于阈值（默认 256）就会将容量翻倍；
如果当前切片的长度大于等于阈值（默认 256），就会每次增加 25% 的容量，基准是 newcap + 3*threshold，直到新容量大于期望容量；

以上就是本文的全部内容，如果觉得还不错的话欢迎点赞，转发和关注，感谢支持。

参考文章：

https://go.dev/doc/go1.18
https://go.dev/blog/slices
https://go.dev/blog/slices-intro
https://golang.design/go-questions/slice/grow/
https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-array-and-slice/

推荐阅读：

Go 语言数组和切片的区别
Go 语言 new 和 make 关键字的区别
为什么 Go 不支持 []T 转换为 []interface
为什么 Go 语言 struct 要使用 tags

?著作权归作者所有,转载或内容合作请联系作者

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,172评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,346评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,788评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,299评论 1赞 288
?港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,409评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,467评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,476评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,262评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,699评论 1赞 307
?护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,994评论 2赞 328
?白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,167评论 1赞 343
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,827评论 4赞 337
?日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,499评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,149评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,387评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,028评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,055评论 2赞 352

传奇手游全部平台_三端传奇开服网址大全下载_三端传奇版本下载教程

Go 语言切片是如何扩容的？

Go 语言切片是如何扩容的？

声明和初始化

扩容时机

源码分析

go1.17

go1.18

内存对齐

总结

推荐阅读更多精彩内容

传奇手游全部平台_三端传奇开服网址大全下载_三端传奇版本下载教程

Go 语言切片是如何扩容的？

声明和初始化

扩容时机

源码分析

go1.17

go1.18

内存对齐

总结

推荐阅读更多精彩内容

Go 语言切片是如何扩容的？