Loading...
墨滴

盘胧

2021/09/06  阅读:33  主题:全栈蓝

golang-泛型(新版本future)

Go 泛型是怎么实现的

Go1.17中可以使用泛型.

新增的两个操作符:~| ⭐️ ~T 代表底层类型是T ⭐️ T1|T2|... 代表

go 泛型实现原理

例一个函数:func Echo[T any](t T){},go编译器到底编译成了什么?

两个名词:

  • 术语:stenciling - 蜡印
  • taylor 和 Griesemer

官网说法:有别于其他语言的实现,go语言的泛型叫做Type Parameter(类型参数)

taylor 和 Griesemer 的提案对type parameters proposal更多的是对泛型呈现形式和影响的思考,具体实现倒是涉及比较少

以前编程语言实现泛型的难处:

  • 拖累程序猿:曲折的实现,fuck
  • 拖累编译器:可能产生很多冗余代码,编译文件可能很大
  • 拖累执行时间: 看看java,需要增加装箱和拆箱的操作,烦不烦

go 要兼具python的优雅和简单的设计哲学——其实就是go自己的哲学,自然不能选择让程序员负担更重,从实际编译代码来看——选择的是第二种

看下go提案的三种解决方案,再看看为什么选择第二种

字典:

编译的时候产生一组实例化的字典,在实例化一个泛型函数的时候会使用字典进行蜡印(stencile)。当为泛型函数生成代码的时候,会生成唯一的一块代码,并且会在参数列表中增加一个字典做参数,就行方法会把reciver当成一个参数传入。字典包含为类型参数为实例化的类型信息。字典在编译时生成,存放在只读的data section中,当然字段可以当成第一个参数,或者最后一个参数,或者放入一个独占的寄存器。当然这种方案还有依赖问题,比如字典递归的问题,更重要的是,它对性能可能有比较大的影响,比如一个实例化类型int, x=y可能通过寄存器复制就可以了,但是泛型必须通过memmove

蜡印(Stenciling)

同一个泛型函数,为每一个实例化的类型参数生成一套独立的代码,就很像类型泛化。这种方案和上面的字典方案正好相反。 比如下面的泛型方法:

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

如果有两个不同的类型实例化的调用:

var a float64 = f[intfloat64](78.0)
var b struct{f int} = f[complex128struct{f int}](31+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泛型的方案是怎么实现的。

泛型实现

demo:

有一个泛型函数func echo[T any](t T) string {return fmt.Sprintf("%v", t)},使用不同的几种实例化类型去调用它,并且使用shape一样的int32uint32做为实例化类型

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 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) TEXT "".Test(SB), ABIInternal, $72-0
 0x0000 00000 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) CMPQ SP, 16(R14)
 0x0004 00004 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-2
 0x0004 00004 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) JLS 175
 0x000a 00010 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-1
 0x000a 00010 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) SUBQ $72, SP
 0x000e 00014 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) MOVQ BP, 64(SP)
 0x0013 00019 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) LEAQ 64(SP), BP
 0x0018 00024 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) FUNCDATA $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
 0x0018 00024 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) FUNCDATA $1, gclocals·54241e171da8af6ae173d69da0236748(SB)
 0x0018 00024 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) LEAQ ""..dict.echo[int](SB), AX
 0x001f 00031 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) XORL BX, BX
 0x0021 00033 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) PCDATA $1, $0
 0x0021 00033 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:13) CALL "".echo[.shape.int](SB)
 0x0026 00038 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:14) LEAQ ""..dict.echo[int32](SB), AX
 0x002d 00045 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:14) XORL BX, BX
 0x002f 00047 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:14) CALL "".echo[.shape.int32](SB)
 0x0034 00052 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) LEAQ ""..dict.echo[uint32](SB), AX
 0x003b 00059 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) XORL BX, BX
 0x003d 00061 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) NOP
 0x0040 00064 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:15) CALL "".echo[.shape.uint32](SB)
 0x0045 00069 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:16) LEAQ ""..dict.echo[uint64](SB), AX
 0x004c 00076 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:16) XORL BX, BX
 0x004e 00078 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:16) CALL "".echo[.shape.uint64](SB)
 0x0053 00083 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) LEAQ ""..dict.echo[string](SB), AX
 0x005a 00090 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) LEAQ go.string."hello"(SB), BX
 0x0061 00097 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) MOVL $5, CX
 0x0066 00102 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:17) CALL "".echo[.shape.string](SB)
 0x006b 00107 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:18) LEAQ ""..dict.echo[struct{}](SB), AX
 0x0072 00114 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:18) CALL "".echo[.shape.struct{}](SB)
 0x0077 00119 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) CALL time.Now(SB)
 0x007c 00124 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ AX, ""..autotmp_0+40(SP)
 0x0081 00129 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ BX, ""..autotmp_0+48(SP)
 0x0086 00134 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ CX, ""..autotmp_0+56(SP)
 0x008b 00139 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ CX, DI
 0x008e 00142 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ BX, CX
 0x0091 00145 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) MOVQ AX, BX
 0x0094 00148 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) LEAQ ""..dict.echo[time.Time](SB), AX
 0x009b 00155 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:19) NOP
 0x00a0 00160 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) MOVQ 64(SP), BP
 0x00aa 00170 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) ADDQ $72, SP
 0x00ae 00174 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) RET
 0x00af 00175 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:20) NOP
 0x00af 00175 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $1, $-1
 0x00af 00175 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-2
 0x00af 00175 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) CALL runtime.morestack_noctxt(SB)
 0x00b4 00180 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:12) PCDATA $0, $-1
 0x00b4 00180 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.int](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00c2 00194 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ DI, SI
 0x00c5 00197 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.int32](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00bd 00189 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVL $1, DI
 0x00c2 00194 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ DI, SI
 0x00c5 00197 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.uint32](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00c5 00197 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.uint64](SB), DUPOK|ABIInternal, $136-16
 .................
 0x00c2 00194 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ DI, SI
 0x00c5 00197 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x00c5 00197 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.string](SB), DUPOK|ABIInternal, $136-24
 .................
 0x00d6 00214 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $2
 0x00d6 00214 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:8) TEXT "".echo[.shape.struct{}](SB), DUPOK|ABIInternal, $136-8
 .................
 0x0093 00147 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) PCDATA $1, $0
 0x0093 00147 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL fmt.Sprintf(SB)
    .................
 0x00cb 00203 (/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 (/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 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CMPL runtime.writeBarrier(SB), $0
 0x00cc 00204 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) JEQ 208
 0x00ce 00206 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) JMP 214
 0x00d0 00208 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) MOVQ AX, 8(CX)
 0x00d4 00212 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) JMP 221
 0x00d6 00214 (/go/src/github.com/smallnest/study/type_parameter/generic/generic.go:9) CALL runtime.gcWriteBarrier(SB)
 .................
 0x0167 00359 (/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                 ...........

泛型的性能


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(12))
 fmt.Println(addInt(12))
}

性能没有看到明显的变化。。。

参考文档

  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#

盘胧

2021/09/06  阅读:33  主题:全栈蓝

作者介绍

盘胧