你真的了解泛型 Generic 嘛?
泛型 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?whereA:?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?emptyfor?_,?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?{comparableHash()?uintptr } //?ImpossibleConstraint?is?a?type?constraint?that?no?type?can?satisfy, //?because?slice?types?are?not?comparable. type?ImpossibleConstraint?interface?{comparabletype?[]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?[]intf?:=?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,?int64String()?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/,
總結
以上是生活随笔為你收集整理的你真的了解泛型 Generic 嘛?的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: MQ 正在变成臭水沟
- 下一篇: 操作系统该怎么学?