To understand the performance of generics and their implementation in Go, you first need to understand the two most common ways of implementing generics in general.
One way of implementing generics into a compiler is to use a virtual method table. The generic function is modified in a way that it only accepts pointers as arguments. The values are then allocated on the heap, and pointers to these values are passed to the generic function. This works because a pointer always looks the same, regardless of the type it is pointing to.
If those values are objects, and the generic function needs to invoke methods of these objects, it can’t do so any longer. The function only has a pointer to the objects and doesn’t know where their methods live. Consequently, it needs a table where the memory addresses of the methods can be looked up: the virtual method table. This so-called dynamic dispatch was already being used by interfaces in Go and languages like Java.
Virtual method tables may not only be used to implement generics, but also other kinds of polymorphism. However, dereferencing those pointers and invoking virtual functions is slower than calling the functions directly, and using virtual method tables prevents the compiler from performing optimizations.
A much simpler approach is monomorphization, where the compiler generates a copy of the generic function for each data type it is invoked with.
func max[T Numeric](a, b T) T {
// ...
}
larger := max(3, 5)
Since the max function shown above is invoked with two integers, the compiler will generate a copy of max for int when monomorphizing the code:
func maxInt(a, b int) int {
// ...
}
larger := maxInt(3, 5)
The great advantage is that monomorphization results in significantly better runtime performance than using virtual method tables. Not only are direct method calls more efficient, they also enable a whole chain of compiler optimizations. The price for this has to be paid at compile time, though. Generating copies of the generic function for all relevant types is time-consuming.
Which of these two approaches is best suited for Go? Fast compilation is important, but so is runtime performance. To meet these demands, the Go team decided to take a hybrid approach when implementing generics.
Go uses monomorphization, but tries to reduce the number of function copies that need to be generated. Instead of creating a copy per type, it generates a copy per layout in memory: int, float64, Node, and other so-called “value types” all look different in memory, hence the generic function will be copied for all of these types.
In contrast to value types, pointers and interfaces always have the same layout in memory. The compiler will generate one copy of the generic function for calls with pointers and interfaces. Just as with virtual method tables, the generic function receives pointers and therefore needs a table for dynamically looking up method addresses. What’s referred to as dictionaries in the Go implementation comes with the same performance characteristics of virtual method tables.
The consequence of this hybrid approach is that you get the performance benefits of monomorphization for calls with value types, and pay the costs of virtual method tables for calls with pointers or interfaces.
What’s often been missed out in the performance discussions is that all these benefits and costs only concern the invocation of a function. Usually, most of the execution time is spent inside the function. The performance overhead of calling methods probably won’t be a bottleneck for you, and even if it is, consider optimizing the function body first.