你真的了解泛型 Generic 嘛？

泛型 Generic Programming^[1] 通常指允許程序員在強(qiáng)類型程序設(shè)計(jì)語言中，編寫代碼時(shí)使用一些以后才指定的類型，在實(shí)例化時(shí)作為參數(shù)指明這些類型，即類型參數(shù)化

首先我們不是科班討論學(xué)術(shù)，有些概念比較模糊也正常，本文討論的內(nèi)容意在給大家提供全局的視野看待泛型 Generic, 大致了解主流語言的實(shí)現(xiàn)

泛型會(huì)提供哪些便利呢？上面的動(dòng)圖非常經(jīng)典，比如 min 函數(shù)，如果沒有泛型，需要針對(duì) int, float, string 分別寫出不同的特定實(shí)現(xiàn)，代碼非常冗余。本文會(huì)討論下為什么 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);  // 整數(shù)
  max(1.2,2.3); // 浮點(diǎn)數(shù)
  return 0;
}

上面是 cpp 模板實(shí)現(xiàn)的 max 泛型函數(shù)，傳入 int, float 都可以工作

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

運(yùn)行結(jié)果如上所示，同樣代碼換成 go 肯定就是錯(cuò)的，本質(zhì)是模板在編譯期單態(tài)化，針對(duì)每個(gè)特定類型生成了特定函數(shù)

$ 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 查看二進(jìn)制的符號(hào)表，生成了兩個(gè)函數(shù)，簽名分別是 double max<double>(double, double), int max<int>(int, int)

CPP 模板非常強(qiáng)大，但是也有缺點(diǎn)，比如二進(jìn)制膨脹的厲害，有可能影響到 cpu icache, 業(yè)務(wù)代碼無所謂了。另外 T 沒有其它語言的 constraint 或 bounded, 比如要求 T 必須實(shí)現(xiàn)某些方法，然后函數(shù)內(nèi)只能調(diào)用這些顯示的約束(C++20 會(huì)引入 concepts 實(shí)現(xiàn)約束)

C 怎么實(shí)現(xiàn)

C 嚴(yán)格意義上沒有實(shí)現(xiàn)，但在 C11 標(biāo)準(zhǔn)中引入了 _Generic 泛型選擇器，閹割版的實(shí)現(xiàn)

#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;
}

上面是實(shí)現(xiàn)的 ADD 方法，只是調(diào)用的時(shí)候看起來是泛型了。這種實(shí)現(xiàn)是有缺點(diǎn)的，c 會(huì)做很多隱式轉(zhuǎn)換，即使你傳入字符串，也會(huì)編譯成功，并且取得一個(gè)值。并沒有在編譯期確保類型 a, b 一致

同時(shí)由于 c 不支持函數(shù)名重載，還要人工編寫特定實(shí)例的函數(shù) addF, addI, 并且二進(jìn)制的符號(hào)表并沒有 ADD. 類比 cpp 是由編譯器替我們完成

在 C11 以前的標(biāo)準(zhǔn)中，很多代碼都是用 void * 實(shí)現(xiàn)，問題在于 void 是沒有類型信息的，需要增加特定的函數(shù)指針回調(diào)，讓我們來看 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 可以是任意類型，只要實(shí)現(xiàn)了 dictType 定義的函數(shù)指針。內(nèi)核里面也有大量類似實(shí)現(xiàn)，非常通用

Rust 實(shí)現(xiàn)

Rust 泛型也同樣編譯期單態(tài)化，運(yùn)行時(shí)沒有開銷

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

這里定義函數(shù) printer, 類型 T 必須實(shí)現(xiàn)了 Display trait, 這就是所謂的 constraint 或者 bounded

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

但假如需要滿足多個(gè)約束的時(shí)候，在 <> 里寫就很不簡(jiǎn)潔，需要使用 where^[4] 關(guān)鍵字

Rust 很多時(shí)候難懂，就是因?yàn)榀B加了泛型，生命周期，所有權(quán)，還有很多的 wrapper, 別說寫了，讀都讀不懂

Java 版本

Java 在 1.5 版本引入了泛型，它的泛型是用類型擦除實(shí)現(xiàn)的。Java 的泛型只是在編譯期間用于檢查類型的正確，為了保證與舊版本 JVM 的兼容，類型擦除會(huì)刪除泛型的相關(guān)信息，導(dǎo)致其在運(yùn)行時(shí)不可用。關(guān)于這塊可以參考 大神R大的回答^[5], 早就有類似 cpp 實(shí)現(xiàn)，只是涉及兼容上的取舍，不得不這么做

