Golang 泛型实现原理

2023-12-24 08:22:10 浏览数 (1)

文章目录
  • 1.有 interface{} 为什么还要有泛型?
  • 2.泛型实现原理
    • 2.1 类型参数
      • 泛型函数
      • 泛型数据结构
    • 2.2 类型约束
    • 2.3 编译时生成
      • 虚拟方法表
      • 单态化
    • Go 的实现
  • 3.小结
  • 参考wenxian

泛型(Generics)是 Go 语言在较早版本缺失的一个特性,直到 Go 1.18 版本中才引入了泛型。泛型提供了一种更灵活、更通用的方式来编写函数和数据结构,以处理不同类型的数据,而不必针对每种类型编写重复的代码。

1.有 interface{} 为什么还要有泛型?

虽然 Go 中的空接口 interface{} 允许存储任何类型的值,但它是一种动态类型的机制,并且在使用时需要进行类型断言。相比之下,泛型(Generics)提供了一种静态类型的通用解决方案,使得代码可以在不失去类型安全性的前提下处理多种数据类型。

使用泛型可以带来如下好处:

  • 类型安全

泛型允许开发者在编译时指定代码的通用类型,为类型参数定义一个类型约束,而不需要使用空接口进行运行时类型断言。这提供了更强的类型安全性,因为在编译时就能够发现类型错误。

  • 性能优化

在某些情况下,使用泛型可以带来性能优势。由于泛型代码是在编译时生成的,而不是在运行时进行类型断言,因此它可以更好地进行优化。

  • 代码重用和抽象

泛型允许编写通用的、与具体数据类型无关的代码,从而提高代码的重用性和抽象性。不再需要为每种数据类型都编写相似的代码,避免违反 DRY 原则(Don’t Repeat Yourself)。

2.泛型实现原理

Go 语言的泛型实现采用了一种基于类型参数的方式。泛型的设计目标是实现更加通用和类型安全的代码,而不是通过接口(像空接口 interface{})和类型断言来实现动态类型的处理。

以下是 Go 泛型实现的基本原理:

2.1 类型参数

Go 的泛型使用类型参数来实现通用性。在定义函数、数据结构或方法时,可以声明一个或多个类型参数。这些类型参数允许你在代码中引用并操作不同的数据类型。

泛型函数

泛型函数允许你编写能够处理不同类型的数据的通用函数,而不必为每种类型编写重复的代码。例如,可以创建一个泛型的排序函数,适用于不同类型的切片。

代码语言:javascript复制
func Swap[T any](a, b T) (T, T) {
    return b, a
}

在上面的例子中,T 是一个类型参数,它表示一个占位符,可以代表任意类型。在函数体内,可以使用 T 来表示参数和返回值的类型。

泛型数据结构

泛型也可以用于创建通用的数据结构,如泛型切片、泛型映射等。这样可以更灵活地处理不同类型的数据。

代码语言:javascript复制
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 是一个泛型的堆栈数据结构,可以处理任意类型的元素。

2.2 类型约束

为了确保类型安全性,Go 引入了类型约束(type constraints)。

类型约束规定了类型参数必须满足的条件,以便进行合法的操作。例如,可以使用 interface{} 类型进行类型约束,也可以使用特定的接口类型或基本类型。

代码语言:javascript复制
func Print[T fmt.Stringer](value T) {
    fmt.Println(value.String())
}

在上述例子中,T 被约束为实现了 fmt.Stringer 接口的类型。

任何类型都可以作为一个类型约束。Go 1.18 引入了一种新的 interface 语法,可以嵌入其他数据类型。

代码语言:javascript复制
type Numeric interface {
    int | float32 | float64
}

这意味着一个接口不仅可以定义一组方法,还可以定义一组类型。使用 Numeric 接口作为类型约束,意味着值可以是整数或浮点数。

代码语言:javascript复制
type Node[T Numeric] struct {
    value T
}

2.3 编译时生成

Go 的泛型代码是在编译时生成的,而不是在运行时进行类型断言。这意味着泛型代码在编译时就能够获得类型信息,从而保证类型安全性。生成的代码针对具体的类型进行了优化,避免了运行时的性能开销。

虚拟方法表

在编译器中实现泛型的一种方法是使用 Virtual Method Table。

泛型函数被修改成只接受指针作为参数的方式。然后,这些值被分配到堆上,这些值的指针被传递给泛型函数。这样做是因为指针看起来总是一样的,不管它指向的是什么类型。

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

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

单态化

一个更简单的方法是单态化(Monomorphization),编译器为每个被调用的数据类型生成一个泛型函数的副本,以确保类型安全和最佳性能。

代码语言:javascript复制
func max[T Numeric](a, b T) T {
    // ...
}

larger := max(3, 5)

由于上面显示的 max 函数是用两个整数调用的,编译器在对代码进行单态化时将为 int 生成一个 max 的副本。

代码语言:javascript复制
func maxInt(a, b int) int {
    // ...
}

larger := maxInt(3, 5)

最大的优势是,单态化带来的运行时性能明显好于使用虚函数表。直接方法调用不仅更有效率,而且还能适用整个编译器的优化链。不过,这样做的代价是编译时长,为所有相关类型生成泛型函数的副本是非常耗时的。

Go 的实现

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

Go 使用单态化,但试图减少需要生成的函数副本的数量。它不是为每个类型创建一个副本,而是为内存中的每个布局生成一个副本:int、float64、Node 和其他所谓的 “值类型” 在内存中看起来都不一样,因此编译器将为所有这些类型生成不同的副本。

与值类型相反,指针和接口在内存中总是有相同的布局。编译器将为指针和接口的调用生成同一个泛型函数的副本。就像虚函数表一样,泛型函数接收指针,因此需要一个表来动态地查找方法地址。在 Go 实现中的字典与虚拟方法表的性能特点相同。

这种混合方法的好处是,你在使用值类型的调用中获得了 Monomorphization 的性能优势,而只在使用指针或接口的调用中付出了 Virtual Method Table 的成本。

在性能讨论中经常被忽略的是,所有这些好处和成本只涉及到函数的调用。通常情况下,大部分的执行时间在函数内部。调用方法的开销可能不会成为性能瓶颈,所以要考虑先优化函数实现,再考虑调用开销。

3.小结

泛型是 Go 语言中一个重要的新增特性,它使得代码更加灵活、清晰,减少了重复代码的编写,并提高了代码的可维护性和性能。


参考wenxian

An Introduction To Generics 泛型设计 - | Go 语言设计哲学- 煎鱼 golang拾遗:为什么我们需要泛型- apocelipes 简单易懂的 Go 泛型使用和实现原理介绍

0 人点赞