go slice 扩容实现

基于 Go 1.19。

go 的切片我们都知道可以自动地进行扩容,具体来说就是在切片的容量容纳不下新的元素的时候,
底层会帮我们为切片的底层数组分配更大的内存空间,然后把旧的切片的底层数组指针指向新的内存中:

在这里插入图片描述

目前网上一些关于扩容倍数的文章都是基于相对旧版本的 Go 的,新版本中,现在切片扩容的时候并不是那种准确的小于多少容量的时候就 2 倍扩容,
大于多少容量的时候就 1.25 倍扩容,其实这个数值多少不是非常关键的,我们只需要知道的是:
在容量较小的时候,扩容的因子更大,容量大的时候,扩容的因子相对来说比较小

扩容的示例

我们先通过一个简单的示例来感受一下切片扩容是什么时候发生的:

var slice = []int{1, 2, 3}
fmt.Println(slice, len(slice), cap(slice))

slice = append(slice, 4)
fmt.Println(slice, len(slice), cap(slice))

在这个例子中,slice 切片初始化的时候,长度和容量都是 3(容量不指定的时候默认等于长度)。
因此切片已经容纳不下新的元素了,在我们往 slice 中追加一个新的元素的时候,
我们发现,slice 的长度和容量都变了,
长度增加了 1,而容量变成了原来的 2 倍。

在这里插入图片描述

在 1.18 版本以后,旧的切片容量小于 256 的时候,会进行 2 倍扩容。

实际扩容倍数

其实最新的扩容规则在 1.18 版本中就已经发生改变了,具体可以参考一下这个 commit
runtime: make slice growth formula a bit smoother。

大概意思是:

在之前的版本中:对于 <1024 个元素,增加 2 倍,对于 >=1024 个元素,则增加 1.25 倍。
而现在,使用更平滑的增长因子公式。 在 256 个元素后开始降低增长因子,但要缓慢。

它还给了个表格,写明了不同容量下的增长因子:

starting capgrowth factor
2562.0
5121.63
10241.44
20481.35
40961.30

从这个表格中,我们可以看到,新版本的切片库容,并不是在容量小于 1024 的时候严格按照 2 倍扩容,大于 1024 的时候也不是严格地按照 1.25 倍来扩容。

growslice 实现

在 go 中,切片扩容的实现是 growslice 函数,位于 runtime/slice.go 中。

growslice 有如下参数:

  • oldPtr: 旧的切片的底层数组指针。
  • newLen: 新的切片的长度(= oldLen + num)。
  • oldCap: 旧的切片的容量。
  • num: 添加的元素数。
  • et: 切片的元素类型(也即 element type)。

返回一个新的切片,这个返回的切片中,底层数组指针指向新分配的内存空间,长度等于 oldLen + num,容量就是底层数组的大小。

growslice 实现步骤

  1. 一些特殊情况判断:如 et.size == 0,切片元素不需要占用空间的情况下,直接返回。
  2. 根据 newLen 计算新的容量,保证新的底层数组至少可以容纳 newLen 个元素。
  3. 计算所需要分配的新的容量所需的内存大小。
  4. 分配新的切片底层数组所需要的内存。
  5. 将旧切片上的底层数组的数据复制到新的底层数组中。

注意:这个函数只是实现扩容,新增的元素没有在这个函数往切片中追加。

growslice 源码剖析

说明:

  1. 整数有可能会溢出,所以代码里面会判断 newLen < 0
  2. 如果切片的元素是空结构体或者空数组,那么 et.size == 0
  3. 在计算新切片的容量的时候,会根据切片的元素类型大小来做一些优化。
  4. 新切片容量所占用的内存大小为 capmem
  5. 新切片所需要的内存分配完成后,会将旧切片的数据复制到新切片中。
  6. 最后返回指向新的底层数组的切片,其长度为 newLen,容量为 newcap
