卷起來！Go泛型是怎么實現(xiàn)的？

Go 1.17中你就可以使用泛型了，可以參考我3月份的文章:Go 泛型嘗鮮, 編譯的時候需要加-gcflags=-G=3參數，而當前master分支，默認已經支持泛型，不需要加-G=3參數了。

你可以通過下面的步驟嘗試go最新分支:

go get golang.org/dl/gotip
gotip download

編譯代碼的時候使用gotip替換go命令即可。

隨著Go 1.17的發(fā)布，最近也涌現(xiàn)了很多的介紹Go泛型的文章，基本上都是簡單介紹的文章。

最近Go泛型的變化是增加了兩個操作符: ~和|：

• an approximation element~T restricts to all types whose underlying type is T: 代表底層類型是T
• a union element T1 | T2 | ... restricts to any of the listed elements: 代表或,類型列表之一。這些不是我想介紹的內容，今天我肝一篇介紹Go泛型實現(xiàn)原理的文章，介紹Go泛型實現(xiàn)的方案。

對于一個函數func Echo[T any](t T){}，Go編譯器到底編譯成了什么代碼？

簡單的說，當前Go泛型實現(xiàn)的方案和下圖中的方案一樣：

在國內的老破小小區(qū)的樓道中常見的一種高科技印刷技術，通過一個鏤花模板，為每一種類型生成特化的類型，這個術語叫做stenciling。

但是如果再說多一點，那么就應該從 Taylor和Griesemer說起。

Go的泛型有別于其它語言的方案，在Go語言中泛型叫做Type Parameter(類型參數).

Taylor和Griesemer的提案Type Parameters Proposal更多的是泛型呈現(xiàn)形式和影響的思考,對具體的實現(xiàn)涉及甚少。

無論什么編程語言，根據Russ Cox的觀察，實現(xiàn)泛型至少要面對下面三條困境之一,那還是在2009年：

• 拖累程序員:比如C語言，增加了程序員的負擔，需要曲折的實現(xiàn)，但是不對增加語言的復雜性
• 拖累編譯器: 比如C++編程語言，增加了編譯器的負擔，可能會產生很多冗余的代碼，重復的代碼還需要編譯器斟酌刪除，編譯的文件可能非常大。Rust的泛型也屬于這一類。
• 拖累執(zhí)行時間:比如Java，將一些裝箱成Object,進行類型擦除。雖然代碼沒啥冗余了，空間節(jié)省了，但是需要裝箱拆箱操作，代碼效率低。很顯然, Go語言至簡的設計哲學讓它的泛型實現(xiàn)不會選擇增加程序員的負擔的道路，所以它會在第二和第三種方案中做選擇。雖然提案中沒有最終說明它選擇了哪種方案，但是從實際編譯的代碼可以看出，它選擇的是第二種方案。
  
  

Keith H. Randall, MIT的博士，現(xiàn)在在Google/Go team做泛型方面的開發(fā)，提出了Go泛型實現(xiàn)的三個方案：

1.字典

在編譯時生成一組實例化的字典，在實例話一個泛型函數的時候會使用字典進行蠟印(stencile)。

當為泛型函數生成代碼的時候，會生成唯一的一塊代碼，并且會在參數列表中增加一個字典做參數，就像方法會把receiver當成一個參數傳入。字典包含為類型參數實例化的類型信息。

字典在編譯時生成，存放在只讀的data section中。

當然字段可以當成第一個參數，或者最后一個參數，或者放入一個獨占的寄存器。

當然這種方案還有依稀問題，比如字典遞歸的問題，更重要的是，它對性能可能有比較大的影響，比如一個實例化類型int, x=y可能通過寄存器復制就可以了，但是泛型必須通過memmove。

2.蠟印(Stenciling)

或者翻譯成用模板印等。

就像下面的動圖一樣，同一個泛型函數，為每一個實例化的類型參數生成一套獨立的代碼，感覺和rust的泛型特化一樣。

這種方案和上面的字典方案正好相反。

比如下面一個泛型方法:

func f[T1, T2 any](x int, y T1) T2 {
    ...
}

如果有兩個不同的類型實例化的調用：

var a float64 = f[int, float64](7, 8.0)
var b struct{f int} = f[complex128, struct{f int}](3, 1+1i)

那么這個方案會生成兩套代碼：

func f1(x int, y int) float64 {
    ... identical bodies ...
}
func f2(x int, y complex128) struct{f int} {
    ... identical bodies ...
}

因為編譯f時是不知道它的實例化類型的，只有在調用它時才知道它的實例化的類型，所以需要在調用時編譯f。對于相同實例化類型的多個調用，同一個package下編譯器可以識別出來是一樣的，只生成一個代碼就可以了，但是不同的package就不簡單了，這些函數表標記為DUPOK,所以鏈接器會丟掉重復的函數實現(xiàn)。

