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

简介: 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

相关文章
|
1天前
|
存储 安全 Java
深入解析Java HashMap的高性能扩容机制与树化优化
深入解析Java HashMap的高性能扩容机制与树化优化
5 1
|
2天前
|
安全 Java 数据安全/隐私保护
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
12 0
|
2天前
|
JSON 安全 Java
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
10 0
|
3天前
|
网络协议 网络架构
RPC原理解析
RPC原理解析
9 0
|
3天前
|
负载均衡 算法 Java
【面试宝藏】Go语言运行时机制面试题
探索Go语言运行时,了解goroutine的轻量级并发及GMP模型,包括G(协程)、M(线程)和P(处理器)。GMP调度涉及Work Stealing和Hand Off机制,实现负载均衡。文章还讨论了从协作到基于信号的抢占式调度,以及GC的三色标记算法和写屏障技术。理解这些概念有助于优化Go程序性能。
20 4
|
4天前
|
JSON Go 数据格式
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】(4)
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】
|
4天前
|
Java 编译器 Go
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】(3)
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】
|
4天前
|
存储 安全 Go
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】(2)
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】
|
4天前
|
Java Go 索引
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】(1)
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】
|
4天前
|
安全 Go 开发者
Go语言中的空值与零值有什么区别?
在Go语言中,`nil`和零值有显著区别。`nil`用于表示指针、通道等类型的“无”或“不存在”,而零值是类型的默认值,如数字的0,字符串的`&#39;&#39;`。`nil`常用于未初始化的变量或错误处理,零值用于提供初始值和避免未初始化的使用。理解两者差异能提升代码质量和稳定性。

推荐镜像

更多