編譯器會(huì)插入額外的類型轉(zhuǎn)換指令，與 C 語言和 C++ 在運(yùn)行前就已經(jīng)實(shí)現(xiàn)或者生成代碼相比，Java 類型的裝箱和拆箱會(huì)降低程序的執(zhí)行效率。非 Java 黨就不寫太多了

Go 為什么需要泛型

官方要在 go1.18 引入泛型，那現(xiàn)在我們是怎么用的呢？很多時(shí)候就是 copy 代碼，或者用 interface{} 代替

func Max(a , b Comparable) Comparable

比如常見的 Max 函數(shù)，傳入?yún)?shù) a, b 都實(shí)現(xiàn)了 Comparable 接口，然后返回最大值。能工作不？能，但是有問題

1. 丟失了類型信息，原來 cpp/rust 的實(shí)現(xiàn)，在函數(shù)中操作的都是原始類型，如果用 interface 還需要斷言，這是運(yùn)行時(shí)行為，性能損失很大
2. 表達(dá)力不夠，比如 a, b 不能確保是同一個(gè)類型，可能一個(gè)是 int, 另外一個(gè)是 struct. 如果想傳入的是類型組合呢？

再看一個(gè) interface{} 不能當(dāng)成泛型的例子

func sort(arr []interface{})

這個(gè)排序函數(shù)如果傳入 sort([]int{1,2,3}) 或是 sort([]float64{1.032, 3.012}) 都會(huì)報(bào)錯(cuò)，原因是什么呢？？？

在 go 中 []interface{} 類型是 slice 不是 interface{}, go 中對(duì)比接口相等時(shí)，是判斷 itab 中 type 和 data 需要都一致。換句話說，不允許類型的協(xié)變(沒其它語言背景的不必糾結(jié)概念，在 Go2 中也不打算支持協(xié)變和逆變)

同時(shí)社區(qū)還有其它庫(kù)輔助，比如 genny^[6] 和 betterGO^[7], 本質(zhì)還是上面的動(dòng)圖

// 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
}

上面定義了一個(gè)泛型 type Something generic.Type, 然后用 go generate 生成對(duì)應(yīng)的泛型代碼

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
}

最后替換相應(yīng)的類型，生成對(duì)應(yīng)源碼文件，人肉模板騷不騷^^

Go2 泛型

泛型討論了很久，參見 generic programming facilities^[8], Why Generics^[9], Next Step^[10], 以及官方 proposal^[11], 這是最終版，語法上不會(huì)再改變。為了運(yùn)行時(shí)性能，go 的實(shí)現(xiàn)類似 rust 編譯期單態(tài)化，而且為了兼容 go1 語法也會(huì)做一些妥協(xié)。如果近期想閱讀源碼的，不如等到明年 go1.18, 因?yàn)橐敕盒驮创a庫(kù)變更會(huì)很大

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) {
 ......
}

類型參數(shù)列表，放到中括號(hào)里 [], 其中 T 是類型，any 關(guān)鍵字是表示可以傳入任意類型。居然不是業(yè)界通用的尖括號(hào) <> 感覺非常丑... 其中 any 其實(shí)就是 interface{} 空接口，寫起來相對(duì)方便，而且語意上表達(dá)更準(zhǔn)確一些

// 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 的參數(shù) s1, s2 類別必然要相同，編譯期保證。這也就是上面提到 go1 時(shí) interface{} 模擬泛型的問題

2.Constraint

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

這個(gè)例子是不會(huì)編譯成功的，因?yàn)?T 是任意類型，并沒有實(shí)現(xiàn) String() 方法。也就是說，泛型函數(shù)只允許調(diào)用 constraint 約束里顯示指定的方法 這樣的好處是，對(duì)于大型項(xiàng)目的構(gòu)建，不會(huì)因?yàn)殡[式的改動(dòng)，而改變兼容性

相比于 rust where 語句，go 中增加了類型參數(shù)列表和接口的組合，做為約束

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
}

上面是約束的定義，關(guān)鍵字 type 后面跟上允許的類型列表，不知道為啥就是丑。其它語言用到哪個(gè)類型，編譯期單態(tài)就好了，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, 另一個(gè)使用場(chǎng)景是泛型類型 Generic Type

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

上面標(biāo)準(zhǔn)的泛型容器定義，類似其它語言的 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 語法，比較相似。但如果泛型類型，有指向自己的指針，那么注意參數(shù)順序也要一樣，P[T1, T2 any] 這樣寫的，那么指針也要 *[T1, T2]. 官方說防止類型實(shí)例化的遞歸

