Go的slice扩容不是全部都按照1.25扩容的,还有内存对齐的概念,别再被忽悠了

简介: Go的slice扩容不是全部都按照1.25扩容的,还有内存对齐的概念,别再被忽悠了

Go的slice扩容机制



扩容


说实话,我看到别的文章中说slice的扩容很简单,小于1024,按照两倍去扩容;大于等于1024,按照1.25去扩容;像这样不负责任的文章误导初学者使我非常不爽,今天就给大家带来源码级别的slice扩容机制,别怕,一切都是那么简单。


1. 先看一个例子(<1024)


package main
import "fmt"
func main() {
 s1 := make([]int, 1023)
 s2 := make([]int, 1)
 s1 = append(s1, s2...)
 fmt.Println(cap(s1), len(s1))
}
输出结果是:
2048 1024
从结果可以看出,小于1024的确实按照2倍去扩容的,我们不妨计作:
f(x) = 2x (x<1024)


大家知道为什么是1024吗?有人问过go作者,说为啥不是2048啊之类的,你猜作者怎么回答,非常简单的一句话:因为在计算机世界中1024这个数字很特别,它就是一个数字,是一个以2为底,10为指数的数,就这样简单。所以有时候大家看源码别纠结细节,一旦陷入就要请求旁边的高人将自己解救出来呀。


2. 再看一个例子(>=1024)


package main
import "fmt"
func main() {
 s1 := make([]int, 1024)
 s2 := make([]int, 258)
 s1 = append(s1, s2...)
 fmt.Println(cap(s1), len(s1))
}
输出结果是:
1696 1282
从结果可以看出,大于等于1024,不是按照1.25(1+1/4)的倍速增长的,所以:
f(x) = x + x/4 (x>=1024)就突然不成立了,这到底是为什么?是不是想要一探究尽呢?接下来剖析源码就知道啦。


3. 两个函数


f(x) = 2x (x<1024)
f(x) = x + x/4 (x >= 1024)


确认:函数1成立,函数2在有些条件下成立 嗯?为什么在有些条件下成立呢?再看一个例子:


package main
import "fmt"
func main() {
 s1 := make([]int, 1024)
 s2 := make([]int, 1)
 s1 = append(s1, s2...)
 fmt.Println(cap(s1), len(s1))
}
输出结果是:
1280 1025

我们可以带函数2去计算下:f(1024) = 1024 + 1024/4 = 1024 + 256 = 1280你看这样的就可以满足函数2了,接下来分析下上面不满足函数2的例子。


4. 源码剖析不满足1.25增速的原因


在源码中主要是看growslice这个函数。


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 { //小于1024 double就可以
   newcap = doublecap
  } else {
   for 0 < newcap && newcap < cap { // 容量比之前大,那么按照1.25的倍速增长
    newcap += newcap / 4
   }
  }
 }
 ... //省略部分代码
 var lenmem, newlenmem, capmem uintptr
 switch {
 ... //省略
 case et.size == sys.PtrSize:
  lenmem = uintptr(old.len) * sys.PtrSize
  newlenmem = uintptr(cap) * sys.PtrSize
  // 看这里 核心函数roundupsize 按照内存字节对齐
  capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
  overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
  newcap = int(capmem / sys.PtrSize) //1696
 ...//省略部分代码
 }
}


好了按照代码流程先走一遍:

  1. 首先我们的长度是大于等于1024的,那么按照上面逻辑先计算得出:f(1024)=1280,发现其实空间还不够,那么继续扩容f(1280)=1280+1280/4=1600
  2. 紧接着进入switch case中,这里的sys.PtrSize=8,而我们的et.size因为是int存储所以也是8,刚好命中这个case,进入。
  3. 然后计算新元素capmem=roundupsize(uintptr(newcap) * sys.PtrSize),则capmem=roundupsize(1600*8)=roundupsize(12800)。
  4. roundupsize函数中size=12800<_MaxSmallSize(32768),并且size<=smallSizeMax(1024)-8不满足,所以最终进入else代码段。
func roundupsize(size uintptr) uintptr {
 if size < _MaxSmallSize {
  if size <= smallSizeMax-8 {
   return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
  } else {
   // 进入到这里
   return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
  }
 }
 if size+_PageSize < size {
  return size
 }
 return alignUp(size, _PageSize)
}
// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
 // a is generally a power of two. This will get inlined and
 // the compiler will optimize the division.
 return (n + a - 1) / a
}
  1. 看下class_to_size和size_to_class128
