你真的了解泛型 Generic 嘛？ - 哈喽比特

259次阅读 | 发布于3年以前

泛型 Generic Programming[1] 通常指允许程序员在强类型程序设计语言中，编写代码时使用一些以后才指定的类型，在实例化时作为参数指明这些类型，即**类型参数化**

首先我们不是科班讨论学术，有些概念比较模糊也正常，本文讨论的内容意在给大家提供全局的视野看待泛型 Generic, 大致了解主流语言的实现

泛型会提供哪些便利呢？上面的动图非常经典，比如 min 函数，如果没有泛型，需要针对 int, float, string 分别写出不同的特定实现，代码非常冗余。本文会讨论下为什么 go 需要泛型以及 go2 泛型的 proposal[2]

CPP 模板

#include <iostream>
template <class T>
T max(T a,T b){
  T ret = a > b? a : b;
  std::cout<< a << " and " << b <<" max is " << ret << std::endl;
  return ret;
}
int main(){
  max(1,2);  // 整数
  max(1.2,2.3); // 浮点数
  return 0;
}

上面是 cpp 模板实现的 max 泛型函数，传入 int, float 都可以工作

$ c++ max.cpp  -o max && ./max
1 and 2 max is 2
1.2 and 2.3 max is 2.3

运行结果如上所示，同样代码换成 go 肯定就是错的，本质是模板在编译期单态化，针对每个特定类型生成了特定函数

$ nm max | grep -i max
0000000100000f90 T __Z3maxIdET_S0_S0_
0000000100000ef0 T __Z3maxIiET_S0_S0_
$ c++filt __Z3maxIdET_S0_S0_
double max<double>(double, double)
$ c++filt __Z3maxIiET_S0_S0_
int max<int>(int, int)

通过 nm 查看二进制的符号表，生成了两个函数，签名分别是 double max<double>(double, double), int max<int>(int, int)

CPP 模板非常强大，但是也有缺点，比如二进制膨胀的厉害，有可能影响到 cpu icache, 业务代码无所谓了。另外 T 没有其它语言的 constraint 或 bounded, 比如要求 T 必须实现某些方法，然后函数内只能调用这些显示的约束(C++20 会引入 concepts 实现约束)

C 怎么实现

C 严格意义上没有实现，但在 C11 标准中引入了 _Generic 泛型选择器，阉割版的实现

#include <stdio.h>
// int类型加法
int addI(int a, int b)
{
    printf("%d + %d = %d\n",a,b, a + b );
    return (a + b);
}
// double类型加法
double addF(double a, double b)
{
    printf("%f + %f = %f\n",a,b, a + b );
    return (a + b);
}
void unsupport(int a,int b)
{
    printf("unsupport type\n");
}
#define ADD(a,b) _Generic((a), \
    int:addI(a,b),\
    double:addF(a,b), \
    default:unsupport(a,b))
int main(void)
{
    ADD(1 , 2);
    ADD(1.1,2.2);
    return 0;
}

上面是实现的 ADD 方法，只是调用的时候看起来是泛型了。这种实现是有缺点的，c 会做很多隐式转换，即使你传入字符串，也会编译成功，并且取得一个值。并没有在编译期确保类型 a, b 一致

同时由于 c 不支持函数名重载，还要人工编写特定实例的函数 addF, addI, 并且二进制的符号表并没有 ADD. 类比 cpp 是由编译器替我们完成

在 C11 以前的标准中，很多代码都是用 void * 实现，问题在于 void 是没有类型信息的，需要增加特定的函数指针回调，让我们来看 redis 例子

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;


typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

上面的代码来自 redis dict[3], 字典是泛型的，value 可以是任意类型，只要实现了 dictType 定义的函数指针。内核里面也有大量类似实现，非常通用

Rust 实现

Rust 泛型也同样编译期单态化，运行时没有开销

fn printer<T: Display>(t: T) {
    println!("{}", t);
}

这里定义函数 printer, 类型 T 必须实现了 Display trait, 这就是所谓的 constraint 或者 bounded

impl <A, D> MyTrait<A, D> for YourType where
    A: TraitB + TraitC,
    D: TraitE + TraitF {

}