// growtslice 为切片分配新的存储空间。
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
	// oldLen 为旧的切片底层数组的长度
	oldLen := newLen - num

	// 分配的新的长度不能小于 0(整数溢出的时候会是负数)
	if newLen < 0 {
		panic(errorString("growslice: len out of range"))
	}

	// 如果结构或数组类型不包含大小大于零的字段(或元素),则其大小为零。
	//(空数组、空结构体,type b [0]int、type zero struct{})
	// 两个不同的零大小变量在内存中可能具有相同的地址。
	if et.size == 0 {
		// append 不应创建具有 nil 指针但长度非零的切片。
		// 在这种情况下,我们假设 append 不需要保留 oldPtr。
		return slice{unsafe.Pointer(&zerobase), newLen, newLen}
	}

	// newcap 是新切片底层数组的容量
	newcap := oldCap
	// 两倍容量
	doublecap := newcap + newcap
	if newLen > doublecap {
		// 如果追加元素之后,新的切片长度比旧切片 2 倍容量还大,
		// 则将新的切片的容量设置为跟长度一样
		newcap = newLen
	} else {
		const threshold = 256
		if oldCap < threshold {
			// 旧的切片容量小于 256 的时候,
			// 进行两倍扩容。
			newcap = doublecap
		} else {
			// oldCap >= 256
			// 检查 0<newcap 以检测溢出并防止无限循环。
			for 0 < newcap && newcap < newLen {
				// 从小切片的增长 2 倍过渡到大切片的增长 1.25 倍。
				newcap += (newcap + 3*threshold) / 4
			}
			// 当 newcap 计算溢出时,将 newcap 设置为请求的上限。
			if newcap <= 0 {
				newcap = newLen
			}
		}
	}

	// 计算实际所需要的内存大小

	// 是否溢出
	var overflow bool
	// lenmem 表示旧的切片长度所需要的内存大小
	//(lenmem 就是将旧切片数据复制到新切片的时候指定需要复制的内存大小)
	// newlenmem 表示新的切片长度所需要的内存大小
	// capmem 表示新的切片容量所需要的内存大小
	var lenmem, newlenmem, capmem uintptr

	// 根据 et.size 做一些计算上的优化:
	// 对于 1,我们不需要任何除法/乘法。
	// 对于 goarch.PtrSize,编译器会将除法/乘法优化为移位一个常数。
	// 对于 2 的幂,使用可变移位。
	switch {
	case et.size == 1: // 比如 []byte,所需内存大小 = size
		lenmem = uintptr(oldLen)
		newlenmem = uintptr(newLen)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == goarch.PtrSize: // 比如 []*int,所需内存大小 = size * ptrSize
		lenmem = uintptr(oldLen) * goarch.PtrSize
		newlenmem = uintptr(newLen) * goarch.PtrSize
		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		newcap = int(capmem / goarch.PtrSize)
	case isPowerOfTwo(et.size): // 比如 []int64,所需内存大小 = size << shift,也就是 size * 2^shift(2^shift 是 et.size)
		var shift uintptr
		if goarch.PtrSize == 8 {
			// Mask shift for better code generation.
			shift = uintptr(sys.TrailingZeros64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.TrailingZeros32(uint32(et.size))) & 31
		}
		lenmem = uintptr(oldLen) << shift
		newlenmem = uintptr(newLen) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
		capmem = uintptr(newcap) << shift
	default: // 没得优化,直接使用乘法了
		lenmem = uintptr(oldLen) * et.size
		newlenmem = uintptr(newLen) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
		capmem = uintptr(newcap) * et.size
	}

	// 检查是否溢出,以及是否超过最大可分配内存
	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: len out of range"))
	}

	// 分配实际所需要的内存
	var p unsafe.Pointer
	if et.ptrdata == 0 { // 不包含指针
		// 分配 capmem 大小的内存,不清零
		p = mallocgc(capmem, nil, false)
		// 这里只清空从 add(p, newlenmem) 开始大小为 capmem-newlenmem 的内存,
		// 也就是前面的 newlenmem 长度不清空。
		// 因为最后的 capmem-newlenmem 这块内存,实际上是额外分配的容量。
		// 前面的那部分会被旧切片的数据以及新追加的数据覆盖。
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// 分配 capmem 大小的内存,需要进行清零
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			// Only shade the pointers in oldPtr since we know the destination slice p
			// only contains nil pointers because it has been cleared during alloc.
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.size+et.ptrdata)
		}
	}
	// 旧切片数据复制到新切片中,复制的内容大小为 lenmem
	//(从 oldPtr 复制到 p)
	memmove(p, oldPtr, lenmem)

	return slice{p, newLen, newcap}
}

