- read

Golang Generics Implementation Details

Amirreza askarpour 35

In this article, we discuss Golang generic implementations.

Golang generics was probably the most wanted feature in the Golang community since 1.0 when they announced that they are going to bring generics to Go, discussions on generic implementation started, we will discuss the two most popular implementations and finally current Go1.18 implementation.

Stenciling

Stenciling is one of the approaches we can take when implementing generics in a compiler, in this approach if we have a generic function like

func max[T comparable](a, b T) bool {
if a > b {
return a
} else {
return b
}
}

for every call in our codebase the compiler would come and generate a new instance of this function just for that call so for example:

max[int](1,2) // this will generate something like max_int_1
max[float32)(1.0, 2.0) // this will generate something like max_float32_1
max[int](3,4) // this will also generate a new max_int_2

As you can see in this approach we have to generate an instance of the function for each call and even when instances are the same or similar we have duplicates.

Note that stenciling gives the best runtime performance but has long compile times and fat binaries. C++ uses this approach.

Dictionaries

using dictionaries is another approach for having generics in a compiler. Dictionaries is the complete opposite of Stenciling since it would just have a singular instance of the function and all needed information about type parameters are passed in a dictionary structure to that function.

func max[T comparable](a, b T) bool {
if a > b {
return a
} else {
return b
}
}

consider code above as a generic max function.

max[int](1,2)
max[float32)(1.0, 2.0)
max[int](3,4)

all calls above are to the same instance of the max function and just the dictionary data is different, for example for the first call dictionary contains that the type is int and some other information about how internal functionalities like make/len/new/etc... should work for ints.

This approach has the lowest performance in runtime since every generic call needs to have that dictionary created and filled and functions also need to access that dictionary for most of their operations. This approach generates less assembly code and smaller binaries, but compiler code is much more complex that Stenciling .

Go implementation

Golang implementation is basically a middle ground between the two above methods. Go generics introduce us to a concept called GCShape which is basically a group of types that are similar, types that have the same underlying type, or types that are pointer types are in the same GCShape group, for example:

type a int
type b int
type c = int
// above are same GCShape

remember that types that are in the same GCShape should have the completely same behavior for all internal compiler operations, for example for + operator, they should behave the same so because of that even int16 and int32 are not in the same GCShape. Go compiler creates a GCShape type when sees a type parameter that does not belong to any GCShape so for example for a string it would create go.shape.string_0 , note that 0 means that it’s the first type parameter.

Go compiler does stenciling for each GCShape instead of each generic call and then at each call site creates a dictionary containing type information for that concrete type and then calls the function so when types are in the same GCShapethey share the same instance of the function.

so for the same max function, we had

max[int](1,2)
max[int](3,4)

function calls above share the same instance of the function. function call below also shares that same instance since the underlying type is int and we can do all internal compiler operations the same as int itself, note that the dictionary created for calls above is different from the dictionary created for the call below since they are different types but since they are in the same GCShape the can share the same instance of the generic function.

type a int
max[a](1,2)

You can see Golang implementation flow in picture below as well

As you can see Go1.18 implementation of generics is the best of both worlds, it compiles fast and also does not produce fat binaries. It has limitations as they announced in release notes of Go1.18.

Generics are the biggest feature and change to the Go language. We should see more and more usages of generics every day since they make codes that were impossible to write possible.