但假如需要满足多个约束的时候，在 <> 里写就很不简洁，需要使用 where[4] 关键字

Rust 很多时候难懂，就是因为叠加了泛型，生命周期，所有权，还有很多的 wrapper, 别说写了，读都读不懂

Java 版本

Java 在 1.5 版本引入了泛型，它的泛型是用类型擦除实现的。Java 的泛型只是在编译期间用于检查类型的正确，为了保证与旧版本 JVM 的兼容，类型擦除会删除泛型的相关信息，导致其在运行时不可用。关于这块可以参考大神R大的回答[5], 早就有类似 cpp 实现，只是涉及兼容上的取舍，不得不这么做

编译器会插入额外的类型转换指令，与 C 语言和 C++ 在运行前就已经实现或者生成代码相比，Java 类型的装箱和拆箱会降低程序的执行效率。非 Java 党就不写太多了

Go 为什么需要泛型

官方要在 go1.18 引入泛型，那现在我们是怎么用的呢？很多时候就是 copy 代码，或者用 interface{} 代替

func Max(a , b Comparable) Comparable

比如常见的 Max 函数，传入参数 a, b 都实现了 Comparable 接口，然后返回最大值。能工作不？能，但是有问题

丢失了类型信息，原来 cpp/rust 的实现，在函数中操作的都是原始类型，如果用 interface 还需要断言，这是运行时行为，性能损失很大
表达力不够，比如 a, b 不能确保是同一个类型，可能一个是 int, 另外一个是 struct. 如果想传入的是类型组合呢？

再看一个 interface{} 不能当成泛型的例子

func sort(arr []interface{})

这个排序函数如果传入 sort([]int{1,2,3}) 或是 sort([]float64{1.032, 3.012}) 都会报错，原因是什么呢？？？

在 go 中 []interface{} 类型是 slice 不是 interface{}, go 中对比接口相等时，是判断 itab 中 type 和 data 需要都一致。换句话说，不允许类型的协变(没其它语言背景的不必纠结概念，在 Go2 中也不打算支持协变和逆变)

同时社区还有其它库辅助，比如 genny[6] 和 betterGO[7], 本质还是上面的动图

// NOTE: this is how easy it is to define a generic type
type Something generic.Type

// SomethingQueue is a queue of Somethings.
type SomethingQueue struct {
  items []Something
}

func NewSomethingQueue() *SomethingQueue {
  return &SomethingQueue{items: make([]Something, 0)}
}
func (q *SomethingQueue) Push(item Something) {
  q.items = append(q.items, item)
}
func (q *SomethingQueue) Pop() Something {
  item := q.items[0]
  q.items = q.items[1:]
  return item
}

上面定义了一个泛型 type Something generic.Type, 然后用 go generate 生成对应的泛型代码

cat source.go | genny gen "Something=string"

// StringQueue is a queue of Strings.
type StringQueue struct {
  items []string
}

func NewStringQueue() *StringQueue {
  return &StringQueue{items: make([]string, 0)}
}
func (q *StringQueue) Push(item string) {
  q.items = append(q.items, item)
}
func (q *StringQueue) Pop() string {
  item := q.items[0]
  q.items = q.items[1:]
  return item
}

最后替换相应的类型，生成对应源码文件，人肉模板骚不骚^^

Go2 泛型

泛型讨论了很久，参见 generic programming facilities[8], Why Generics[9], Next Step[10], 以及官方 proposal[11], 这是最终版，语法上不会再改变。为了运行时性能，go 的实现类似 rust 编译期单态化，而且为了兼容 go1 语法也会做一些妥协。如果近期想阅读源码的，不如等到明年 go1.18, 因为引入泛型源码库变更会很大

1.Multiple type parameters

// Print prints the elements of any slice.
// Print has a type parameter T and has a single (non-type)
// parameter s which is a slice of that type parameter.
func Print[T any](s []T) {
 ......
}

类型参数列表，放到中括号里 [], 其中 T 是类型，any 关键字是表示可以传入任意类型。居然不是业界通用的尖括号 <> 感觉非常丑... 其中 any 其实就是 interface{} 空接口，写起来相对方便，而且语意上表达更准确一些

