Go语言-切片的容量是怎样增长的

这篇具有很好参考价值的文章主要介绍了Go语言-切片的容量是怎样增长的。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一般都是在向 slice 追加了元素之后,才会引起扩容。追加元素调用的是 append 函数。

先来看看 append 函数的原型:

func append(slice []Type, elems ...Type) []Type

append 函数的参数长度可变,因此可以追加多个值到 slice 中,还可以用...传入 slice,直接追加一个切片。

slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)

append函数返回值是一个新的slice,Go编译器不允许调用了 append 函数后不使用返回值。

append(slice, elem1, elem2)
append(slice, anotherSlice...)

所以上面的用法是错的,不能编译通过。

使用 append 可以向 slice 追加元素,实际上是往底层数组添加元素。但是底层数组的长度是固定的,如果索引 len-1 所指向的元素已经是底层数组的最后一个元素,就没法再添加了。

这时,slice 会迁移到新的内存位置,新底层数组的长度也会增加,这样就可以放置新增的元素。同时,为了应对未来可能再次发生的 append 操作,新的底层数组的长度,也就是新 slice 的容量是留了一定的 buffer 的。否则,每次添加元素的时候,都会发生迁移,成本太高。

新 slice 预留的 buffer 大小是有一定规律的。网上大多数的文章都是这样描述的:

当原 slice 容量小于 1024 的时候,新 slice 容量变成原来的 2 倍;原 slice 容量超过 1024,新 slice 容量变成原来的1.25倍。

我在这里先说结论:以上描述是错误的。

为了说明上面的规律是错误的,我写了一小段玩具代码:

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 里的元素。这样,我就可以观察,新老 slice 的容量变化情况,从而找出规律。

运行结果:

[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

在老 slice 容量小于1024的时候,新 slice 的容量的确是老 slice 的2倍。目前还算正确。

但是,当老 slice 容量大于等于 1024 的时候,情况就有变化了。当向 slice 中添加元素 1280 的时候,老 slice 的容量为 1280,之后变成了 1696,两者并不是 1.25 倍的关系(1696/1280=1.325)。添加完 1696 后,新的容量 2304 当然也不是 16961.25 倍。

可见,现在网上各种文章中的扩容策略并不正确。我们直接搬出源码:源码面前,了无秘密。

从前面汇编代码我们也看到了,向 slice 追加元素的时候,若容量不够,会调用 growslice 函数,所以我们直接看它的代码。

// go 1.9.5 src/runtime/slice.go:82
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 {
            for newcap < cap {
                newcap += newcap / 4
            }
        }
    }
    // ……

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

看到了吗?如果只看前半部分,现在网上各种文章里说的 newcap 的规律是对的。现实是,后半部分还对 newcap 作了一个内存对齐,这个和内存分配策略相关。进行内存对齐之后,新 slice 的容量是要 大于等于 老 slice 容量的 2倍或者1.25倍。

之后,向 Go 内存管理器申请内存,将老 slice 中的数据复制过去,并且将 append 的元素添加到新的底层数组中。

最后,向 growslice 函数调用者返回一个新的 slice,这个 slice 的长度并没有变化,而容量却增大了。

【引申1】

来看一个例子,来源于这里

package main

import "fmt"

func main() {
    s := []int{5}
    s = append(s, 7)
    s = append(s, 9)
    x := append(s, 11)
    y := append(s, 12)
    fmt.Println(s, x, y)
}
代码 切片对应状态
s := []int{5} s 只有一个元素,[5]
s = append(s, 7) s 扩容,容量变为2,[5, 7]
s = append(s, 9) s 扩容,容量变为4,[5, 7, 9]。注意,这时 s 长度是3,只有3个元素
x := append(s, 11) 由于 s 的底层数组仍然有空间,因此并不会扩容。这样,底层数组就变成了 [5, 7, 9, 11]。注意,此时 s = [5, 7, 9],容量为4;x = [5, 7, 9, 11],容量为4。这里 s 不变
y := append(s, 12) 这里还是在 s 元素的尾部追加元素,由于 s 的长度为3,容量为4,所以直接在底层数组索引为3的地方填上12。结果:s = [5, 7, 9],y = [5, 7, 9, 12],x = [5, 7, 9, 12],x,y 的长度均为4,容量也均为4