总结

go 的切片在容量较小的情况下,确实会进行 2 倍扩容,但是随着容量的增长,扩容的增长因子会逐渐降低。
新版本的 growslice 实现中,只有容量小于 256 的时候才会进行 2 倍扩容,
然后随着容量的增长,扩容的因子会逐渐降低(但并不是直接降到 1.25,而是一个相对缓慢的下降)。

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

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

相关文章

【DDD】学习笔记-软件开发团队的沟通与协作

领域驱动设计的核心是“领域”&#xff0c;因此要运用领域驱动设计&#xff0c;从一开始就要让团队走到正确的点儿上。当我们组建好了团队之后&#xff0c;应该从哪里开始&#xff1f;不是 UI 原型设计、不是架构设计、也不是设计数据库&#xff0c;这些事情虽然重要但却非最高…

Linux常见的管理命令

1. whoami 作用&#xff1a; 显示出当前有效的用户名称&#xff0c;Linux是多用户多任务 语法&#xff1a;whoami(选项) 选项&#xff1a; --help&#xff1a;在线帮助 --version&#xff1a;显示版本信息和退出 场景使用&#xff1a; 1. 当用户想要查看当前登录系统的用户…

时间数据前端显示格式化

背景 在实际我们通常需要在前端显示对数据操作的时间或者最近的更新时间&#xff0c;如果我们只是简单的使用 LocalDateTime.now()来传入数据不进行任何处理那么我们就会得到非常难看的数据 解决方式&#xff1a; 1). 方式一 在属性上加上注解&#xff0c;对日期进行格式…

【Py/Java/C++三种语言详解】LeetCode每日一题240122【贪心】LeetCode670、最大交换

文章目录 题目链接题目描述解题思路为什么是贪心一个带图的例子 代码pythonjavacpp时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目链接 LeetCode670、最大交换 题目描述 给定一个非负整数数组 nums 和一个整数 k &#xff0c;你需要将这个数组分成 k 个非空的连…

深入浅出 diffusion(4):pytorch 实现简单 diffusion

1. 训练和采样流程 2. 无条件实现 import torch, time, os import numpy as np import torch.nn as nn import torch.optim as optim from torchvision.datasets import MNIST from torchvision import transforms from torch.utils.data import DataLoader from torchvision.…

智能分析网关V4智慧冶金工厂视频智能监管方案

一、背景与需求 随着工业4.0的推进&#xff0c;冶金行业正面临着转型升级的压力。为了提高生产效率、降低能耗、保障安全&#xff0c;冶金智能工厂视频监管方案应运而生。该方案通过高清摄像头、智能分析技术、大数据处理等手段&#xff0c;对工厂进行全方位、实时监控&#xf…

matlab appdesigner系列-图窗工具2-工具栏

工具栏&#xff0c;就是一般在任意软件界面上方的工具菜单栏 示例&#xff1a;工具菜单绘制正弦函数 操作步骤如下&#xff1a; 1&#xff09;将坐标区和工具栏拖拽到画布上 2)点击工具栏的号&#xff0c;可以看到可以添加2种工具&#xff0c;按钮工具和切换工具&#xff0c…

Unity 代理模式(实例详解)

文章目录 实例1&#xff1a;资源加载代理&#xff08;Asset Loading Proxy&#xff09;实例2&#xff1a;网络请求代理&#xff08;Network Request Proxy&#xff09;实例3&#xff1a;性能优化代理&#xff08;Performance Optimization Proxy&#xff09;实例4&#xff1a;权…

LC 2846. 边权重均等查询

2846. 边权重均等查询 难度&#xff1a; 困难 题目大意&#xff1a; 现有一棵由 n 个节点组成的无向树&#xff0c;节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges &#xff0c;其中 edges[i] [ui, vi, wi] 表示树中存在一条位于节点 …

银行数据仓库体系实践(11)--数据仓库开发管理系统及开发流程

