Go 泛型是怎麼實現的?

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 的發佈，最近也湧現了很多的介紹 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 泛型實現原理的文章，介紹 Go 泛型實現的方案。

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

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

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

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

Go 泛型提案中關於泛型實現的介紹

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

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

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

• 拖累程序員: 比如 C 語言，增加了程序員的負擔，需要曲折的實現，但是不對增加語言的複雜性
• 拖累編譯器: 比如 C++ 編程語言，增加了編譯器的負擔，可能會產生很多冗餘的代碼，重複的代碼還需要編譯器斟酌刪除，編譯的文件可能非常大。Rust 的泛型也屬於這一類。
• 拖累執行時間: 比如 Java，將一些裝箱成 Object, 進行類型擦除。雖然代碼沒啥冗餘了，空間節省了，但是需要裝箱拆箱操作，代碼效率低。

很顯然, Go 語言至簡的設計哲學讓它的泛型實現不會選擇增加程序員的負擔的道路，所以它會在第二和第三種方案中做選擇。雖然提案中沒有最終說明它選擇了哪種方案，但是從實際編譯的代碼可以看出，它選擇的是第二種方案。

三個方案

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

字典

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

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

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

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

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

蠟印 (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, 所以鏈接器會丟掉重複的函數實現。

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

混合方案（GC Shape Stenciling）

混合前面的兩種方案。

對於實例類型的 shape 相同的情況，只生成一份代碼，對於 shape 類型相同的類型，使用字典區分類型的不同行爲。

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

啥叫shape?

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

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

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

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

接下來我們看一個例子，看看 Go 泛型的方案是怎麼實現的。

例子

下面是一個簡單的例子，有一個泛型函數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())
}

反編譯後代碼非常長，精簡如下。編譯的時候禁止優化和內聯，否則實例化的代碼內聯後看不到效果了。

可以看到函數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))
}

參考文檔

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://colobu.com/2021/08/30/how-is-go-generic-implemented/?hmsr=toutiao.io&utm_campaign=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io