深入理解 Go slice 扩容机制

前言

go 的切片可以自动地进行扩容,当调用append方法时,如果len == cap,即容纳不下新的元素的时, 底层会帮我们为切片的底层数组分配更大的内存空间,然后把旧的切片的底层数组指针指向新的内存中

  • 注意不是根据底层数据的容量来判断是否扩容,而是根据slice的属性cap,cap可能比数组实际容量小

分配更大的内存时预留的一定的buffer

  • 如果不预留,只考虑当前新增的元素,则每次append时都会发生数据拷贝,成本太高

于是slice扩容的重点就在于,预留多少buffer?

1.18以前

直接看源码:

源码位置:/src/runtime/slice.go growslice

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
         }
         if newcap <= 0 {
            newcap = cap
         }
      }
   }
   
   // ...
   
   capmem = roundupsize(uintptr(newcap))

新容量的计算规则如下:

  • 需要的容量比2倍老容量大:使用需要的容量

    • 一般发生于append一个较大的slice时,例如 append(s, s1...)
  • 如果老容量小于1024,按照2倍扩容

  • 如果老容量大于等于1024,按照1.25倍扩容,对应源码newcap += newcap / 4

  • 如果newcap溢出了int最大值,不扩容

最后再按照内存分配块的大小,向上修正

内存分配各个size如下:{0, 8, 16, 24, 32, 48, 64, 80, 96, 112...}

例如,如果slice为int类型,有5个元素,应该占40个字节,但由于分配到size=48的内存块,会向上修正到48字节,也就是cap变为6

func main() {
   s := []int{}
   s = append(s, []int{1, 2, 3, 4, 5}...)
   fmt.Println(cap(s))  // 结果为6
}

这个扩容规则有什么问题?

  1. 不够平滑:容量小于1024时2倍扩容,大于1024突然降到1.25倍扩容

  2. 容量增长不单调,正常应该是较大的初始容量扩容后有较大的最终容量

    1. 例如以下代码:
x1 := make([]int, 897)
x2 := make([]int, 1024)
y := make([]int, 100)
println(cap(append(x1, y...))) // 2048
println(cap(append(x2, y...))) // 1280

x1的容量比x2小,都增加100个元素后x1的容量反而比x2大

1.18以后

go在这次提交中 runtime: make slice growth formula a bit smoother修改了扩容规则:

其用一个更平滑的公式来计算扩容因子,在256个元素之前还是2倍扩容因子,在256个元素后逐步减少,不同容量下的扩容因子如下:

starting capgrowth factor
2562.0
5121.63
10241.44
20481.35
40961.30

改版后代码如下:

// ...
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
   newcap = cap
} else {
   const threshold = 256
   if old.cap < threshold {
      newcap = doublecap
   } else {
      for 0 < newcap && newcap < cap {
         newcap += (newcap + 3*threshold) / 4
      }
      if newcap <= 0 {
         newcap = cap
      }
   }
}
// ...

在容量256以后,预留的buffer容量为 1/4原容量,加上了 3/4 * 256

这样当old.cap为256时还是2倍扩容,随着容量增大3/4 * 256占原容量的比例逐渐降低最终收敛于0,达到平滑扩容的效果

总结

  • 1.18以前:

    • 容量小于1024时为2倍扩容,大于等于1024时为1.25倍扩容
  • 1.18以后:

    • 小于256时为2倍扩容,大于等于256时的扩容因子逐渐从2减低为1.25
  • 不管1.18前后,最终需要按照内存分配块向上修正

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/1273.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AD域安全攻防实践(附攻防矩阵图)

以域控为基础架构&#xff0c;通过域控实现对用户和计算机资源的统一管理&#xff0c;带来便利的同时也成为了最受攻击者重点攻击的集权系统。 01、攻击篇 针对域控的攻击技术&#xff0c;在Windows通用攻击技术的基础上自成一套技术体系&#xff0c;将AD域攻防分为信息收集、权…

安装Docker

Docker分为CE和EE两大版本。CE即社区版&#xff08;免费&#xff0c;支持周期7个月&#xff09;&#xff0c;EE即企业版&#xff0c;强调安全&#xff0c;付费使用&#xff0c;支持周期 24 个月。 Docker CE 分为 stable test 和 nightly 三个更新频道。 官方网站上有各种环境…

Nacos 注册中心 - 健康检查机制源码

目录 1. 健康检查介绍 2. 客户端健康检查 2.1 临时实例的健康检查 2.2 永久实例的健康检查 3. 服务端健康检查 3.1 临时实例的健康检查 3.2 永久实例服务端健康检查 1. 健康检查介绍 当一个服务实例注册到 Nacos 中后&#xff0c;其他服务就可以从 Nacos 中查询出该服务…

LeetCode234_234. 回文链表

LeetCode234_234. 回文链表 一、描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&…

Day920.结构化日志业务审计日志 -SpringBoot与K8s云原生微服务实践

结构化日志&业务审计日志 Hi&#xff0c;我是阿昌&#xff0c;今天学习记录的是关于结构化日志&业务审计日志的内容。 1、什么是结构化日志 结构化日志&#xff08;Structured Logging&#xff09;是一种将日志信息组织为结构化数据的技术。 传统的日志通常是一些文…

UE实现建筑分层抽屉展示效果

文章目录 1.实现目标2.实现过程2.1 基础设置2.2 核心函数3.参考资料1.实现目标 使用时间轴对建筑楼层的位置偏移进行控制,实现分层抽屉的动画展示效果。 2.实现过程 建筑抽屉的实现原理比较简单,即对Actor的位置进行偏移,计算并更新其世界位置即可。这里还是基于ArchVizExp…