// Print2 has two type parameters and two non-type parameters.
func Print2[T1, T2 any](s1 []T1, s2 []T2) { ... }

// Print2Same has one type parameter and two non-type parameters.
func Print2Same[T any](s1 []T, s2 []T) { ... }

在 Print2 中可以传入相同或不同的类型，比如 Print2[int, int] 者 Print2[int, string] 都是允许的

但是 Print2Same 的参数 s1, s2 类别必然要相同，编译期保证。这也就是上面提到 go1 时 interface{} 模拟泛型的问题

2.Constraint

func Stringify[T any](s []T) (ret []string) {
 for _, v := range s {
  ret = append(ret, v.String()) // INVALID
 }
 return ret
}

这个例子是不会编译成功的，因为 T 是任意类型，并没有实现 String() 方法。也就是说，泛型函数只允许调用 constraint 约束里显示指定的方法 这样的好处是，对于大型项目的构建，不会因为隐式的改动，而改变兼容性

相比于 rust where 语句，go 中增加了类型参数列表和接口的组合，做为约束

package constraints

// Ordered is a type constraint that matches any ordered type.
// An ordered type is one that supports the <, <=, >, and >= operators.
type Ordered interface {
 type int, int8, int16, int32, int64,
  uint, uint8, uint16, uint32, uint64, uintptr,
  float32, float64,
  string
}

上面是约束的定义，关键字 type 后面跟上允许的类型列表，不知道为啥就是丑。其它语言用到哪个类型，编译期单态就好了，go 需要人工枚举所有可能...

// Smallest returns the smallest element in a slice.
// It panics if the slice is empty.
func Smallest[T constraints.Ordered](s []T) T {
 r := s[0] // panics if slice is empty
 for _, v := range s[1:] {
  if v < r {
   r = v
  }
 }
 return r
}

3.泛型类型

上面提到的都是 Generic Func, 另一个使用场景是泛型类型 Generic Type

// Vector is a name for a slice of any element type.
type Vector[T any] []T

上面标准的泛型容器定义，类似其它语言的 Vector

// Push adds a value to the end of a vector.
func (v *Vector[T]) Push(x T) { *v = append(*v, x) }

同样，泛型类型还可以定义方法

// List is a linked list of values of type T.
type ListNode[T] {xxx}
type List[T] struct {
    head *ListNode[T]
    tail *ListNode[T]
    size int
}


// This type is INVALID.
type P[T1, T2 any] struct {
 F *P[T2, T1] // INVALID; must be [T1, T2]
}

上面是定义的 struct 语法，比较相似。但如果泛型类型，有指向自己的指针，那么注意参数顺序也要一样，P[T1, T2 any] 这样写的，那么指针也要 *[T1, T2]. 官方说防止类型实例化的递归

4.Comparable types in constraints

Go 不允许重载操作符，这样好处多多。但同时代表着大于，小于这些只适用于基本类型。但也有例外 ==, != 可以比较 struct, array, interface. 官方在标准库预定义了约束 comparable 用于比较

// Index returns the index of x in s, or -1 if not found.
func Index[T comparable](s []T, x T) int {
 for i, v := range s {
  // v and x are type T, which has the comparable
  // constraint, so we can use == here.
  if v == x {
   return i
  }
 }
 return -1
}

上面的例子很清晰明了，T 实现了比较接口，就可以用 ==

// ComparableHasher is a type constraint that matches all
// comparable types with a Hash method.
type ComparableHasher interface {
 comparable
 Hash() uintptr
}

// ImpossibleConstraint is a type constraint that no type can satisfy,
// because slice types are not comparable.
type ImpossibleConstraint interface {
 comparable
 type []int
}

用 interface 实现约束，上面的例子是 hasher 接口，下面的接口是永远不能实现的，很好理解，类型 []int 是不能比较的

5.类型推导 type inference

类型推导很重要，可以省略很多无用代码，编译器自动识别类型

func Map[F, T any](s []F, f func(F) T) []T { ... }

