【Go1.18】泛型的实现

本文主要探索一下Go1.18中泛型的实现。说到泛型，我们很自然地会想到基于模板的代码生成，尤其是有过C++经验的同学。我们习惯认为泛型函数就是个模板，等到真正使用的时候，编译器会根据不同的类型实参来生成多套代码。

比如对于只有一个类型参数的泛型函数，代码中有两个地方会调用它，并且传递了不同的类型参数，我们就会认为编译器会生成两套代码，分别对应这两种类型参数。Go的泛型是这样实现的吗？且看下文分解。

实践是检验真理的唯一标准，所以我们就实际写个泛型函数来验证一下。如下代码给出了一个只有一个类型参数的泛型函数，并且分别用两种类型参数来调用它：

package main
import (    "fmt")
func Print[T any](v T) {    fmt.Printf("%T: %[1]v\n", v)}
type Int int
func main() {    Print(1)    Print(Int(1))}

首先来看一下运行效果，使用go1.18进行编译，然后运行得到的可执行文件，输出结果如下所示：

$ ./main.exe int: 1main.Int: 2

按照惯例，接下来我会查看一下可执行文件的main包中都有什么东西：

$ go tool nm main.exe | grep ' main\.'  4c7a28 R main..dict.Print[int]  4c7a30 R main..dict.Print[main.Int]  525060 D main..inittask  48c9e0 T main.Print[go.shape.int_0]  48c980 T main.main

除了main函数之外，数据段中的这个inittask我们之前分析过了，是包依赖初始化要用的数据结构。值得注意的是Print函数，并没有像我们猜想的那样生成两套代码。我们原本以为应该生成一个main.Print[int]函数和一个main.Print[main.Int]函数，但是却只发现了一个main.Print[go.shape.int_0]函数，而且函数名字还这么奇怪。在只读数据段里有两个dict，看起来跟Print函数也有些关系。为了弄清楚它们之间的关系，我们反编译一下main函数，调用Print函数的两段汇编代码如下所示：

// Print(1)LEAQ main..dict.Print[int](SB), AXMOVL $0x1, BXCALL main.Print[go.shape.int_0](SB)
// Print(Int(2))LEAQ main..dict.Print[main.Int](SB), AXMOVL $0x2, BXCALL main.Print[go.shape.int_0](SB)

我们可以看到，这两次调用的都是main.Print[go.shape.int_0]这个函数。通过新版调用约定的寄存器传参规则，可以反推出来，这个函数有两个参数，第一个是个dict的地址，第二个应该是个整型参数。这两次调用分别使用了不同的dict，说明这个dict和实际的类型参数相关。进行到这里出现了很多新东西，为了提高后续探索研究的效率，我们需要先理解相关的设计思想。下面就来看一下go1.18中泛型实现相关的Proposal。

Proposal

这篇提案描述了go1.18中如何基于字典和gcshape模板来实现泛型。编译器实现泛型侧重于创建泛型函数和方法的实例，这些函数和方法将使用具体的类型参数来执行。为了避免为具有不同类型参数的每次函数或方法调用都生成一个实例（也就是纯模板），我们在每次泛型函数或方法的调用中都会传递一个字典。在字典里提供了有关类型参数的信息，这样就可以用一个实例支持多种不同的类型参数。

（注：设计者认为纯模板方式会造成代码量暴增，进而影响CPU指令缓存和分支预测的性能）

出于实现起来更简单以及性能方面的考量，我们没有用一个实例来支持所有可能的类型参数。相反，我们让具有相同gcshape的一组类型参数共享一个实例。

Gcshapes

我们所说的gcshape代表了一组类型，单从名字来看似乎和GC有关，你可能会想到内存布局中的标量和指针，事实上还要更严格一些。在目前的实现中，如果两个类型有着同样的底层类型，或者它们都是指针类型，那么他们就属于同一个gcshape。

这样设计的好处是，不需要在字典中包含运算符方法（例如，对于不同宽度的整型，加法运算符+对应的机器指令也不太一样）。同样，一个 gcshape 中的所有类型始终以相同的方式实现内置方法（例如make、new和len）。接口类型和非接口类型属于不同的gcshape，即使非接口类型有着和接口相同的双指针结构，因为在调用方法时它们的行为差异很大。

在命名方面，所有的gcshape都会被放置到内置包go.shape中。由于实现方面的原因，我们根据类型参数在列表出现的顺序，为相应的gcshape类型加上序号后缀。因此，当一个底层是string类型的类型参数出现在列表中第一个位置时，就会被命名为go.shape.string_0，出现在第二个位置时就会被命名为go.shape.string_1，以此类推。所有的指针类型都作为*uint8类型来命名，也就是go.shape.*uint8_0以及go.shape.*uint8_1等。

我们把一个泛型函数或方法针对一组shape类型参数的实例化，称为shape实例化。

字典格式

