乐趣区

关于go:简单易懂的-Go-泛型使用和实现原理介绍

原文:A gentle introduction to generics in Go by Dominik Braun

万俊峰 Kevin:我看了感觉文章非常简单易懂,就征求了作者批准,翻译进去给大家分享一下。

本文是对泛型的根本思维及其在 Go 中的实现的一个比拟容易了解的介绍,同时也是对围绕泛型的各种性能探讨的简略总结。首先,咱们来看看泛型所解决的外围问题。

问题

假如咱们想实现一个简略的 tree 数据结构。每个节点持有一个值。在 Go 1.18 之前,实现这种构造的典型办法如下。

type Node struct {value interface{}
}

这在大多数状况下都很好用,但它也有一些毛病。

首先,interface{} 能够是任何货色。如果咱们想限度 value 可能持有的类型,例如整数和浮点数,咱们只能在运行时查看这个限度。

func (n Node) IsValid() bool {switch n.value.(type) {
        case int, float32, float64:
            return true
        default:
            return false
    }
}

这样并不可能在编译时限度类型,像下面这样的类型判断在许多 Go 库中都是很常见的做法。这里有 go-zero 我的项目中的例子。

第二,对 Node 中的值进行解决是十分繁琐和容易出错的。对值做任何事件都会波及到某种类型的断言,即便你能够平安地假如值持有一个 int 值。