这是一个 Map 算子函数的签名，f 匿名函数，将 []F 转换成 []T 类型 slice

 var s []int
 f := func(i int) int64 { return int64(i) }
 var r []int64
 // Specify both type arguments explicitly.
 r = Map[int, int64](s, f)
 // Specify just the first type argument, for F,
 // and let T be inferred.
 r = Map[int](s, f)
 // Don't specify any type arguments, and let both be inferred.
 r = Map(s, f)

最理想只需要调用 r=Map(s, f) 就可以，否则还要写 r = Map[int, int64](s, f), 能推导的就不要让人写

除了上面的，再举个例子比如 T1, T2 是两个类型参数，那么 []map[int]bool 可以和以下类型统一 unified 起来

[]map[int]bool 这个就是类型自身，很好理解
T1 当然可以匹配
[]T1 T1 匹配到 map[int]bool
[]map[T1]T2 这里 T1 是 int, T2 是 bool

上面只是几种可能，但同时不能匹配到 int, struct{}, []map[T1]string 这也是显而易见的。虽然 go2 不支持协变，但是基于类型推导还是比 go1 方便的多

6.type lists 组合

// StringableSignedInteger is a type constraint that matches any
// type that is both 1) defined as a signed integer type;
// 2) has a String method.
type StringableSignedInteger interface {
 type int, int8, int16, int32, int64
 String() string
}

约束还可以将 类型列表 与普通的接口函数组合起来。上面的 StringableSignedInteger 要求约束，必须是 type list 里的任一类型，同时实现了 String() string 函数

问题是 int 这些都没有 string 方法，所以上面约束其实是 impossible 的，只是举例子说明如何使用

7.未实现部份

官方还列举了很多 omissions[12] 未实现的点

比如不支持：特化，元编程(cpp 玩烂了)，curry 柯立化等等，泛型分享内容大致这些，感兴趣直接看官网好了

泛型代价

引入泛型不是没有代价的，都是取舍，好在 go 语言诞生才十年，没有很重的历史包袱

Slow Compiler: 这是 c++/rust 泛型
Slow Performance: 这是 java/scala 泛型
Slow Programmer: 这是 go1

但 go 真的需要泛型嘛？虽然 go 定位是系统语言，用的最多还是偏业务层，中间件以下还是 c/c++ 的舞台，哪怕 go 己经有了杀手级应用 docker/k8s

吸引大公司选择 go 的原因，就是简单，快速上手，goroutine 用户态高并发。如果 GA 后，会不会导致代码库里泛型使用泛滥呢？可以预见，go1.18 出来后，大家要刷新对 go 的认识了，同时对于新手学习区线也不再简单

支持泛型也会让 go 很好的处理数据，要是再搞个分代 GC, 是不是可以造大数据的轮子了^^

小结

引用曹大[13]的一句话：敏捷大师们其实非常双标，他们给出的方法论也不一定靠谱，反正成功了就是大师方法得当，失败了就是我们执行不力没有学到精髓。正着说反着说都有道理。

再看看现在的 Go 社区，buzzwords 也很多，如果一个特性大师不想做，那就是 less is more. 如果一个特性大师想做，那就是 orthogonal, 非常客观

参考资料

[1] 泛型程序设计: https://zh.wikipedia.org/wiki/%E6%B3%9B%E5%9E%8B%E7%BC%96%E7%A8%8B,

[2] go2 泛型最终提案: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md,

[3] redis disct: https://github.com/redis/redis/blob/unstable/src/dict.h#L61,

[4] rust where: https://rustwiki.org/zh-CN/rust-by-example/generics/where.html,

[5] Java 不能实现真正泛型的原因是什么？: https://www.zhihu.com/question/28665443/answer/118148143,

[6] genny: https://github.com/cheekybits/genny,

[7] betterGO: https://github.com/PioneerIncubator/betterGo,

[8] generic programming facilities: https://github.com/golang/go/issues/15292,

[9] Why Generics: https://blog.golang.org/why-generics#TOC_1.,

[10] generics-next-step: https://blog.golang.org/generics-next-step,

[11] 泛型官方 proposal: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md,

[12] omissions: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#omissions,

[13] why-do-we-need-generics: https://xargin.com/why-do-we-need-generics/,