4.Comparable types in constraints

Go 不允許重載操作符，這樣好處多多。但同時(shí)代表著大于，小于這些只適用于基本類型。但也有例外 ==, != 可以比較 struct, array, interface. 官方在標(biāo)準(zhǔn)庫(kù)預(yù)定義了約束 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 實(shí)現(xiàn)了比較接口，就可以用 ==

// 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 實(shí)現(xiàn)約束，上面的例子是 hasher 接口，下面的接口是永遠(yuǎn)不能實(shí)現(xiàn)的，很好理解，類型 []int 是不能比較的

5.類型推導(dǎo) type inference

類型推導(dǎo)很重要，可以省略很多無用代碼，編譯器自動(dòng)識(shí)別類型

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

這是一個(gè) Map 算子函數(shù)的簽名，f 匿名函數(shù)，將 []F 轉(zhuǎn)換成 []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)

最理想只需要調(diào)用 r=Map(s, f) 就可以，否則還要寫 r = Map[int, int64](s, f), 能推導(dǎo)的就不要讓人寫

除了上面的，再舉個(gè)例子比如 T1, T2 是兩個(gè)類型參數(shù)，那么 []map[int]bool 可以和以下類型統(tǒng)一 unified 起來

• []map[int]bool 這個(gè)就是類型自身，很好理解
• T1 當(dāng)然可以匹配
• []T1 T1 匹配到 map[int]bool
• []map[T1]T2 這里 T1 是 int, T2 是 bool

上面只是幾種可能，但同時(shí)不能匹配到 int, struct{}, []map[T1]string 這也是顯而易見的。雖然 go2 不支持協(xié)變，但是基于類型推導(dǎo)還是比 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
}

約束還可以將 類型列表 與普通的接口函數(shù)組合起來。上面的 StringableSignedInteger 要求約束，必須是 type list 里的任一類型，同時(shí)實(shí)現(xiàn)了 String() string 函數(shù)

問題是 int 這些都沒有 string 方法，所以上面約束其實(shí)是 impossible 的，只是舉例子說明如何使用

7.未實(shí)現(xiàn)部份

官方還列舉了很多 omissions^[12] 未實(shí)現(xiàn)的點(diǎn)

比如不支持：特化，元編程(cpp 玩爛了)，curry 柯立化等等，泛型分享內(nèi)容大致這些，感興趣直接看官網(wǎng)好了

泛型代價(jià)

引入泛型不是沒有代價(jià)的，都是取舍，好在 go 語言誕生才十年，沒有很重的歷史包袱

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

但 go 真的需要泛型嘛？雖然 go 定位是系統(tǒng)語言，用的最多還是偏業(yè)務(wù)層，中間件以下還是 c/c++ 的舞臺(tái)，哪怕 go 己經(jīng)有了殺手級(jí)應(yīng)用 docker/k8s

吸引大公司選擇 go 的原因，就是簡(jiǎn)單，快速上手，goroutine 用戶態(tài)高并發(fā)。如果 GA 后，會(huì)不會(huì)導(dǎo)致代碼庫(kù)里泛型使用泛濫呢？可以預(yù)見，go1.18 出來后，大家要刷新對(duì) go 的認(rèn)識(shí)了，同時(shí)對(duì)于新手學(xué)習(xí)區(qū)線也不再簡(jiǎn)單

支持泛型也會(huì)讓 go 很好的處理數(shù)據(jù)，要是再搞個(gè)分代 GC, 是不是可以造大數(shù)據(jù)的輪子了^^

小結(jié)

引用曹大^[13]的一句話：敏捷大師們其實(shí)非常雙標(biāo)，他們給出的方法論也不一定靠譜，反正成功了就是大師方法得當(dāng)，失敗了就是我們執(zhí)行不力沒有學(xué)到精髓。正著說反著說都有道理。

再看看現(xiàn)在的 Go 社區(qū)，buzzwords 也很多，如果一個(gè)特性大師不想做，那就是 less is more. 如果一個(gè)特性大師想做，那就是 orthogonal, 非常客觀

寫文章不容易，如果對(duì)大家有所幫助和啟發(fā)，請(qǐng)大家?guī)兔c(diǎn)擊在看，點(diǎn)贊，分享 三連

關(guān)于 泛型 大家有什么看法，歡迎留言一起討論，大牛多留言 ^_^

參考資料