Go 语言切片如何扩容?(全面解析原理和过程)

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: Go 语言切片如何扩容?(全面解析原理和过程)

Go 语言切片如何扩容?(全面解析原理和过程)

一、结构介绍

切片(Slice)在 Go 语言中,有一个很常用的数据结构,切片是一个拥有相同类型元素的可变长度的序列,它是基于数组类型做的一层封装。它非常灵活,支持自动扩容。并发不安全。

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


底层源码定义:

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

1.指针: 指向 slice 可以访问到的第一个元素。

2.长度: slice 中元素个数。

3.容量: slice 起始元素到底层数组最后一个元素间的元素个数。

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


二、扩容时机与过程

Go 中切片的扩容机制是基于动态数组的,这意味着切片的底层数组会动态调整大小以适应元素的增加。下面是 Go 切片扩容的一般过程:

1.初始分配:

当使用 make 创建一个切片时,Go 会为其分配一块初始的底层数组,并将切片的长度和容量都设置为相同的值。

2.追加元素:

当你使用 append 向切片追加元素时,Go 会检查是否有足够的容量来容纳新的元素。如果有足够的容量,新元素会被添加到底层数组的末尾,切片的长度会增加。如果没有足够的容量,就需要进行扩容。

3.扩容:

当切片需要扩容时,Go 会创建一个新的更大的底层数组(具体的扩容策略看下面扩容原理)。然后,原数组的元素会被复制到新数组中,新元素会被添加到新数组的末尾。最后,切片的引用会指向新的底层数组,原数组会被垃圾回收。

这个扩容的过程保证了在大多数情况下,append 操作都是高效的。由于每次扩容都会涉及元素的复制,因此在涉及大量元素的情况下可能会导致一些性能开销。如果你知道切片需要存储的元素数量,可以使用 make 函数make([]T, length, capacity)的第三个参数显式指定容量,以减少扩容的次数。

三、扩容原理

Go1.18之前切片的扩容是以容量1024为临界点,当旧容量 < 1024个元素,扩容变成2倍;当旧容量 > 1024个元素,那么会进入一个循环,每次增加25%直到大于期望容量。

然而这个扩容机制已经被Go 1.18弃用了,官方说新的扩容机制能更平滑地过渡。

具体扩容原理分别如下:

Go 1.18版本 之前扩容原理

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

1. 如果期望容量大于当前容量的两倍就会使用期望容量;

2. 如果当前切片的长度小于 1024 就会将容量翻倍;

3. 如果当前切片的长度大于等于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;


注:解释一下第一条:

比如 nums := []int{1, 2} nums = append(nums, 2, 3, 4),这样期望容量为2+3 = 5,而5 > 2*2,故使用期望容量(这只是不考虑内存对齐的情况下)

记录容量变化如下:

[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

Go 1.18版本 之后扩容原理

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

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


1. 如果期望容量大于当前容量的两倍就会使用期望容量;

2. 如果当前切片的长度小于阈值(默认 256)就会将容量翻倍;

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

记录容量变化如下:

[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

大致规则如下:

其中,当扩容前容量 >= 256时,会按照公式进行扩容

newcap += (newcap + 3*threshold) / 4

这样得到的预估容量并不是最终结果,还有内存对齐,进一步调整newcap

在1.18中,优化了切片扩容的策略,让底层数组大小的增长更加平滑:通过减小阈值并固定增加一个常数,使得优化后的扩容的系数在阈值前后不再会出现从2到1.25的突变,该commit作者给出了几种原始容量下对应的“扩容系数”:

oldcap 扩容系数
256 2.0
512 1.63
1024 1.44
2048 1.35
4096 1.30


可以看到,Go1.18的扩容策略中,随着容量的增大,其扩容系数是越来越小的,可以更好地节省内存。

可以试着求一个极限,当oldcap远大于256的时候,扩容系数将会变成1.25。

四、内存对齐

扩容之后的容量并不是严格按照这个策略的。那是为什么呢?

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

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

举例:

还是上面的例子:

nums := []int{1, 2}
nums = append(nums, 2, 3, 4)
fmt.Printf("len:%v  cap:%v", len(nums), cap(nums))

按照上述策略的结果,应该是 len:5,cap:5。但是最终结果为 len:5,cap:6

解释:容量计算完了后还要考虑到内存的高效利用,进行内存对齐,则会调用这个函数 roundupsize 。(具体可以看源码)

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 {
        return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
        }
    }
    if size+_PageSize < size {
        return size
    }
    return alignUp(size, _PageSize)
}

size 表示新切片需要的内存大小 我们传入的 int 类型,每个占用 8 字节 (可以调用 unsafe.Sizeof() 函数查看占用的大小),一共 5 个 所以是 40,size 小于_MaxSmallSize 并且小于 smallSizeMax-8 ,那么使用通用公式  (size+smallSizeDiv-1)/smallSizeDiv 计算得到 5,然后到 size_to_class8 找到第五号元素 为 4,再从 class_to_size 找到 第四号元素 为 48,这就是新切片占用的内存大小,每个 int 占用 8 字节,所以最终切片的容量为 6 。所以说切片的扩容有它基本的扩容规则,在规则之后还要考虑内存对齐,这就代表不同数据类型的切片扩容的容量大小是会不一致。

五、总结

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

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

一、go1.18 之前:

1.如果期望容量大于当前容量的两倍就会使用期望容量;

2.如果当前切片的长度小于 1024 就会将容量翻倍;

3.如果当前切片的长度大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;

二、go1.18 之后:

1.如果期望容量大于当前容量的两倍就会使用期望容量;

2.如果当前切片的长度小于阈值(默认 256)就会将容量翻倍;

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


总的来说,Go的设计者不断优化切片扩容的机制,其目的只有一个:就是控制让小的切片容量增长速度快一点,减少内存分配次数,而让大切片容量增长率小一点,更好地节省内存。


如果只选择翻倍的扩容策略,那么对于较大的切片来说,现有的方法可以更好的节省内存。

如果只选择每次系数为1.25的扩容策略,那么对于较小的切片来说扩容会很低效。

之所以选择一个小于2的系数,在扩容时被释放的内存块会在下一次扩容时更容易被重新利用。

参考文章:

https://juejin.cn/post/7101928883280150558

https://www.51cto.com/article/750934.html

https://yufengbiji.com/posts/golang-slice

目录
相关文章
|
11天前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
12天前
|
编译器 Go
揭秘 Go 语言中空结构体的强大用法
Go 语言中的空结构体 `struct{}` 不包含任何字段,不占用内存空间。它在实际编程中有多种典型用法:1) 结合 map 实现集合(set)类型;2) 与 channel 搭配用于信号通知;3) 申请超大容量的 Slice 和 Array 以节省内存;4) 作为接口实现时明确表示不关注值。此外,需要注意的是,空结构体作为字段时可能会因内存对齐原因占用额外空间。建议将空结构体放在外层结构体的第一个字段以优化内存使用。
|
12天前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
27 3
|
12天前
|
存储 缓存 安全
Go 语言中的 Sync.Map 详解:并发安全的 Map 实现
`sync.Map` 是 Go 语言中用于并发安全操作的 Map 实现,适用于读多写少的场景。它通过两个底层 Map(`read` 和 `dirty`)实现读写分离,提供高效的读性能。主要方法包括 `Store`、`Load`、`Delete` 等。在大量写入时性能可能下降,需谨慎选择使用场景。
|
13天前
|
SQL 安全 Java
阿里双十一背后的Go语言实践:百万QPS网关的设计与实现
解析阿里核心网关如何利用Go协程池、RingBuffer、零拷贝技术支撑亿级流量。 重点分享: ① 如何用gRPC拦截器实现熔断限流; ② Sync.Map在高并发读写中的取舍。
|
17天前
|
存储 Go
Go 语言入门指南:切片
Golang中的切片(Slice)是基于数组的动态序列,支持变长操作。它由指针、长度和容量三部分组成,底层引用一个连续的数组片段。切片提供灵活的增减元素功能,语法形式为`[]T`,其中T为元素类型。相比固定长度的数组,切片更常用,允许动态调整大小,并且多个切片可以共享同一底层数组。通过内置的`make`函数可创建指定长度和容量的切片。需要注意的是,切片不能直接比较,只能与`nil`比较,且空切片的长度为0。
Go 语言入门指南:切片
|
20天前
|
算法 安全 Go
公司局域网管理系统里的 Go 语言 Bloom Filter 算法,太值得深挖了
本文探讨了如何利用 Go 语言中的 Bloom Filter 算法提升公司局域网管理系统的性能。Bloom Filter 是一种高效的空间节省型数据结构,适用于快速判断元素是否存在于集合中。文中通过具体代码示例展示了如何在 Go 中实现 Bloom Filter,并应用于局域网的 IP 访问控制,显著提高系统响应速度和安全性。随着网络规模扩大和技术进步,持续优化算法和结合其他安全技术将是企业维持网络竞争力的关键。
41 2
公司局域网管理系统里的 Go 语言 Bloom Filter 算法,太值得深挖了
|
16天前
|
开发框架 前端开发 Go
eino — 基于go语言的大模型应用开发框架(二)
本文介绍了如何使用Eino框架实现一个基本的LLM(大语言模型)应用。Eino中的`ChatModel`接口提供了与不同大模型服务(如OpenAI、Ollama等)交互的统一方式,支持生成完整响应、流式响应和绑定工具等功能。`Generate`方法用于生成完整的模型响应,`Stream`方法以流式方式返回结果,`BindTools`方法为模型绑定工具。此外,还介绍了通过`Option`模式配置模型参数及模板功能,支持基于前端和用户自定义的角色及Prompt。目前主要聚焦于`ChatModel`的`Generate`方法,后续将继续深入学习。
128 7
|
26天前
|
监控 Linux PHP
【02】客户端服务端C语言-go语言-web端PHP语言整合内容发布-优雅草网络设备监控系统-2月12日优雅草简化Centos stream8安装zabbix7教程-本搭建教程非docker搭建教程-优雅草solution
【02】客户端服务端C语言-go语言-web端PHP语言整合内容发布-优雅草网络设备监控系统-2月12日优雅草简化Centos stream8安装zabbix7教程-本搭建教程非docker搭建教程-优雅草solution
75 20
|
16天前
|
存储 开发框架 Devops
eino — 基于go语言的大模型应用开发框架(一)
Eino 是一个受开源社区优秀LLM应用开发框架(如LangChain和LlamaIndex)启发的Go语言框架,强调简洁性、可扩展性和可靠性。它提供了易于复用的组件、强大的编排框架、简洁明了的API、最佳实践集合及实用的DevOps工具,支持快速构建和部署LLM应用。Eino不仅兼容多种模型库(如OpenAI、Ollama、Ark),还提供详细的官方文档和活跃的社区支持,便于开发者上手使用。
103 8

热门文章

最新文章

推荐镜像

更多