字典是在编译阶段静态确定的，与泛型函数或方法的调用以及调用时具体的类型实参相对应。调用一个函数或方法需要传递对应的字典，字典根据被调用的泛型函数或方法的完全限定名称和具体的类型参数来命名，比如上面的main..dict.Print[int]和main..dict.Print[main.Int]。字典中包含了调用一个泛型函数或方法的shape实例所需的具体类型参数信息，有着相同名字的字典会被编译器和链接器去重。

为了创建所需的字典，我们需要把shape类型参数替换为真正的类型参数，这就要求shape类型参数完全可区分。类型参数列表中可能有多个shape参数有着相同的类型，所以我们才要按照它们的顺序给它们加上编号后缀，这样就确保了不同shape参数间完全可区分。

接下来我们就一边参照Proposal一边实践，来看一下字典中到底包含哪些内容。go1.18的编译器在开发的时候，内置了打印字典相关调试信息的代码，只不过在发布的时候用一个布尔变量把这部分逻辑关闭掉了，我们可以再把它打开。在src/cmd/compile/internal/noder/stencil.go的第32行有个infoPrintMode变量，它的默认值是false，把它改成true，然后执行src下的buildall.bash来重新构建编译器。用构建好的编译器来编译泛型代码，就能够看到生成了哪些字典，以及各个字典的结构。下面，我们实际看一下组成字典的4大部分：

第一部分，具体类型参数

这一区间包含了用来调用泛型函数或方法的类型参数的类型信息，也就是对应的runtime._type的地址。比如，build如下代码：

package main
import (    "fmt")
func Print[T any](v T) {    fmt.Printf("%T: %[1]v\n", v)}
type Int int
func main() {    Print(Int(2))}

编译器输出的调试信息如下所示：

$ go build main.go# command-line-arguments>>> InstInfo for Print[go.shape.int_0]  Typeparam go.shape.int_0>>> Done Instinfo=== Creating dictionary .dict.Print["".Int] * IntMain dictionary in main at generic function call: Print - (<node FUNCINST>)(Int(2))=== Finalizing dictionary .dict.Print["".Int]=== Finalized dictionary .dict.Print["".Int]

函数Print[go.shape.int_0]有一个shape类型参数go.shape.int_0，后缀0表明这是第一个类型参数。在创建字典.dict.Print["".Int]的时候，只包含了一项，也就是Int类型的类型元数据地址。有兴趣的话，可以反编译一下main.Print[go.shape.int_0]这个函数，你会发现fmt.Printf之所以能够打印出类型的名称，就是因为这个字典传递了对应的类型元数据信息。

第二部分，派生类型信息

这种情况所描述的，就是泛型函数或方法中基于类型参数创建了新的类型，比如*T、[]T和map[K,V]等，并且我们需要用到这些派生类型的动态类型信息（类型元数据）。比如显式或隐式的转换为空接口类型interface{}，或者作为type switch或类型断言的目标类型等。简单起见，我们就来测试一个[]T的示例，对上一段代码稍作修改，只是改动了fmt.Printf的第二个参数：

func Print[T any](v T) {    fmt.Printf("%T: %[1]v\n", []T{v})}

再次编译输出的调试信息如下：

$ go build main.go # command-line-arguments>>> InstInfo for Print[go.shape.int_0]  Typeparam go.shape.int_0  Derived type []go.shape.int_0>>> Done Instinfo=== Creating dictionary .dict.Print["".Int] * Int - []IntMain dictionary in main at generic function call: Print - (<node FUNCINST>)(Int(2))=== Finalizing dictionary .dict.Print["".Int]=== Finalized dictionary .dict.Print["".Int]

明显看到Print[go.shape.int_0]函数多出来一个派生的shape类型参数，字典中也相应的包含了[]Int对应的类型信息，实际上也是类型元数据的地址。这个例子说明，连派生类型的类型信息都是要由调用者来准备好。

第三部分，子字典区间

所谓子字典sub-dictionaries，也就是当前这个泛型函数或方法又调用其他泛型函数或方法时，这些子调用所需要传递的字典。没错，这也是需要从外层一起生成并传递进来的。我们重写一下上面的例子，加上嵌套的泛型函数调用：

package main
import (    "fmt")
func Print[T any](v T) {    fmt.Printf("%T: %[1]v\n", v)}
func PrintSlice[T any](s []T) {    for i := 0; i < len(s); i++ {        Print(s[i])    }}
type Int int
func main() {    PrintSlice([]Int{1, 2})}

这次编译后输出的调试信息如下所示：

