您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > Go语言

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

时间:2023-04-03 14:09:52  来源:AlwaysBeta  作者:yongxinz

在 Go 语言中,有一个很常用的数据结构,那就是切片(Slice)。

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

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

图片

底层源码定义如下:

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}
  1. 指针: 指向 slice 可以访问到的第一个元素。
  2. 长度: slice 中元素个数。
  3. 容量: slice 起始元素到底层数组最后一个元素间的元素个数。

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

图片

声明和初始化

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

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 %vn", len(s), cap(s), s)

    for i := 1; i <= 5; i++ {
        s = append(s, i) // 向切片中添加元素
        fmt.Printf("添加元素%d: len=%d cap=%d %vn", 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 = %-4dn", 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}
}
 

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

  1. 如果期望容量大于当前容量的两倍就会使用期望容量;
  2. 如果当前切片的长度小于 1024 就会将容量翻倍;
  3. 如果当前切片的长度大于等于 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。

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

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

内存对齐

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

那是为什么呢?

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

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

 

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

总结

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

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

一、go1.18 之前:

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

二、go1.18 之后:

  1. 如果期望容量大于当前容量的两倍就会使用期望容量;
  2. 如果当前切片的长度小于阈值(默认 256)就会将容量翻倍;
  3. 如果当前切片的长度大于等于阈值(默认 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/


Tags:Go 语言   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
Go 语言不支持并发读写 Map,为什么?
Go语言的map类型不支持并发读写的主要原因是并发读写会导致数据竞态(data race),这意味着多个 goroutine 可能同时访问并修改同一个 map,从而引发不确定的结果。在Go语言的设计...【详细内容】
2024-01-05  Search: Go 语言  点击:(81)  评论:(0)  加入收藏
Go 语言为什么建议多使用切片,少使用数组?
01 、介绍在 Go 语言中,数组固定长度,切片可变长度;数组和切片都是值传递,因为切片传递的是指针,所以切片也被称为“引用传递”。读者朋友们在使用 Go 语言开发项目时,或者在阅读...【详细内容】
2023-12-27  Search: Go 语言  点击:(134)  评论:(0)  加入收藏
Go 语言使用 Echo 构建高性能 Web 应用
Echo提供了一个高性能且易用的框架,用于构建Go语言编写的Web应用。它具备灵活的路由功能、方便的请求处理、强大的中间件支持和简单的JSON操作,非常适合快速开发API服务和Web...【详细内容】
2023-12-26  Search: Go 语言  点击:(134)  评论:(0)  加入收藏
Go 语言中并发的威力
发挥效率和响应能力并发是现代软件开发中的一个基本概念,它使程序能够同时执行多个任务,提高效率和响应能力。在本文中,我们将探讨并发在现代软件开发中的重要性,并深入了解 Go...【详细内容】
2023-12-21  Search: Go 语言  点击:(115)  评论:(0)  加入收藏
Go 语言字符串使用方式与技巧
01 介绍关于 Go 语言字符串的使用,我们需要了解标准库 strconv 和标准库 strings 的使用方式,它们分别用于字符串类型转换和字符串操作。本文我们重点介绍 Go 语言字符串使用...【详细内容】
2023-12-10  Search: Go 语言  点击:(159)  评论:(0)  加入收藏
Go 语言中的map和内存泄漏
Map在内存中总是会增长;它不会收缩。因此,如果map导致了一些内存问题,你可以尝试不同的选项,比如强制 Go 重新创建map或使用指针。在 Go 中使用map时,我们需要了解map增长和收缩...【详细内容】
2023-11-23  Search: Go 语言  点击:(248)  评论:(0)  加入收藏
Go 语言切片扩容规则是扩容2倍?1.25倍?到底几倍
切片,相信大家用了 Go 语言那么久这这种数据类型并不陌生,但是平日里聊到关于切片是如何扩容的,很多人可能会张口就来,切片扩容的时候,如果老切片的容量小于 1024 那么就再扩容 1...【详细内容】
2023-10-11  Search: Go 语言  点击:(219)  评论:(0)  加入收藏
Go 语言流行 ORM 框架
ORM,全称 Object-Relational Mapping,即对象-关系映射,是一种程序设计技术,用于实现面向对象编程语言里对象的表现形式与关系数据库中数据的存储之间的转换。在实际工作中,我们...【详细内容】
2023-10-05  Search: Go 语言  点击:(232)  评论:(0)  加入收藏
盘点 Go 语言的那些日志库:你用了哪个?
Go语言是一种高性能、简洁、并发友好的编程语言,广泛用于开发各种应用程序,如网络服务、微服务、云计算、区块链等。Go语言的标准库提供了一个基本的日志包(log),可以用于记录简...【详细内容】
2023-09-10  Search: Go 语言  点击:(224)  评论:(0)  加入收藏
为什么说 Go 语言字符串是不可变的?
最近有读者留言说,平时在写代码的过程中,是会对字符串进行修改的,但网上都说 Go 语言字符串是不可变的,这是为什么呢?这个问题本身并不困难,但对于新手来说确实容易产生困惑,今天就...【详细内容】
2023-05-29  Search: Go 语言  点击:(247)  评论:(0)  加入收藏
▌简易百科推荐
宝藏级Go语言开源项目——教你自己动手开发互联网搜索引擎
DIYSearchEngine 是一个能够高速采集海量互联网数据的开源搜索引擎,采用 Go 语言开发。Github 地址:https://github.com/johnlui/DIYSearchEngine运行方法首先,给自己准备一杯...【详细内容】
2024-03-12  OSC开源社区    Tags:Go语言   点击:(19)  评论:(0)  加入收藏
Go Gin框架实现优雅地重启和停止
在Web应用程序中,有时候我们需要重启或停止服务器,无论是因为更新代码还是进行例行维护。在这种情景下,我们需要保证应用程序的可用性和数据的一致性。这就需要优雅地关闭和重...【详细内容】
2024-01-30  源自开发者  微信公众号  Tags:Go   点击:(67)  评论:(0)  加入收藏
如何让Go程序以后台进程或daemon方式运行
本文探讨了如何通过Go代码实现在后台运行的程序。最近我用Go语言开发了一个WebSocket服务,我希望它能在后台运行,并在异常退出时自动重新启动。我的整体思路是将程序转为后台...【详细内容】
2024-01-26  Go语言圈  微信公众号  Tags:Go程序   点击:(60)  评论:(0)  加入收藏
深入Go底层原理,重写Redis中间件实战
Go语言以其简洁、高效和并发性能而闻名,深入了解其底层原理可以帮助我们更好地利用其优势。在本文中,我们将探讨如何深入Go底层原理,以及如何利用这些知识重新实现一个简单的Re...【详细内容】
2024-01-25  547蓝色星球    Tags:Go   点击:(68)  评论:(0)  加入收藏
Go 内存优化与垃圾收集
Go提供了自动化的内存管理机制,但在某些情况下需要更精细的微调从而避免发生OOM错误。本文将讨论Go的垃圾收集器、应用程序内存优化以及如何防止OOM(Out-Of-Memory)错误。Go...【详细内容】
2024-01-15  DeepNoMind  微信公众号  Tags:Go   点击:(63)  评论:(0)  加入收藏
Go函数指针是如何让你的程序变慢的?
导读Go 语言的常规优化手段无需赘述,相信大家也能找到大量的经典教程。但基于 Go 的函数值问题,业界还没有太多深度讨论的内容分享。本文作者根据自己对 Go 代码的使用与调优...【详细内容】
2024-01-15  腾讯云开发者  微信公众号  Tags:Go函数   点击:(88)  评论:(0)  加入收藏
Go编程中调用外部命令的几种场景
在很多场合, 使用Go语言需要调用外部命令来完成一些特定的任务, 例如: 使用Go语言调用Linux命令来获取执行的结果,又或者调用第三方程序执行来完成额外的任务。在go的标准库...【详细内容】
2024-01-09  suntiger    Tags:Go编程   点击:(107)  评论:(0)  加入收藏
Go 语言不支持并发读写 Map,为什么?
Go语言的map类型不支持并发读写的主要原因是并发读写会导致数据竞态(data race),这意味着多个 goroutine 可能同时访问并修改同一个 map,从而引发不确定的结果。在Go语言的设计...【详细内容】
2024-01-05  Go语言圈  微信公众号  Tags:Go 语言   点击:(81)  评论:(0)  加入收藏
Go微服务入门到容器化实践
Go微服务入门到容器化实践Go 是一门高效、现代化、快速增长的编程语言,非常适合构建 Web 应用程序。而 Docker 是一种轻量级的容器化技术,能够使得您的应用程序在任何地方运行...【详细内容】
2024-01-01  大雷家吃饭    Tags:Go微服务   点击:(63)  评论:(0)  加入收藏
你是否想知道如何应对高并发?Go语言为你提供了答案!
并发编程是当前软件领域中不可忽视的一个关键概念。随着CPU等硬件的不断发展,我们都渴望让我们的程序运行速度更快、更快。而Go语言在语言层面天生支持并发,充分利用现代CPU的...【详细内容】
2023-12-29  灵墨AI探索室  微信公众号  Tags:Go语言   点击:(110)  评论:(0)  加入收藏
站内最新
站内热门
站内头条