number, ok := node.value.(int)
if !ok {// ...}

double := number * 2

这些只是应用 interface{} 的一些不便之处,它没有提供类型平安,并有可能导致难以复原的运行时谬误。

解决办法

咱们不打算承受任意数据类型或具体类型,而是定义一个叫做 T占位符类型 作为值的类型。请留神,这段代码还不会通过编译。

type Node[T] struct {value T}

首先须要申明泛型类型 T,这是在构造或函数名称前面方括号外面应用的。

T 能够是任何类型,只有在实例化一个具备明确类型的 Node 时,T 才会被推导为该类型。

n := Node[int]{value: 5,}

泛型 Node 被实例化为 Node[int](整数节点),所以 T 是一个 int

类型束缚

下面的实现里,T 的申明短少一个必要的信息:类型束缚。

类型束缚用于进一步限度能够作为 T 的可能类型。Go 自身提供了一些预约义的类型束缚,但也能够应用自定义的类型束缚。

type Node[T any] struct {value T}

任意类型(any)束缚容许 T 实际上是任何类型。如果节点值须要进行比拟,有一个 comparable 类型束缚,满足这个预约义束缚的类型能够应用 == 进行比拟。

type Node[T comparable] struct {value T}

任何类型都能够作为一个类型束缚。Go 1.18 引入了一种新的 interface 语法,能够嵌入其余数据类型。

type Numeric interface {int | float32 | float64}

这意味着一个接口不仅能够定义一组办法,还能够定义一组类型。应用 Numeric 接口作为类型束缚,意味着值能够是整数或浮点数。

type Node[T Numeric] struct {value T}

重获类型平安

绝对于应用 interface{},泛型类型参数的微小劣势在于,T 的最终类型在编译时就会被推导进去。为 T 定义一个类型束缚,齐全打消了运行时查看。如果用作 T 的类型不满足类型束缚,代码就不会编译通过。

在编写泛型代码时,你能够像曾经晓得 T 的最终类型一样写代码。

func (n Node[T]) Value() T {return n.value}

下面的函数返回 n.Value,它的类型是 T。因而,返回值是 T,如果 T 是一个整数,那么返回类型就已知是 int。因而,返回值能够间接作为一个整数应用,不须要任何类型断言。

n := Node[int]{value: 5,}

double := n.Value() * 2

在编译时复原类型平安使 Go 代码更牢靠,更不容易出错。

泛型应用场景

Ian Lance Taylor 的 When To Use Generics 中列出了泛型的典型应用场景,归结为三种次要状况:

  1. 应用内置的容器类型,如 slicesmapschannels
  2. 实现通用的数据结构,如 linked listtree
  3. 编写一个函数,其实现对许多类型来说都是一样的,比方一个排序函数

一般来说,当你不想对你所操作的值的内容做出假如时,能够思考应用泛型。咱们例子中的 Node 并不太关怀它持有的值。

当不同的类型有不同的实现时,泛型就不是一个好的抉择。另外,不要把 Read(r io.Reader) 这样的接口函数签名改为 Read[T io.Reader](r T) 这样的通用签名。

性能

要理解泛型的性能及其在 Go 中的实现,首先须要理解个别状况下实现泛型的两种最常见形式。

这是对各种性能的深入研究和围绕它们进行的探讨的简要介绍。你大概率不太须要关怀 Go 中泛型的性能。

虚构办法表

在编译器中实现泛型的一种办法是应用 Virtual Method Table。泛型函数被批改成只承受指针作为参数的形式。而后,这些值被调配到堆上,这些值的指针被传递给泛型函数。这样做是因为指针看起来总是一样的,不论它指向的是什么类型。

如果这些值是对象,而泛型函数须要调用这些对象的办法,它就不能再这样做了。该函数只有一个指向对象的指针,不晓得它们的办法在哪里。因而,它须要一个能够查询方法的内存地址的表格:Virtual Method Table。这种所谓的动静调度曾经被 Go 和 Java 等语言中的接口所应用。

Virtual Method Table 不仅能够用来实现泛型,还能够用来实现其余类型的多态性。然而,推导这些指针和调用虚构函数要比间接调用函数慢,而且应用 Virtual Method Table 会阻止编译器进行优化。

单态化

一个更简略的办法是单态化(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)

最大的劣势是,Monomorphization 带来的运行时性能显著好于应用 Virtual Method Table。间接办法调用不仅更有效率,而且还能实用整个编译器的优化链。不过,这样做的代价是编译时长,为所有相干类型生成泛型函数的正本是十分耗时的。

Go 的实现

这两种办法中哪一种最适宜 Go?疾速编译很重要,但运行时性能也很重要。为了满足这些要求,Go 团队决定在实现泛型时混合两种办法。

Go 应用 Monomorphization,但试图缩小须要生成的函数正本的数量。它不是为每个类型创立一个正本,而是为内存中的每个布局生成一个正本:intfloat64Node 和其余所谓的 "值类型" 在内存中看起来都不一样,因而泛型函数将为所有这些类型复制正本。

与值类型相同,指针和接口在内存中总是有雷同的布局。编译器将为指针和接口的调用生成一个泛型函数的正本。就像 Virtual Method Table 一样,泛型函数接管指针,因而须要一个表来动静地查找办法地址。在 Go 实现中的字典与虚构办法表的性能特点雷同。

论断

这种混合办法的益处是,你在应用值类型的调用中取得了 Monomorphization 的性能劣势,而只在应用指针或接口的调用中付出了 Virtual Method Table 的老本。

在性能探讨中常常被疏忽的是,所有这些益处和老本只波及到函数的调用。通常状况下,大部分的执行工夫是在函数外部应用的。调用办法的性能开销可能不会成为性能瓶颈,即便是这样,也要思考先优化函数实现,再思考调用开销。

更多浏览

Vicent Marti: Generics can make your Go code slower (PlanetScale)

Andy Arthur: Generics and Value Types in Golang (Dolthub)

Virtual method table (Wikipedia)

Monomorphization (Wikipedia)

Dynamic dispatch (Wikipedia)

对规范库的影响

作为 Go 1.18 的一部分,不扭转规范库 是一个审慎的决定。目前的打算是收集泛型的教训,学习如何适当地应用它们,并在规范库中找出正当的用例。

Go 有一些对于通用包、函数和数据结构的提议:

  • constraints, providing type constraints (#47319)
  • maps, providing generic map functions (#47330)
  • slices, providing generic slice functions (#47203)
  • sort.SliceOf, a generic sort implementation (#47619)
  • sync.PoolOf and other generic concurrent data structures (#47657)

对于 go-zero 泛型的打算

对 go-zero 反对用泛型改写,咱们持审慎态度,因为一旦应用泛型,那么 Go 版本必须从 1.15 降级到 1.18,很多用户的线上服务当初还未降级到最新版,所以 go-zero 的泛型改写会延后 Go 两三个版本,确保用户线上服务大部分曾经降级到 Go 1.18

go-zero 也在对泛型做充沛的调研和尝试。

其中的 mr 包曾经新开仓库反对了泛型:

https://github.com/kevwan/mapreduce

其中的 fx 包也已新开仓库尝试反对泛型,然而因为短少 template method,未能实现,期待后续 Go 泛型的欠缺

https://github.com/kevwan/stream

当后续 go-zero 反对泛型的时候,咱们就会合入这些曾经充沛测试的泛型实现。

我的项目地址

https://github.com/zeromicro/go-zero

欢送应用 go-zerostar 反对咱们!

微信交换群

关注『微服务实际 』公众号并点击 交换群 获取社区群二维码。

如果你有 go-zero 的应用心得文章,或者源码学习笔记,欢送通过公众号分割投稿!

退出移动版