$ go build main.go # command-line-arguments>>> InstInfo for PrintSlice[go.shape.int_0]  Typeparam go.shape.int_0  Subdictionary at generic function/method call: Print - (<node FUNCINST>)(s[i])  Derived type []go.shape.int_0  Derived type func(go.shape.int_0)>>> Done Instinfo=== Creating dictionary .dict.PrintSlice["".Int] * Int - []Int - func(Int)=== Creating dictionary .dict.Print["".Int] * Int>>> InstInfo for Print[go.shape.int_0]  Typeparam go.shape.int_0>>> Done Instinfo - Subdict .dict.Print["".Int]Main dictionary in main at generic function call: PrintSlice - (<node FUNCINST>)([]Int{...})Sub-dictionary in PrintSlice[go.shape.int_0] at generic function call: Print - (<node FUNCINST>)(s[i])=== Finalizing dictionary .dict.Print["".Int]=== Finalized dictionary .dict.Print["".Int]=== Finalizing dictionary .dict.PrintSlice["".Int]=== Finalized dictionary .dict.PrintSlice["".Int]

先来看看函数PrintSlice[go.shape.int_0]的实例化信息，除了我们意料之中的subdictionary和派生类型[]go.shape.int_0，连它调用的另一个泛型函数也有一个派生类型func(go.shape.int_0)与之对应。字典.dict.PrintSlice["".Int]中包含了一个类型参数信息，两个派生类型信息，还有一个子字典。子字典的结构比较简单，我们就不再展开说明了。

第四部分，itab区间

存在这个区间主要是因为，我们的泛型函数或方法中，可能会存在从类型参数以及其派生类型到一种非空接口类型的转换，或者从一个非空接口到类型参数及其派生类型的类型断言等。这种情况下就需要用到相应itab的地址，这也要从外层准备好并传递给被调用的泛型函数或方法，后者从字典中取出并使用。为了展示这种情况，我们再修改一下上面的例子：

package main
import (    "fmt"    "strconv")
func Print[T fmt.Stringer](v T) {    fmt.Printf("%T: %[1]v\n", v.String())}
func PrintSlice[T fmt.Stringer](s []T) {    for i := 0; i < len(s); i++ {        Print(s[i])    }}
type Int int
func (n Int) String() string {    return strconv.Itoa(int(n))}
func main() {    PrintSlice([]Int{1, 2})}

我们把两个泛型函数中类型参数的约束条件都改成了fmt.Stringer接口，这就让我们可以在Print函数中调用v的String方法。注意，必须要用代码显式调用，这样才是泛型，被fmt.Printf隐式调用的话，那是接口的动态派发。编译上述代码，得到的调试输出如下所示：

$ go build main.go # command-line-arguments>>> InstInfo for PrintSlice[go.shape.int_0]  Typeparam go.shape.int_0  Subdictionary at generic function/method call: Print - (<node FUNCINST>)(s[i])  Derived type []go.shape.int_0  Derived type func(go.shape.int_0)>>> Done Instinfo=== Creating dictionary .dict.PrintSlice["".Int] * Int - []Int - func(Int)=== Creating dictionary .dict.Print["".Int] * Int>>> InstInfo for Print[go.shape.int_0]  Typeparam go.shape.int_0  Optional subdictionary at generic bound call: v.String()  Itab for bound call: v.String>>> Done Instinfo - Unused subdict entry - Subdict .dict.Print["".Int]Main dictionary in main at generic function call: PrintSlice - (<node FUNCINST>)([]Int{...})Sub-dictionary in PrintSlice[go.shape.int_0] at generic function call: Print - (<node FUNCINST>)(s[i])=== Finalizing dictionary .dict.Print["".Int] + Itab for (Int,fmt.Stringer)=== Finalized dictionary .dict.Print["".Int]=== Finalizing dictionary .dict.PrintSlice["".Int]=== Finalized dictionary .dict.PrintSlice["".Int]

与上个例子相比，字典.dict.PrintSlice["".Int]的结构没什么变化，但是子字典.dict.Print["".Int]中增加了一个对应(Int,fmt.Stringer)的itab。如果反编译一下函数Print[go.shape.int_0]，你会发现调用v的String方法时，是从字典中的itab里取得的方法地址。至于接收者，是在栈上分配的一个副本，实际传递了这个副本的地址。你可能会觉得，这不就是接口的动态派发吗？这两者还是有些不同的，我们后续慢慢探索。

小节

本文参考了go1.18泛型实现的Proposal，也就是基于字典和gcshape模板的泛型实现，解释了gcshape的含义，并探索了字典的格式（包含哪些信息），让大家对go1.18中泛型的实现能有一个大体上的了解。如果只是采用纯模板的方式，为每种类型参数组合生成一套代码，那就很好理解了，也就不需要再讲什么。

最后总结几句，Go把拥有相同底层类型的所有类型归为一组，并让它们共享同一个函数或方法实例（机器码层面），为了让这个共享的实例中能够区分实际的参数类型，就通过字典的形式把类型信息传进去。

好了，本文就到这里~

欢迎扫描下方二维码

或微信搜索：KylinLabs

添加作者微信^~^

接受邀请加入交流群~