Mybatis报BindingException:Invalid bound statement (not found)异常

一、前言 本文的mybatis是与springboot整合时出现的异常&#xff0c;若使用的不是基于springboot&#xff0c;解决思路也大体一样的。 二、从整合mybatis的三个步骤排查问题 但在这之前&#xff0c;我们先要知道整合mybatis的三个重要的工作&#xff0c;如此才能排查&#x…

SDG,ADAM,LookAhead,Lion等优化器的对比介绍

本文将介绍了最先进的深度学习优化方法&#xff0c;帮助神经网络训练得更快&#xff0c;表现得更好。有很多个不同形式的优化器&#xff0c;这里我们只找最基础、最常用、最有效和最新的来介绍。 优化器 首先&#xff0c;让我们定义优化。当我们训练我们的模型以使其表现更好…

MySQL中事务的相关问题

事务 一、事务的概述&#xff1a; 1、事务处理&#xff08;事务操作&#xff09;&#xff1a;保证所有事务都作为一个工作单元来执行&#xff0c;即使出现了故障&#xff0c;都不能改变这种执行方式。当在一个事务中执行多个操作时&#xff0c;要么所有的事务都被提交(commit…

[ROC-RK3568-PC] [Firefly-Android] 10min带你了解Camera的使用

&#x1f347; 博主主页&#xff1a; 【Systemcall小酒屋】&#x1f347; 博主追寻&#xff1a;热衷于用简单的案例讲述复杂的技术&#xff0c;“假传万卷书&#xff0c;真传一案例”&#xff0c;这是林群院士说过的一句话&#xff0c;另外“成就是最好的老师”&#xff0c;技术…

再也不想去字节跳动面试了,6年测开面试遭到这样打击.....

前几天我朋友跟我吐苦水&#xff0c;这波面试又把他打击到了&#xff0c;做了快6年软件测试员。。。为了进大厂&#xff0c;也花了很多时间和精力在面试准备上&#xff0c;也刷了很多题。但题刷多了之后有点怀疑人生&#xff0c;不知道刷的这些题在之后的工作中能不能用到&…

【Python/Opencv】图像权重加法函数:cv2.addWeighted()详解

【Python/Opencv】图像权重加法函数&#xff1a;cv2.addWeighted()详解 文章目录【Python/Opencv】图像权重加法函数&#xff1a;cv2.addWeighted()详解1. 介绍2. API3. 代码示例与效果3.1 代码3.2 效果4. 参考1. 介绍 在OpenCV图像加法cv2.add函数详解详细介绍了图像的加法运…

字符串匹配【BF、KMP算法】

文章目录:star:BF算法代码实现BF的改进思路:star:KMP算法&#x1f6a9;next数组&#x1f6a9;代码实现优化next数组最终代码⭐️BF算法 BF算法&#xff0c;即暴力(Brute Force)算法&#xff0c;是普通的模式匹配算法&#xff0c;BF算法的思想就是将主串S的第一个字符与模式串P…

三、Python 操作 MongoDB ----非 ODM

文章目录一、连接器的安装和配置二、新增文档三、查询文档四、更新文档五、删除文档一、连接器的安装和配置 pymongo&#xff1a; MongoDB 官方提供的 Python 工具包。官方文档&#xff1a; https://pymongo.readthedocs.io/en/stable/ pip安装&#xff0c;命令如下&#xff1…

JVM调优,调的是什么?目的是什么?

文章目录前言一、jvm是如何运行代码的&#xff1f;二、jvm的内存模型1 整体内存模型结构图2 堆中的年代区域划分3 对象在内存模型中是如何流转的?4 什么是FULL GC,STW? 为什么会发生FULL GC?5 要调优,首先要知道有哪些垃圾收集器及哪些算法6 调优不是盲目的,要有依据,几款内…

HttpRunner3.x(1)-框架介绍

HttpRunner 是一款面向 HTTP(S) 协议的通用测试框架&#xff0c;只需编写维护一份 YAML/JSON 脚本&#xff0c;即可实现自动化测试、性能测试、线上监控、持续集成等多种测试需求。主要特征继承的所有强大功能requests &#xff0c;只需以人工方式获得乐趣即可处理HTTP&#xf…

【每日反刍】——指针运算

&#x1f30f;博客主页&#xff1a;PH_modest的博客主页 &#x1f6a9;当前专栏&#xff1a;每日反刍 &#x1f48c;其他专栏&#xff1a; &#x1f534; 每日一题 &#x1f7e2; 读书笔记 &#x1f7e1; C语言跬步积累 &#x1f308;座右铭&#xff1a;广积粮&#xff0c;缓称…

【Java进阶篇】—— File类与IO流

一、File类的使用 1.1 概述 File 类以及本章中的各种流都定义在 java.io 包下 一个File对象代表硬盘或网络中可能存在的一个文件或文件夹&#xff08;文件目录&#xff09; File 能新建、删除、重命名 文件和目录&#xff0c;但 File不能访问文件内容本身。如果我们想要访问…

【LeetCode】二叉树基础练习 5 道题

第一题&#xff1a;单值二叉树 题目介绍&#xff1a; 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时&#xff0c;才返回true&#xff1b;否则返回false。 //题目框架 bool isUnivalTree(struct TreeNode* root){ }…

【24】Verilog进阶 - 序列检测2

VL35 状态机-非重叠的序列检测 1 思路 状态机嘛,也是比较熟悉的朋友啦, 我就火速写出了STG。如下黑色所示: 2 初版代码 `timescale 1ns/1nsmodule sequence_test1(input wire clk ,input wire rst ,input wire data ,output reg flag ); //*************code**********…
最新文章