You can use generics in Go 1.17. The current master branch, by default, already supports generics, so you don’t need to add the -G=3 parameter.

You can try the latest branch of go by following these steps:

1
2

go get golang.org/dl/gotip
gotip download

Just use the gotip command instead of go when compiling your code.

With the release of Go 1.17, there have been a lot of articles on Go generics, but they are basically brief introductory articles.

The most recent change to Go generics is the addition of two operators: ~ and |.

  • an approximation element ~T restricts to all types whose underlying type is T.
  • a union element T1 | T2 | ... restricts to any of the listed elements.

These are not what I want to cover, today I am writing an introduction to the principles of Go generic implementation and introducing the Go generic implementation scheme.

For a function func Echo[T any](t T){}, what exactly does the Go compiler compile into the code?

In short, the current scheme of the Go generic implementation is the same as the one in the following diagram.

A high-tech printing technique, common in the hallways of old, dilapidated neighbourhoods in China, generates specialised types for each type by means of an openwork template, a term called stenciling.

But if there is more to it, then it is time to start with Taylor and Griesemer.

Introduction to the Go generic implementation in the Go generic proposal

Go’s generics differ from the schemes of other languages in that they are called Type Parameter (type parameters).

Taylor and Griesemer’s proposal Type Parameters Proposal is more of a reflection on the form and implications of generic presentation, with very little on concrete implementation.

Regardless of the programming language, according to Russ Cox’s observations, implementations of generics face at least one of the following three dilemmas, and that was back in 2009.

  • dragging down the programmer: e.g. C, adding to the programmer’s burden, requiring convoluted implementation, but not to the complexity of the language
  • Rust’s generics also fall into this category.
  • Rust’s generics also fall into this category. Although the code is less redundant and space is saved, it requires boxing and unboxing, which makes the code inefficient.

Obviously, the Go language’s philosophy of minimalist design means that its generic implementation will not choose the path of increasing the burden on the programmer, so it will choose between the second and third option. Although the proposal does not ultimately state which option it chooses, the actual compiled code shows that it chooses the second option.

Three options

Keith H. Randall, PhD at MIT, now working on the Google/Go team on generic development, has proposed three options for a Go generic implementation.

Dictionary

A set of instantiated dictionaries is generated at compile time, and the dictionaries are waxed (stencile) when instantiating a generic function.

When code is generated for a generic function, a unique piece of code is generated and a dictionary is added to the argument list as an argument, just as a method will pass in a receiver as an argument. The dictionary contains the type information instantiated for the type parameter.

The dictionary is generated at compile time and is stored in a read-only data section.

The field can of course be taken as the first argument, or the last argument, or put into an exclusive register.

There are of course dependency issues with this solution, such as the recursion of dictionaries, and more importantly, it can have a relatively large impact on performance, for example an instantiated type int , x=y might be fine by register copying, but a generic type must be copied by memmove.

Stenciling

As in the following motion picture, the same generic function generates a separate set of code for each instantiated type parameter, which feels the same as the generic specialisation of rust.

This solution is the opposite of the dictionary solution above.

For example, the following generic method:

1
2
3

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

If there are two different types instantiated by the call.

1
2

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

This option would then generate two sets of code.

1
2
3
4
5
6

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

For multiple calls of the same instantiation type, the compiler recognises that they are the same under the same package and generates only one piece of code, but it is not so simple for different packages, where the function table is marked as DUPOK, so the linker will throw away duplicate function implementations.

This strategy takes more time to compile, as the generic functions need to be compiled several times. Because each type requires a separate piece of compiled code for the same generic function, if there are very many types, the compiled file can be very large and the performance is poor.

GC Shape Stenciling

Mix the two previous options.

For instance types with the same shape, only one copy of the code is generated, and for types with the same shape type, a dictionary is used to distinguish between the different behaviours of the types.

This solution is somewhere in between.

What does shape mean?

The shape of a type is how it is presented to the memory allocator/garbage collector, including its size, the required alignment, and which parts of the type contain pointers.

Each unique shape produces one copy of code, each carrying a dictionary containing information about the instantiated type.

The problem with this solution is how much benefit it actually brings, how slow it can become, and a number of other issues.

From the current decompiled code, it appears that Go is currently using the second scheme, despite the shape and dict flags in the name, so perhaps Go’s generalisation scheme is still evolving, and it is not impossible to evolve to the third or other schemes.

Let’s look at an example to see how the Go generic scheme is implemented.

Example

Here is a simple example with a generic function func echo[T any](t T) string {return fmt.Sprintf("%v", t)} , which is called using several different instantiated types and using shape-like int32 and uint32 as the instantiated types.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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())
}

The decompiled code is very long and is streamlined as follows. Compile with optimization and inlining disabled, otherwise the instantiated code will not be visible after inlining.

You can see that the function echo is compiled into different functions: "".echo[.shape.int], "".echo[.shape.int32], "".echo[.shape.uint32], "".echo[.shape.uint64], "".echo[.shape.string], "".echo[.shape.string], "".echo[.shape.string], "".echo[.shape.string], "".echo[.shape.string], "".echo[.shape.string], "".echo[.shape.string], "".echo[.shape.string], "". shape.string] , "".echo[.shape.structure{}] , "".echo[.shape.structure{ time.wall uint64; time.ext int64; time.loc *time.Location }] different functions, even if shape of the same type ( int32 , uint32 ). These functions are called with "". .dict.echo[uint64] is called in this way.

So I cautiously suspect that Go’s approach to generics is gradually evolving towards a third option.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

# 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                 ...........

Performance of generic types

Write a simple benchmark program and see no significant change in performance.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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))
}

Reference documents

  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#