const (
 _MaxSmallSize   = 32768
 smallSizeDiv    = 8
 smallSizeMax    = 1024
 largeSizeDiv    = 128
 _NumSizeClasses = 67
 _PageShift      = 13
)
var class_to_size = [_NumSizeClasses]uint16{
0, 8, 16, 24, 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}
var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{
32, 33, 34, 35, 36, 37, 37, 38, 38, 
39, 39, 40, 40, 40, 41, 41, 41, 42, 
43, 43, 44, 44, 44, 44, 44, 45, 45, 
45, 45, 45, 45, 46, 46, 46, 46, 47, 
47, 47, 47, 47, 47, 48, 48, 48, 49, 
49, 50, 51, 51, 51, 51, 51, 51, 51, 
51, 51, 51, 52, 52, 52, 52, 52, 52, 
52, 52, 52, 52, 53, 53, 54, 54, 54, 
54, 55, 55, 55, 55, 55, 56, 56, 56, 
56, 56, 56, 56, 56, 56, 56, 56, 57, 
57, 57, 57, 57, 57, 57, 57, 57, 57, 
58, 58, 58, 58, 58, 58, 59, 59, 59, 
59, 59, 59, 59, 59, 59, 59, 59, 59, 
59, 59, 59, 59, 60, 60, 60, 60, 60, 
60, 60, 60, 60, 60, 60, 60, 60, 60, 
60, 60, 61, 61, 61, 61, 61, 62, 62, 
62, 62, 62, 62, 62, 62, 62, 62, 62, 
63, 63, 63, 63, 63, 63, 63, 63, 63, 
63, 64, 64, 64, 64, 64, 64, 64, 64, 
64, 64, 64, 64, 64, 64, 64, 64, 64, 
64, 64, 64, 64, 64, 65, 65, 65, 65, 
65, 65, 65, 65, 65, 65, 65, 65, 65, 
65, 65, 65, 65, 65, 65, 65, 65, 66, 
66, 66, 66, 66, 66, 66, 66, 66, 66, 
66, 67, 67, 67, 67, 67, 67, 67, 67, 
67, 67, 67, 67, 67, 67, 67, 67, 67, 
67, 67, 67, 67, 67, 67, 67, 67, 67, 
67, 67, 67, 67, 67, 67}
  1. 通过函数divRoundUp(size-smallSizeMax, largeSizeDiv)计算出:divRoundUp(12800-1024, 128) = divRoundUp(12800-1024, 128) = (12800-1024+128-1) / 128 = 11903/128=92
  2. 我们根据92在size_to_class128中找到是57,然后在class_to_size中根据索引57找到是13568。
  3. 所以roundupsize函数返回13568,而newcap = int(capmem / sys.PtrSize) = 13568/8 = 1696,至此我们就求出来cap的最终容量是1696啦。
  4. 注意我的go源码版本是go1.16.7


5. 小结


看完源码之后心情舒爽,我相信大家肯定会更自信了,不管同事问你还是面试官问你,你可以自豪的给他从源码角度分析了,而且别人一听就能判断出你是读过源码的,求知欲满满!

如果你觉得这篇文章对你帮助很大,请你转发、分享、关注、点赞哦,写作不易,还望大家多多支持哈。



相关文章
|
7天前
|
存储 安全 Java
Java面试题:深入探索Java内存模型,Java内存模型中的主内存与工作内存的概念,Java内存模型中的happens-before关系,volatile关键字在Java内存模型中的作用
Java面试题:深入探索Java内存模型,Java内存模型中的主内存与工作内存的概念,Java内存模型中的happens-before关系,volatile关键字在Java内存模型中的作用
12 1
|
11天前
|
缓存 编译器 Shell
回顾go语言基础中一些特别的概念
【7月更文挑战第6天】本文介绍Go语言基础涵盖包声明、导入、函数、变量、语句和表达式以及注释。零值可用类型如切片、互斥锁和缓冲,支持预分配容量以优化性能。
42 2
回顾go语言基础中一些特别的概念
|
26天前
|
Java Go
Go 中 slice 的内存管理机制
Go 中 slice 的内存管理机制
|
26天前
|
Go
Go 语言是如何实现切片扩容
Go 语言是如何实现切片扩容
|
1月前
|
运维 Serverless Nacos
Serverless 应用引擎产品使用合集之在访问量过大的情况下,函数配置的cpu和内存会自动扩容吗
阿里云Serverless 应用引擎(SAE)提供了完整的微服务应用生命周期管理能力,包括应用部署、服务治理、开发运维、资源管理等功能,并通过扩展功能支持多环境管理、API Gateway、事件驱动等高级应用场景,帮助企业快速构建、部署、运维和扩展微服务架构,实现Serverless化的应用部署与运维模式。以下是对SAE产品使用合集的概述,包括应用管理、服务治理、开发运维、资源管理等方面。
|
2月前
|
Go 索引
Go 语言切片(Slice)
Go 语言切片(Slice)
19 1
|
2月前
|
存储 Java Go
Go 语言切片如何扩容?(全面解析原理和过程)
Go 语言切片如何扩容?(全面解析原理和过程)
52 2
|
2月前
|
存储 缓存 Java
简单介绍一下什么是“工作内存”和“主内存”(JMM中的概念)
该文介绍了Java多线程中`volatile`关键字确保内存可见性的概念。
29 0
|
2月前
|
存储
【进程概念】虚拟内存与页表简述
【进程概念】虚拟内存与页表简述
|
2月前
|
Go 数据处理
Go杂记1-切片Slice作为函数参数那点事儿
Go杂记1-切片Slice作为函数参数那点事儿
24 0