Golang 泛型实现原理
文章目录
- 1.什么是泛型?
- 2.有 interface{} 为什么还要有泛型?
- 3.泛型有哪些特性?
- 3.1 类型参数
- 泛型函数
- 泛型类型
- 3.2 类型约束
- 3.3 类型集
- 3.4 约束元素
- 任意类型约束元素
- 近似约束元素
- 联合约束元素
- 约束中的可比类型
- 3.5 类型推断
- 4.实现原理
- 4.1 类型擦除
- 虚方法表
- 4.2 字典
- 4.3 单态化
- 模板(Template)
- 蜡印(Stenciling)
- 5.小结
- 参考wenxian
泛型(Generics)是 Go 语言在较早版本缺失的一个特性,直到 Go 1.18 版本中才引入了泛型。泛型提供了一种更灵活、更通用的方式来编写函数和数据结构,以处理不同类型的数据,而不必针对每种类型编写重复的代码。
1.什么是泛型?
假设我们有一个实现两个数相加的功能函数:
func Add(a int, b int) int {return a + b
}
通过传入 int 类型的 a 和 b,就可以返回 a 和 b 相加后的结果。如果 a 和 b 是 float 类型呢?
如果要解决上述问题,通常有两种解决方法:
(1)增加一个函数。
func AddFloat(a, b float32) float32 {return a + b
}
(2)利用反射,运行时进行类型判断。
func Add(a interface{}, b interface{}) interface{} {switch a.(type) {case int:return a.(int) + b.(int)case float32:return a.(float32) + b.(float32)default:return nil}
}
这两个方法有什么缺点吗?
方法1:会引入新的函数,如果还有其他类型的a,b需要相加的话,就需要再增加更多的函数。
方法2:使用了反射,性能会有影响。
如果不想增加一个新的功能逻辑一模一样的函数,同时也不想使用有性能问题的反射的话。就可以使用泛型。
func Add[T int | float32 | float64](a, b T) T {return a + b
}
泛型是一种编程范式,允许程序员在强类型程序设计语言中编写模板代码来适应任意类型。
通俗一点的描述,泛型是一种相同代码逻辑使用不同类型用的方法,而不需要一遍又一遍地复制和粘贴相同的函数,只是类型发生了变化。
2.有 interface{} 为什么还要有泛型?
虽然 Go 中的空接口 interface{} 允许存储任何类型的值,但它是一种动态类型的机制,并且在使用时需要进行类型断言。相比之下,泛型(Generics)提供了一种静态类型的通用解决方案,使得代码可以在不失去类型安全性的前提下处理多种数据类型。
使用泛型可以带来如下好处:
- 类型安全
泛型允许开发者在编译时指定代码的通用类型,为类型参数定义一个类型约束,而不需要使用空接口进行运行时类型断言。这提供了更强的类型安全性,因为在编译时就能够发现类型错误。
- 性能优化
在某些情况下,使用泛型可以带来性能优势。由于泛型代码是在编译时生成的,而不是在运行时进行类型断言,因此它可以更好地进行优化。
- 代码重用和抽象
泛型允许编写通用的、与具体数据类型无关的代码,从而提高代码的重用性和抽象性。不再需要为每种数据类型都编写相似的代码,避免违反 DRY 原则(Don’t Repeat Yourself)。
3.泛型有哪些特性?
Go 语言泛型实现采用了一种基于类型参数的方式实现更加通用和类型安全的代码,而不是通过接口(像空接口 interface{})和类型断言来实现动态类型的处理。
以下是 Go 泛型实现的基本特性:
3.1 类型参数
Go 的泛型使用类型参数来实现通用性。在定义函数、类型或方法时,可以声明一个或多个类型参数。这些类型参数允许你在代码中引用并操作不同数据类型的对象。
泛型函数
泛型函数允许你编写能够处理不同类型的数据的通用函数,而不必为每种类型编写重复的代码。例如,可以创建一个泛型的排序函数,适用于不同类型的切片。
func Swap[T any](a, b T) (T, T) {return b, a
}
在上面的例子中,T 是一个类型参数,它表示一个占位符,可以代表任意类型。在函数体内,可以使用 T 来表示参数和返回值的类型。
泛型类型
泛型也可以用于创建通用的类型,如泛型切片、泛型映射等。这样可以更灵活地处理不同类型的数据。
type Stack[T any] struct {items []T
}func (s *Stack[T]) Push(item T) {s.items = append(s.items, item)
}func (s *Stack[T]) Pop() T {if len(s.items) == 0 {panic("Stack is empty")}item := s.items[len(s.items)-1]s.items = s.items[:len(s.items)-1]return item
}
上述例子中,Stack 是一个泛型的堆栈数据结构,可以处理任意类型的元素。
3.2 类型约束
为了确保类型安全性,Go 引入了类型约束(type constraints)。
类型约束规定了类型参数必须满足的条件,以便进行合法的操作。例如,可以使用 interface{} 类型进行类型约束,也可以使用特定的接口类型或基本类型。
func Print[T fmt.Stringer](value T) {fmt.Println(value.String())
}
在上述例子中,T 被约束为实现了 fmt.Stringer 接口的类型。
3.3 类型集
类型集(Type Set)表示一堆类型的集合,用来在泛型中约束类型参数的范围。
在 Go1.18 之前,Go 官方对接口的定义是:接口是一个方法集(Method Set)。而 Go1.18 开始将接口的定义正式更改为了类型集。
Go 1.18 引入了一种新的接口语法,可以嵌入其他数据类型,构成类型集合。
type Numeric interface {int | float32 | float64
}
这意味着一个接口不仅可以定义一组方法,还可以定义一组类型。使用 Numeric 接口作为类型约束,意味着值可以是整数或浮点数。
type Node[T Numeric] struct {value T
}
3.4 约束元素
任意类型约束元素
在类型集合中,任意类型均可作为类型参数的约束元素。
// 其中 int 为基础类型
type Integer interface { int }
近似约束元素
实际编码时,可能会有很多的类型别名,例如:
type (orderStatus int32sendStatus int32receiveStatus int32...
)
Go1.18 中扩展了近似约束元素(Approximation Constraint Element)这个概念,以上述例子来说,即:基础类型为 int32 的类型。语法表现为:
type AnyStatus interface{ ~int32 }
如果我们需要对上述自定义的 status 做一个翻译,就可以使用以下方式:
// 使用定义的类型集
func translateStatus[T AnyStatus](status T) string {switch status {case 1:return "成功"case -1:return "失败"default:return "未知"}
}// 或者不使用类型集
func translateStatus[T ~int32](status T) string {switch status {case 1:return "成功"case -1:return "失败"default:return "未知"}
}
联合约束元素
联合元素,写成一系列由竖线 (|) 分隔的约束元素。
这里给所有有符号的整数类型添加一个通用的求和方法。
type Integer interface {~int | ~int8 | ~int16 | ~int32 | ~int64
}func addInteger[T Integer](a, b T) T {return a + b
}
约束中的可比类型
Go1.18 中内置了一个类型约束 comparable约束,comparable约束的类型集是所有可比较类型的集合。这允许你对该类型的值进行比较操作。
func indexSlice[T comparable](s []T, x T) int {for i, v := range s {if v == x {return i}}return -1
}
3.5 类型推断
在许多情况下,可以使用类型推断来避免必须显式写出部分或全部类型参数。可以利用函数调用使用的实参类型推断出类型参数。
func Print[T any](s T) {fmt.Println(s)
}s := []int{1, 2, 3}// 显示指定参数类型
Print[[]int](s)
// 推断参数类型
Print(s)
4.实现原理
要了解 Go 是如何实现泛型的,首先需要了解一下实现泛型的最常用方法。
4.1 类型擦除
在编译器中实现泛型的另一种方法是类型擦除(Type erasure)。
对 Java 来说统一的数据类型就是 Object,在编译阶段做完类型检查后就将类型信息通过转换成 Object 进行擦除,这样只需要生成一份泛型函数的副本即可。类型擦除保证了泛型函数生成的字节码和非泛型函数的是相同的,也符合 Java 对兼容性的要求。不过类型擦除也给 Java 的泛型带来了很多的限制,比如:
- 基本类型不支持泛型化
Java 的泛型只能应用于类和对象,无法直接用于基本数据类型(如 int、char)。这导致在使用泛型时需要使用包装类(Wrapper Classes),如 Integer 代替 int。
- 不能创建参数化类型的数组
例如 List<String>[] array = new ArrayList<String>[10];
是非法的。这是因为 Java 泛型系统中的数组是具体化的,而泛型是擦除的,二者不兼容。
- 无法创建参数化类型的实例
不能直接实例化泛型类型。例如,不能使用 new T() 创建泛型类的实例,因为在类型擦除后无法确定 T 的具体类型。
虚方法表
对 Java 来说通过类型擦除结合「虚方法表」(Virtual Method Table)来实现泛型的效果:运行时同样的数据类型 Object,却能调用原始类型的方法。
泛型函数被修改成只接受统一数据类型 Object 作为参数。在调用实际类型对象的方法时,需要找到不通对象的方法。因此,需要一个可以查询方法的内存地址的表格:虚方法表。
虚方法表不仅可以用来实现泛型,还可以用来实现其他类型的多态性,比如 C++ 中的多态。然而,推导这些指针和调用虚拟函数要比直接调用函数慢,而且使用虚方法表会阻止编译器进行优化。
4.2 字典
编译器在编译泛型函数时只生成了一份函数副本,通过新增一个字典参数来供调用方传递类型参数(Type Parameters),这样就可以用一个函数实例支持多种不同的类型参数。这种实现方式称为字典传递(Dictionary passing)。
Go 实现泛型的方式,就是在编译阶段,通过将类型信息以字典的方式传递给泛型函数。当然这个字典不仅包含了类型信息,还包含了此类型的内存操作函数如 make/len/new 等。
同样的 Swift 也通过字典传递了一种名为 Witness table 的数据结构,这种数据结构包含着类型的大小及类型的内存操作函数(移动、复制与释放)。
Swift 在编译阶段通过在函数入参中以字典的形式把 Witness table 注入,达到了以统一的方式处理任何类型,而不用对类型进行装箱操作。这样一来,Swift就可以实现泛型,而且不需要单态化,虽然在运行时有动态查找的开销,但这种表结构节省了分配内存和缓存不一致性的成本。
4.3 单态化
单态化(Monomorphization)是一个实现泛型的常用方法,编译器为每个被调用的数据类型单独生成一个泛型函数副本,以确保类型安全和最佳性能。
func max[T Numeric](a, b T) T {// ...
}larger := max(3, 5)
由于上面显示的 max 函数是用两个整数调用的,编译器在对代码进行单态化时将为 int 生成一个 max 的副本。
func maxInt(a, b int) int {// ...
}larger := maxInt(3, 5)
单态化针对不同类型创建单独的函数副本,显而易见会增加编译时长,但是可以在编译期针对不同类型进行代码优化,且运行时没有类型相关的判断逻辑,性能较好。
模板(Template)
C++ 通过模板实现泛型类、方法和函数,这导致编译器为每个唯一的类型参数集编译了代码的单独副本。这种方法的一个关键优势是没有运行时性能开销,尽管它以增加编译时间和二进制文件大小为代价。
蜡印(Stenciling)
蜡印其实就是模版,也是一种代码生成技术。但 Go 除了使用字典传递实现装箱外,还采用了 GC Shape Stenciling 的技术。这种看起来很高级的名词简单来说是为了解决蜡印或模版的问题,因为在蜡印的过程中,编译器会为每一个实例化的类型参数生成一套独立的代码,这种会有一个问题,请看下面的例子:
type a int
type b int
虽然 a 和 b 是两个自定义的类型,但它们底层都是 int 类型,但编译器会为这两个类型而生成两套函数的版本(如对 max 泛型函数来说会生成 max_a 与 max_b 两个函数版本)。这是一种浪费,还会生成庞大的二进制文件。
GC Shape 这种技术就是通过对类型的底层内存布局(从内存分配器或垃圾回收器的视角)分组,对拥有相同的内存布局的类型参数进行蜡印,比如指针和接口在内存中总是有相同的布局,编译器将为指针和接口的调用生成同一个泛型函数的副本,这样就可以避免生成大量重复的代码。
Go 实现泛型的方式混合了字典与蜡印技术,对于实例类型的 Shape 相同的情况,只生成一份代码,对于 Shape 相同的类型,使用字典区分类型的不同行为。最终的流程如下:
1.开始编译
2.寻找泛型函数调用
3.使用 GCShape 对类型分组
4.为类型生成实例化的函数
5.创建包含类型信息的字典
6.调用实例化的函数并传递入参与类型字典
总的来说 Go 在 1.18 实现泛型的方式和 Rust 类似,如果感兴趣可以看这篇Rust泛型的文章:透过Rust探索系统的本原:泛型。
5.小结
对静态类型检查的编程语言,实现泛型的方式有很多,如:
- C++:通过模版实现,相比 C 的宏,模版显然更强大灵活。
- Java:通过类型擦除的装箱技术结合虚方法表实现,虽然类型擦除导致 Java 的泛型实现不如人意,但这种代价确保了兼容性。
- Swift:通过字典传入的方式配合 Witness Table 的实现,这种巧妙的方式在编译速度与运行时速度之间取得了不错的平衡。
- Go:通过字典传入的方式配合 GC Shape 的蜡印技术实现,这种方式在编译速度与运行时速度之间取得了不错的平衡。
虽然看起来方式多样,但实际上只有两种思路:
- 编译时只生成一份代码,调用方法统一,运行时根据传入的实参类型信息执行相应的操作。
- 编译时根据不同类型生成不同的代码。
泛型是 Go 语言中一个重要的新增特性,它使得代码更加灵活、清晰,减少了重复代码的编写,提高了代码的可维护性和性能。
在性能讨论中经常被忽略的是,所有这些好处和成本只涉及到函数的调用。通常情况下,大部分的执行时间在函数内部。调用方法的开销可能不会成为性能瓶颈,所以要考虑先优化函数实现,再考虑调用开销。
Go 也在不断的改进自己实现泛型的机制,所以此文会存在一些时效性的问题。
参考wenxian
An Introduction To Generics
Type Parameters Proposal
泛型设计 - | Go 语言设计哲学- 煎鱼
golang拾遗:为什么我们需要泛型- apocelipes
简单易懂的Go 泛型使用和实现原理介绍- 万俊峰Kevin
编程语言是如何实现泛型的 - BMPI
Go泛型是怎么实现的? - 鸟窝
相关文章:

Golang 泛型实现原理
文章目录 1.什么是泛型?2.有 interface{} 为什么还要有泛型?3.泛型有哪些特性?3.1 类型参数泛型函数泛型类型 3.2 类型约束3.3 类型集3.4 约束元素任意类型约束元素近似约束元素联合约束元素约束中的可比类型 3.5 类型推断 4.实现原理4.1 类型擦除虚方法…...

[玩转AIGC]LLaMA2之如何微调模型
目录 1、下载训练脚本2、 下载模型2.1、申请下载权限2.2、模型下载 3、模型微调3.1、使用单卡微调3.2、使用多卡训练: 1、下载训练脚本 首先我们从github上下载Llama 2的微调代码:GitHub - facebookresearch/llama-recipes: Examples and recipes for L…...

使用克魔助手进行iOS数据抓包和HTTP抓包的方法详解
摘要 本文博客将介绍如何在iOS环境下使用克魔助手进行数据抓包和HTTP抓包。通过抓包,开发者可以分析移动应用程序的网络请求发送和接收过程,识别潜在的性能和安全问题,提高应用的质量和安全性。 引言 在移动应用程序的开发和测试过程中&am…...
【递归 回溯】LeetCode-301. 删除无效的括号
301. 删除无效的括号。 给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。 示例 1: 输入:s "()())()" 输出:[…...
C++ 基本的输入输出
C 标准库提供了一组丰富的输入/输出功能,我们将在后续的章节进行介绍。本章将讨论 C 编程中最基本和最常见的 I/O 操作。 C 的 I/O 发生在流中,流是字节序列。如果字节流是从设备(如键盘、磁盘驱动器、网络连接等)流向内存&#…...

vue3老项目如何引入vite
vue3老项目如何引入vite 安装 npm install vite vitejs/plugin-vue --save-dev Vite官方中文文档修改package.json文件 在 npm scripts 中使用 vite 执行文件 "scripts": {"serve": "vite","build": "vite build","pr…...

javaEE -19(9000 字 JavaScript入门 - 4)
一: jQuery jQuery是一个快速、小巧且功能丰富的JavaScript库。它旨在简化HTML文档遍历、事件处理、动画效果以及与后端服务器的交互等操作。通过使用jQuery,开发者可以以更简洁、更高效的方式来编写JavaScript代码。 jQuery提供了许多易于使用的方法和…...
二叉树的非递归遍历|前中后序遍历
二叉树的非递归遍历 文章目录 二叉树的非递归遍历前序遍历-栈层序遍历-队列中序遍历-栈后序遍历-栈 前序遍历-栈 首先我们应该创建一个Stack 用来存放节点,首先我们想要打印根节点的数据,此时Stack里面的内容为空,所以我们优先将头结点加入S…...
开源minio-AWS-S3存储的部署及go操作详细
介绍 MinIO是一个开源的分布式对象存储服务,它允许用户在私有云或公有云环境中构建自己的对象存储基础设施。MinIO旨在提供高性能、高可用性的对象存储,并且与Amazon S3兼容,这意味着可以使用S3客户端工具和库直接与MinIO交互,而…...
【Web2D/3D】Canvas(第三篇)
1. 前言 <canvas>是HTML5新增元素,它是一个画板,开发人员基于它的2D上下文或webgl上下文,使用JS脚本绘制简单的动画、可交互画面,甚至进行视频渲染。 本篇介绍基于canvas的2D上下文绘制2D画面的一些方法和属性。 2. canvas…...

紫光展锐T820与飞桨完成I级兼容性测试 助推端侧AI融合创新
近日,紫光展锐高性能5G SoC T820与百度飞桨完成I级兼容性测试(基于Paddle Lite工具)。测试结果显示,双方兼容性表现良好,整体运行稳定。这是紫光展锐加入百度“硬件生态共创计划”后的阶段性成果。 本次I级兼容性测试完…...

3DV 2024 Oral | SlimmeRF:可动态压缩辐射场,实现模型大小和建模精度的灵活权衡
目前大多数NeRF模型要么通过使用大型模型来实现高精度,要么通过牺牲精度来节省内存资源。这使得任何单一模型的适用范围受到局限,因为高精度模型可能无法适应低内存设备,而内存高效模型可能无法满足高质量要求。为此,本文研究者提…...

【unity学习笔记】4.场景切换
创建空物体→创建脚本挂载在空物体上→打开脚本 1.创建所需要的场景 assets中点击创建场景 2.文件→生成设置 3.将需要的场景拖入 4.场景跳转 创建空对象,将脚本放在空对象上。 注意两个类:场景类、场景管理类 void Start(){//场景跳转SceneManager.Lo…...
LeetCode75| 滑动窗口
目录 643 子数组最大平均数 | 1456 定长子串中元音的最大数目 1004 最大连续1的个数 ||| 1493 删掉一个元素以后全为1的最长子数组 643 子数组最大平均数 | class Solution { public:double findMaxAverage(vector<int>& nums, int k) {double sum 0;double re…...

gulimall-002 分布式基础概念
1、微服务概念 微服务是一种非常流行的架构风格。 拒绝大型单体应用,基于业务边界进行服务微化拆分,各个服务独立部署运行。 每个服务运行在自己的单个进程使用轻量级机制通信可以使用不同的编程语言编写以及不同的数据存储技术 2、集群&分布式&…...
K8s之声明式APIs
大家好,我是升仔 引言 Kubernetes(K8s)是一个开源的容器编排系统,用于自动化部署、扩展和管理容器化应用。在K8s中,声明式APIs(Application Programming Interfaces)是一种核心概念࿰…...

Hive执行计划
Hive提供了explain命令来展示一个查询的执行计划,这个执行计划对于我们了解底层原理,Hive 调优,排查数据倾斜等很有帮助。 使用语法如下: explain query;在 hive cli 中输入以下命令(hive 2.3.7): explain select s…...

Leetcode—62.不同路径【中等】
2023每日刷题(七十二) Leetcode—62.不同路径 超时dfs代码 class Solution { public:int uniquePaths(int m, int n) {int starti 1, startj 1;int ans 0;function<void(int, int)> dfs [&](int i, int j) {if(i m && j n) {a…...

【汇编笔记】初识汇编-内存读写
汇编语言的由来: CPU是计算机的核心,由于计算机只认识二进制,所以CPU执行的指令是二进制。 我们要想让CPU工作,就得给他提供它认识的指令,这一系列的指令的集合,称之为指令集。 指令集: 不同的体…...

Shell脚本通过渗透测试检测服务器安全!
以下是一个简单的 Shell 脚本通过渗透测试来发现服务器漏洞的例子: #!/bin/bash # 设置变量 server_url"http://example.com" server_port"80" script_path"/path/to/script.脚本" # 创建并打开 Web 服务器 web_server$(curl -s $se…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...