数据仓库管理着整个银行或公司的数据&#xff0c;数据结构复杂&#xff0c;数据量庞大&#xff0c;任何一个数据字段的变化或错误都会引起数据错误&#xff0c;影响数据应用&#xff0c;同时业务的发展也带来系统不断升级&#xff0c;数据需求的不断增加&#xff0c;数据仓库需…

EventSource 长链接执行

EventSource 说明文档MDN 其他参考文档 一、利用node启服务 import fs from fs import express from express const app express() // eventSource 仅支持 get 方法 // 服务器端发送的数据必须是纯文本格式&#xff0c;不能是二进制数据。 app.get(/api, (req, res) > …

项目性能优化之用compression-webpack-plugin插件开启gzip压缩

背景&#xff1a;vue项目打包发布后&#xff0c;部分js、css文件体积较大导致页面卡顿&#xff0c;于是使用webpack插件compression-webpack-plugin开启gzip压缩 前端配置vue.config.js 先通过npm下载compression-webpack-plugin包&#xff0c;npm i compression-webpack-plug…

Android SharedPreferences源码分析

文章目录 Android SharedPreferences源码分析概述基本使用源码分析获取SP对象初始化和读取数据写入数据MemoryCommitResultcommitToMemory()commit()apply()enqueueDiskWrite()writeToFile() 主动等待写回任务结束 总结 Android SharedPreferences源码分析 概述 SharedPrefer…

EXCEL VBA抓取网页JSON数据并解析

EXCEL VBA抓取网页JSON数据并解析 链接地址&#xff1a; https://api.api68.com/CQShiCai/getBaseCQShiCaiList.do?lotCode10036&date2024-01-26 Sub test() On Error Resume Next Sheet.Select Sheet1.Cells.ClearContents [a1:g1] Split("preDrawIssue|preDrawTi…

Ubuntu20.04添加桌面启动、侧边栏启动和终端启动

桌面启动 新建XX.desktop文件 在桌面新建一个XX.desktop文件&#xff0c;以QtCreator为例。 &#xff08;注意这里不能使用sudo&#xff0c;因为这样会把文件的权限归为root&#xff0c;导致后续设置可执行程序不方便&#xff09; gedit qtcreator.desktop在XX.desktop文件中…

第14次修改了可删除可持久保存的前端html备忘录:增加一个翻牌钟,修改背景主题:现代深色

第14次修改了可删除可持久保存的前端html备忘录&#xff1a;增加一个翻牌钟&#xff0c;修改背景主题&#xff1a;现代深色 备忘录代码 <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta http-equiv"X…

设计模式—行为型模式之责任链模式

设计模式—行为型模式之责任链模式 责任链&#xff08;Chain of Responsibility&#xff09;模式&#xff1a;为了避免请求发送者与多个请求处理者耦合在一起&#xff0c;于是将所有请求的处理者通过前一对象记住其下一个对象的引用而连成一条链&#xff1b;当有请求发生时&am…

Flink面试题

0. 思维导图 1. 简单介绍一下Flink♥♥ Flink是一个分布式的计算框架&#xff0c;主要用于对有界和无界数据流进行有状态计算&#xff0c;其中有界数据流就是值离线数据&#xff0c;有明确的开始和结束时间&#xff0c;无界数据流就是指实时数据&#xff0c;源源不断没有界限&a…

ES文档索引、查询、分片、文档评分和分析器技术原理

技术原理 索引文档 索引文档分为单个文档和多个文档。 单个文档 新建单个文档所需要的步骤顺序&#xff1a; 客户端向 Node 1 发送新建、索引或者删除请求。节点使用文档的 _id 确定文档属于分片 0 。请求会被转发到 Node 3&#xff0c;因为分片 0 的主分片目前被分配在 …

Android源码设计模式解析与实战第2版笔记(二)

第二章 应用最广的模式 — 单例模式 单例模式的定义 确保某一个类只有一个实例&#xff0c;而且自行实例化并向整个系统提供这个实例。 单例模式的使用场景 确保某个类有且只有一个对象的场景&#xff0c;避免产生多个对象消耗过多的资源&#xff0c;或者某种类型的对象只应…