所以最后程序的执行结果是:

[5 7 9] [5 7 9 12] [5 7 9 12]

这里要注意的是,append函数执行完后,返回的是一个全新的 slice,并且对传入的 slice 并不影响。

【引申2】

关于 append,我们最后来看一个例子,来源于 Golang Slice的扩容规则。

package main

import "fmt"

func main() {
    s := []int{1,2}
    s = append(s,4,5,6)
    fmt.Printf("len=%d, cap=%d",len(s),cap(s))
}

运行结果是:
len=5, cap=6

如果按网上各种文章中总结的那样:小于原 slice 长度小于 1024 的时候,容量每次增加 1 倍。添加元素 4 的时候,容量变为4;添加元素 5 的时候不变;添加元素 6 的时候容量增加 1 倍,变成 8。

那上面代码的运行结果就是:

len=5, cap=8

这是错误的!我们来仔细看看,为什么会这样,再次搬出代码:

// go 1.9.5 src/runtime/slice.go:82
func growslice(et *_type, old slice, cap int) slice {
    // ……
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        // ……
    }
    // ……

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

这个函数的参数依次是 元素的类型,老的 slice,新 slice 最小求的容量。

例子中 s 原来只有 2 个元素,lencap 都为 2,append 了三个元素后,长度变为 5,容量最小要变成 5,即调用 growslice 函数时,传入的第三个参数应该为 5。即 cap=5。而一方面,doublecap 是原 slice容量的 2 倍,等于 4。满足第一个 if 条件,所以 newcap 变成了 5。

接着调用了 roundupsize 函数,传入 40。(代码中ptrSize是指一个指针的大小,在64位机上是8)

我们再看内存对齐,搬出 roundupsize 函数的代码:

// src/runtime/msize.go:13
func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= smallSizeMax-8 {
            return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
        } else {
            //……
        }
    }
    //……
}

const _MaxSmallSize = 32768
const smallSizeMax = 1024
const smallSizeDiv = 8

很明显,我们最终将返回这个式子的结果:

class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]]

这是 Go 源码中有关内存分配的两个 slice。class_to_size通过 spanClass获取 span划分的 object大小。而 size_to_class8 表示通过 size 获取它的 spanClass。

var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31}

var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}

我们传进去的 size 等于 40。所以 (size+smallSizeDiv-1)/smallSizeDiv = 5;获取 size_to_class8 数组中索引为 5 的元素为 4;获取 class_to_size 中索引为 4 的元素为 48。

最终,新的 slice 的容量为 6:

newcap = int(capmem / ptrSize) // 6

至于,上面的两个魔法数组的由来,就不展开了。

【引申2】
向一个nil的slice添加元素会发生什么?为什么?

其实 nil slice 或者 empty slice 都是可以通过调用 append 函数来获得底层数组的扩容。最终都是调用 mallocgc 来向 Go 的内存管理器申请到一块内存,然后再赋给原来的nil slice 或 empty slice,然后摇身一变,成为“真正”的 slice 了。

更多宝藏

🍇🍉🍊🍏🍋🍅🥝🥥🫒🫕🥗
视频推送看这里🤤:
https://space.bilibili.com/1909782963
项目仓库看这里🤗:
https://github.com/w-x-x-w
https://gitee.com/w-_-x
公众号名称😮:编程启航
博客文章看这里🤭:
https://blog.csdn.net/weixin_62650212文章来源地址https://www.toymoban.com/news/detail-529415.html