這種策略需要更多的編譯時間，因為需要編譯泛型函數多次。因為對于同一個泛型函數，每種類型需要單獨的一份編譯的代碼，如果類型非常多，編譯的文件可能非常大，而且性能也比較差。

3.混合方案（GC Shape Stenciling）

混合前面的兩種方案。

對于實例類型的shape相同的情況，只生成一份代碼，對于shape類型相同的類型，使用字典區(qū)分類型的不同行為。

這種方案介于前兩者之間。

啥叫shape?

類型的shape是它對內存分配器/垃圾回收器呈現(xiàn)的方式，包括它的大小、所需的對齊方式、以及類型哪些部分包含指針。

每一個唯一的shape會產生一份代碼，每份代碼攜帶一個字典，包含了實例化類型的信息。

這種方案的問題是到底能帶來多大的收益，它會變得有多慢，以及其它的一些問題。

從當前的反編譯的代碼看，當前Go采用的是第二種方案，盡管名稱中已經帶了shape、dict的標志，或許，Go的泛型方案還在進化之中，進化到第三種方案或者其它方案也不是沒有可能。

接下來我們看一個例子，看看Go泛型的方案是怎么實現(xiàn)的。

下面是一個簡單的例子，有一個泛型函數func echo[T any](t T) string {return fmt.Sprintf("%v", t)},使用不同的幾種實例化類型去調用它，并且使用shape一樣的int32和uint32做為實例化類型。

package generic
import (
 "fmt"
 "time"
)
func echo[T any](t T) string {
 return fmt.Sprintf("%v", t)
}
func Test() {
 echo(0)
 echo(int32(0))
 echo(uint32(0))
 echo(uint64(0))
 echo("hello")
 echo(struct{}{})
 echo(time.Now())
}

反編譯后代碼非常長，精簡如下。編譯的時候禁止優(yōu)化和內聯(lián)，否則實例化的代碼內聯(lián)后看不到效果了。

可以看到函數echo編譯成了不同的函數："".echo[.shape.int]、"".echo[.shape.int32]、"".echo[.shape.uint32]、"".echo[.shape.uint64]、"".echo[.shape.string]、"".echo[.shape.struct{}]、"".echo[.shape.struct{ time.wall uint64; time.ext int64; time.loc *time.Location }]不同的函數，即使shape一樣的類型(int32、uint32)。調用這些函數時，是通過""..dict.echo[uint64]這種方式調用的。

所以我謹慎懷疑，Go的泛型方式在逐步的向第三種方案進化。

# command-line-arguments
"".Test STEXT size=185 args=0x0 locals=0x48 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) TEXT "".Test(SB), ABIInternal, $72-0
 "".Test STEXT size=185 args=0x0 locals=0x48 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) TEXT "".Test(SB), ABIInternal, $72-0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) CMPQ SP, 16(R14)
 0x0004 00004 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-2
 0x0004 00004 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) JLS 175
 0x000a 00010 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-1
 0x000a 00010 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) SUBQ $72, SP
 0x000e 00014 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) MOVQ BP, 64(SP)
 0x0013 00019 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) LEAQ 64(SP), BP
 0x0018 00024 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) FUNCDATA $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
 0x0018 00024 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) FUNCDATA $1, gclocals·54241e171da8af6ae173d69da0236748(SB)
 0x0018 00024 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) LEAQ ""..dict.echo[int](SB), AX
 0x001f 00031 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) XORL BX, BX
 0x0021 00033 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) PCDATA $1, $0
 0x0021 00033 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) CALL "".echo[.shape.int](SB)
 0x0026 00038 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:14) LEAQ ""..dict.echo[int32](SB), AX
 0x002d 00045 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:14) XORL BX, BX
 0x002f 00047 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:14) CALL "".echo[.shape.int32](SB)
 0x0034 00052 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) LEAQ ""..dict.echo[uint32](SB), AX
 0x003b 00059 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) XORL BX, BX
 0x003d 00061 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) NOP
 0x0040 00064 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) CALL "".echo[.shape.uint32](SB)
 0x0045 00069 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:16) LEAQ ""..dict.echo[uint64](SB), AX
 0x004c 00076 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:16) XORL BX, BX
 0x004e 00078 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:16) CALL "".echo[.shape.uint64](SB)
 0x0053 00083 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) LEAQ ""..dict.echo[string](SB), AX
 0x005a 00090 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) LEAQ go.string."hello"(SB), BX
 0x0061 00097 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) MOVL $5, CX
 0x0066 00102 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) CALL "".echo[.shape.string](SB)
 0x006b 00107 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:18) LEAQ ""..dict.echo[struct{}](SB), AX
 0x0072 00114 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:18) CALL "".echo[.shape.struct{}](SB)
 0x0077 00119 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) CALL time.Now(SB)
 0x007c 00124 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ AX, ""..autotmp_0+40(SP)
 0x0081 00129 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ BX, ""..autotmp_0+48(SP)
 0x0086 00134 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ CX, ""..autotmp_0+56(SP)
 0x008b 00139 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ CX, DI
 0x008e 00142 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ BX, CX
 0x0091 00145 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ AX, BX
 0x0094 00148 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) LEAQ ""..dict.echo[time.Time](SB), AX
 0x009b 00155 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) NOP
 0x00a0 00160 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) CALL "".echo[.shape.struct{ time.wall uint64; time.ext int64; time.loc *time.Location }](SB)
 0x00a5 00165 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) MOVQ 64(SP), BP
 0x00aa 00170 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) ADDQ $72, SP
 0x00ae 00174 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) RET
 0x00af 00175 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) NOP
 0x00af 00175 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $1, $-1
 0x00af 00175 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-2
 0x00af 00175 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) CALL runtime.morestack_noctxt(SB)
 0x00b4 00180 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-1
 0x00b4 00180 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) JMP 0
    .................