到了这里,关于Go语言-切片的容量是怎样增长的的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Golang】VsCode下开发Go语言的环境配置(超详细图文详解)

    📓推荐网站(不断完善中):个人博客 📌个人主页:个人主页 👉相关专栏:CSDN专栏、个人专栏 🏝立志赚钱,干活想躺,瞎分享的摸鱼工程师一枚 ​ 话说在前,Go语言的编码方式是 UTF-8 ,理论上你直接使用文本进行编辑也是可以的,当然为了提升我们的开发效率我们还是需

    2024年02月07日
    浏览(81)
  • 【Go】Go 语言教程--GO语言切片(Slice)(十四)

    往期回顾: Go 语言教程–介绍(一) Go 语言教程–语言结构(二) Go 语言教程–语言结构(三) Go 语言教程–数据类型(四) Go 语言教程–语言变量(五) Go 语言教程–GO语言常量(六) Go 语言教程–GO语言运算符(七) Go 语言教程–GO条件和循环语句(八) Go 语言教程

    2024年02月16日
    浏览(49)
  • go语言中的切片

    切片(Slice)是一个拥有相同类型元素的可变长度的序列。它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。 切片是一个引用类型,它的内部结构包含 地址 、 长度 和 容量 。切片一般用于快速地操作一块数据集合。 切片的本质就是对底层数组的封装,它包含了

    2024年02月11日
    浏览(40)
  • Go语言基础之切片

    切片(Slice)是一个拥有相同类型元素的可变长度的序列。它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。 切片是一个引用类型,它的内部结构包含地址、长度和容量。切片一般用于快速地操作一块数据集合 声明切片类型的基本语法如下: 其中, name:表示变

    2024年02月11日
    浏览(53)
  • Go 语言切片是如何扩容的?

    原文链接: Go 语言切片是如何扩容的? 在 Go 语言中,有一个很常用的数据结构,那就是切片(Slice)。 切片是一个拥有相同类型元素的可变长度的序列,它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。 切片是一种引用类型,它有三个属性: 指针 , 长度 和

    2023年04月09日
    浏览(39)
  • 【go语言】2.2.1 数组和切片

    数组和切片是 Go 语言中常用的数据结构,它们都可以存储多个同类型的元素。 数组是具有固定长度的数据类型,它的长度在定义时就已经确定,不能随意改变。 你可以使用以下方式定义一个数组: 这段代码定义了一个长度为 3 的  int  类型数组  arr 。你也可以在定义时初

    2024年02月15日
    浏览(48)
  • 【Go语言快速上手(三)】数组, 切片与映射

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:Go语言专栏⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习更多Go语言知识   🔝🔝 在了解过GO的控制语句和函数后,按照学习语言的逻辑也理应进入到容器的学习,GO语言的容易比较特殊,它不像C++一样有专门的STL库

    2024年04月29日
    浏览(66)
  • Go语言中的数组、切片和映射解析

    数组存放的是固定长度、相同类型的数据,而且这些存放的元素是连续的。 例如声明一个整形数组: 在类型名前加 [] 中括号,并设置好长度,大括号中的元素用于初始化数组,需要注意的是数组的长度不同,即属于不同的类型。 如果所有元素都被初始化的数组,声明时可以

    2024年02月09日
    浏览(44)
  • 从源码分析 Go 语言使用 cgo 导致的线程增长

    TDengine Go 连接器 https://github.com/taosdata/driver-go 使用 cgo 调用 taos.so 中的 API,使用过程中发现线程数不断增长,本文从一个 cgo 调用开始解析 Go 源码,分析造成线程增长的原因。 对 driver-go/wrapper/taosc.go 进行转换 go tool cgo taosc.go 执行后生成 _obj 文件夹 以 taosc.cgo1.go 中 TaosResetC

    2024年02月07日
    浏览(52)
  • Go 语言中高效切片拼接和 GO 1.22 提供的新方法

    在 Go 语言中,切片拼接是一项常见的操作,但如果处理不当,可能会导致性能问题或意外的副作用。 本文将详细介绍几种高效的切片拼接方法,包括它们的优缺点以及适用场景。 在 Go 中,切片是一种动态数组,常用于存储和处理一系列相同类型的数据。 在实际应用中,我

    2024年01月19日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包