"".echo[.shape.int] STEXT dupok size=268 args=0x10 locals=0x88 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.int](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00c2 00194 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ DI, SI
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL fmt.Sprintf(SB)
    .................
"".echo[.shape.int32] STEXT dupok size=266 args=0x10 locals=0x88 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.int32](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00bd 00189 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVL $1, DI
 0x00c2 00194 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ DI, SI
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL fmt.Sprintf(SB)
    .................
"".echo[.shape.uint32] STEXT dupok size=266 args=0x10 locals=0x88 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.uint32](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL fmt.Sprintf(SB)
    .................
"".echo[.shape.uint64] STEXT dupok size=268 args=0x10 locals=0x88 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.uint64](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00c2 00194 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ DI, SI
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL fmt.Sprintf(SB)
    .................
"".echo[.shape.string] STEXT dupok size=295 args=0x18 locals=0x88 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.string](SB), DUPOK|ABIInternal, $136-24
 .................
 0x00d6 00214 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $2
 0x00d6 00214 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL fmt.Sprintf(SB)
    .................
"".echo[.shape.struct{}] STEXT dupok size=208 args=0x8 locals=0x88 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.struct{}](SB), DUPOK|ABIInternal, $136-8
 .................
 0x0093 00147 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x0093 00147 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL fmt.Sprintf(SB)
    .................
 0x00cb 00203 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) JMP 0
 .................
"".echo[.shape.struct{ time.wall uint64; time.ext int64; time.loc *time.Location }] STEXT dupok size=364 args=0x20 locals=0xa0 funcid=0x0
 0x0000 00000 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.struct{ time.wall uint64; time.ext int64; time.loc *time.Location }](SB), DUPOK|ABIInternal, $160-32
 .................
 0x00c5 00197 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CMPL runtime.writeBarrier(SB), $0
 0x00cc 00204 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) JEQ 208
 0x00ce 00206 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) JMP 214
 0x00d0 00208 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ AX, 8(CX)
 0x00d4 00212 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) JMP 221
 0x00d6 00214 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL runtime.gcWriteBarrier(SB)
 .................
 0x0167 00359 (/Users/chaoyuepan/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) JMP 0
 
...............
"".echo[.shape.string].stkobj SRODATA static size=32
 .......
"".echo[.shape.string].arginfo1 SRODATA static dupok size=9
 .......           ..........
"".echo[.shape.struct{}].stkobj SRODATA static size=32
 .......
"".echo[.shape.struct{}].arginfo1 SRODATA static dupok size=5
 .......
"".echo[.shape.struct{ time.wall uint64; time.ext int64; time.loc *time.Location }].stkobj SRODATA static size=56
 ......
"".echo[.shape.struct{ time.wall uint64; time.ext int64; time.loc *time.Location }].arginfo1 SRODATA static dupok size=11
 0x0000 00 08 fe 08 08 10 08 18 08 fd ff                 ...........

泛型的性能 寫一個簡單的benchmark程序，沒看到明顯的性能變化。

package bench_test
import (
 "fmt"
    "testing"
)
func BenchmarkAdd_Generic(b *testing.B) {
 for i := 0; i < b.N; i++ {
  add(i, i)
 }
}
func BenchmarkAdd_NonGeneric(b *testing.B) {
 for i := 0; i < b.N; i++ {
  addInt(i, i)
 }
}
type Addable interface {
 int
}
func add[T Addable](a, b T) T {
 return a + b
}
func addInt(a, b int) int {
 return a + b
}
func main() {
 fmt.Println(add(1, 2))
 fmt.Println(addInt(1, 2))
}

• https://github.com/golang/proposal/blob/master/design/generics-implementation-dictionaries.md
• https://github.com/golang/proposal/blob/master/design/generics-implementation-gcshape.md
• https://github.com/golang/proposal/blob/master/design/generics-implementation-stenciling.md
• https://github.com/golang/proposal/blob/master/design/43651-type-parameters.md
• https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/view#