Generics

Generics, or more academically known as Parameterized Polymorphism, refers to achieving code reuse and flexibility through type parameterization. In many programming languages, parameterized polymorphism is an important concept that allows functions or data structures to handle different types of data without writing separate code for each type. Originally, Go didn't have generics, but since its inception, the highest demand from the Go community was to add generics. Finally, Go language added support for generics in version 1.18 in 2022.

Design

When designing generics, Go language considered the following approaches:

• stenciling: Monomorphization, typically used in C++ and Rust, generates a copy of template code for each used type. This has the best performance with no runtime overhead, equal to direct calls. The downside is significantly slower compilation speed (compared to Go itself), and since code is generated for each type, it also causes binary file size bloat.
• dictionaries: It only generates one set of code, and at compile time creates a type dictionary stored in the read-only data section, containing all type information that will be used. When calling functions, it queries type information based on the dictionary. This approach doesn't slow down compilation or cause size bloat, but creates huge runtime overhead with poor generic performance.

The above two methods represent two extremes. Go language ultimately chose Gcshape stenciling, a compromise choice. For types with the same memory shape (shape determined by the memory allocator), it uses monomorphization to generate the same code. For example, type Int int and int are actually the same type, so they share one set of code. However, for pointers, although all pointer types have the same memory shape, like *int and *Person, they cannot share the same code because the target type's memory layout is completely different when dereferencing. Therefore, Go also uses dictionaries to get type information at runtime, so Go's generics also have runtime overhead.

Introduction

Let's look at a simple example.

func Sum(a, b int) int {
   return a + b
}

This is a very simple function that adds two int type integers and returns the result. If you want to pass two float64 type floating-point numbers for addition, it obviously won't work because the types don't match. One solution is to define a new function, as follows:

func SumFloat64(a, b float64) float64 {
  return a + b
}

So the question is, if developing a math utility package to calculate the sum of two numbers for all numeric types, do we need to write a function for each type? Obviously not possible. Or we could use any type with reflection to judge, as follows:

func SumAny(a, b any) (any, error) {
  tA, tB := reflect.ValueOf(a), reflect.ValueOf(b)
  if tA.Kind() != tB.Kind() {
    return nil, errors.New("disMatch type")
  }

  switch tA.Kind() {
  case reflect.Int:
  case reflect.Int32:
    ...
  }
}

But this is tedious to write and has poor performance. However, the logic of the Sum function is exactly the same - just adding two numbers. This is where generics come in. So why do we need generics? Generics are to solve problems where execution logic is independent of type. Such problems don't care what type is given, they just need to complete the corresponding operation.

Syntax

The syntax for generics is as follows:

func Sum[T int | float64](a, b T) T {
   return a + b
}

Type Parameter: T is a type parameter. The specific type of the parameter depends on what type is passed in.

Type Constraint: int | float64 constitutes a type constraint. This type constraint specifies which types are allowed, constraining the type range of the type parameter.

Type Argument: Sum[int](1,2), manually specifying the int type, int is the type argument.

The first usage is to explicitly specify which type to use, as follows:

Sum[int](2012, 2022)

The second usage is to not specify the type and let the compiler infer it, as follows:

Sum(3.1415926, 1.114514)

This is a generic slice with type constraint int | int32 | int64:

type GenericSlice[T int | int32 | int64] []T

When using it, the type argument cannot be omitted:

GenericSlice[int]{1, 2, 3}

This is a generic hash map. The key type must be comparable, so the comparable interface is used. The value type constraint is V int | string | byte:

type GenericMap[K comparable, V int | string | byte] map[K]V

Usage:

gmap1 := GenericMap[int, string]{1: "hello world"}
gmap2 := make(GenericMap[string, byte], 0)

This is a generic struct with type constraint T int | string:

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

Usage:

GenericStruct[int]{
   Name: "jack",
   Id:   1024,
}
GenericStruct[string]{
   Name: "Mike",
   Id:   "1024",
}

This is an example of a generic slice parameter:

type Company[T int | string, S []T] struct {
   Name  string
   Id    T
   Stuff S
}

// Can also be written as:
type Company[T int | string, S []int | []string] struct {
  Name  string
  Id    T
  Stuff S
}

Usage:

Company[int, []int]{
   Name:  "lili",
   Id:    1,
   Stuff: []int{1},
}

TIP

In generic structs, this writing style is more recommended:

type Company[T int | string, S int | string] struct {
  Name  string
  Id    T
  Stuff []S
}

SayAble is a generic interface, and Person implements this interface.

type SayAble[T int | string] interface {
   Say() T
}

type Person[T int | string] struct {
   msg T
}

func (p Person[T]) Say() T {
   return p.msg
}

func main() {
  var s SayAble[string]
  s = Person[string]{"hello world"}
  fmt.Println(s.Say())
}

Generic Interface

Generic interfaces can provide better abstraction and constraint capabilities. Here's an example:

func PrintObj[T fmt.Stringer](s T) {
	fmt.Println(s.String())
}

type Person struct {
	Name string
}

func (p Person) String() string {
	return fmt.Sprintf("Person: %s", p.Name)
}

func main() {
	PrintObj(Person{Name: "Alice"})
}

You can also use non-generic interfaces as generic type parameters:

func Write[W io.Writer](w W, bs []byte) (int, error) {
	return w.Write(bs)
}

Generic Assertion

We can use generics to perform type assertion on any type. For example, the following function can assert all types.

func Assert[T any](v any) (bool, T) {
	var av T
	if v == nil {
		return false, av
	}
	av, ok := v.(T)
	return ok, av
}

Type Set

After 1.18, the definition of interface became type set. Interfaces containing type sets are also called General interfaces.

An interface type defines a type set

Type sets can only be used for type constraints in generics, not for type declarations, type conversions, or type assertions. As a set, type sets have empty sets, unions, and intersections. Next, these three situations will be explained.

Union

The interface type SignedInt is a type set. The union of signed integer types is SignedInt, and conversely, SignedInt is their superset.

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

This applies to basic data types as well as other general interfaces:

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnSignedInt interface {
  uint8 | uint16 | uint32 | uint64
}

type Integer interface {
  SignedInt | UnSignedInt
}

Intersection

The type set of a non-empty interface is the intersection of the type sets of all its elements. Translated to human language: if an interface contains multiple non-empty type sets, then that interface is the intersection of these type sets. An example is as follows:

type SignedInt interface {
   int8 | int16 | int | int32 | int64
}

type Integer interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type Number interface {
  SignedInt
  Integer
}

The intersection in the example is definitely SignedInt:

func Do[T Number](n T) T {
   return n
}

Do[int](2)
DO[uint](2) // Cannot compile

Empty Set

An empty set means no intersection. An example is as follows. The Integer in the example below is a type empty set.

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

type UnsignedInt interface {
  uint8 | uint16 | uint | uint32 | uint64
}

type Integer interface {
  SignedInt
  UnsignedInt
}

Because unsigned integers and signed integers definitely have no intersection, the intersection is an empty set. In the example below, no matter what type is passed, it cannot compile.

Do[Integer](1)
Do[Integer](-100)

Empty Interface

An empty interface is different from an empty set. An empty interface is a collection of all type sets, i.e., containing all types.

func Do[T interface{}](n T) T {
   return n
}

func main() {
   Do[struct{}](struct{}{})
   Do[any]("abc")
}

However, we generally use any as a generic parameter because interface{} doesn't look good.

Underlying Type

When using the type keyword to declare a new type, even if its underlying type is included in the type set, it still won't compile when passed in.

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64
}

type TinyInt int8

func Do[T Int](n T) T {
   return n
}

func main() {
   Do[TinyInt](1) // Cannot compile, even though its underlying type is within the Int type set range
}

There are two solutions. The first is to add that type to the type set, but this is meaningless because TinyInt and int8 have the same underlying type. So there's a second solution.

type Int interface {
   int8 | int16 | int | int32 | int64 | uint8 | uint16 | uint | uint32 | uint64 | TinyInt
}

Use the ~ symbol to represent the underlying type. If a type's underlying type belongs to the type set, then that type belongs to the type set, as shown below:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64
}

After modification, it can compile:

func main() {
   Do[TinyInt](1) // Can compile because TinyInt is within the Int type set
}

Notes

Generics cannot be used as a type's basic type

The following is incorrect. Generic parameter T cannot be used as a basic type:

type GenericType[T int | int32 | int64] T

Although the following is allowed, it's meaningless and may cause numeric overflow issues, so it's not recommended:

type GenericType[T int | int32 | int64] int

Generic types cannot use type assertion

Using type assertion on generic types will not compile. Generics are meant to solve type-independent problems. If a problem requires different logic for different types, generics shouldn't be used at all. Use interface{} or any instead.

func Sum[T int | float64](a, b T) T {
   ints,ok := a.(int) // Not allowed
   switch a.(type) { // Not allowed
   case int:
   case bool:
      ...
   }
   return a + b
}

Anonymous structs don't support generics

Anonymous structs don't support generics. The following code won't compile:

testStruct := struct[T int | string] {
   Name string
   Id T
}[int]{
   Name: "jack",
   Id: 1
}

Anonymous functions don't support custom generics

Both of the following won't compile:

var sum[T int | string] func (a, b T) T
sum := func[T int | string](a,b T) T{
    ...
}

But you can use existing generic types, for example in closures:

func Sum[T int | float64](a, b T) T {
  sub := func(c, d T) T {
    return c - d
  }
  return sub(a,b) + a + b
}

Generic methods are not supported

Methods cannot have generic parameters, but the receiver can have generic parameters. The following code won't compile:

type GenericStruct[T int | string] struct {
   Name string
   Id   T
}

func (g GenericStruct[T]) name[S int | float64](a S) S {
   return a
}

Type sets cannot be used as type arguments

Any interface with a type set cannot be used as a type argument.

type SignedInt interface {
  int8 | int16 | int | int32 | int64
}

func Do[T SignedInt](n T) T {
   return n
}

func main() {
   Do[SignedInt](1) // Cannot compile
}

Intersection issues in type sets

For non-interface types, type unions cannot have intersections. For example, in the following example, TinyInt and ~int8 have an intersection.

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // Cannot compile
}

type TinyInt int8

But for interface types, intersections are allowed, as in the following example:

type Int interface {
   ~int8 | ~int16 | ~int | ~int32 | ~int64 | ~uint8 | ~uint16 | ~uint | ~uint32 | ~uint64 | TinyInt // Can compile
}

type TinyInt interface {
  int8
}

Type sets cannot directly or indirectly include themselves

In the following example, Floats directly includes itself, and Double includes Floats, so it indirectly includes itself.

type Floats interface {  // Code cannot compile
   Floats | Double
}

type Double interface {
   Floats
}

comparable interface cannot be included in type sets

Similarly, it cannot be included in type constraints, so it's basically used alone.

func Do[T comparable | Integer](n T) T { // Cannot compile
   return n
}

type Number interface { // Cannot compile
  Integer | comparable
}

type Comparable interface { // Can compile but meaningless
  comparable
}

Method sets cannot be included in type sets

Any interface containing methods cannot be included in type sets:

type I interface {
    int | fmt.Stringer // cannot use fmt.Stringer in union (fmt.Stringer contains methods)
}

But they can be intersected, though this is meaningless:

type I interface {
    int
    fmt.Stringer
}

Usage

Data structures are the most common use case for generics. Below, two data structures are used to demonstrate how to use generics.

Queue

Below is a simple queue implemented with generics. First, declare the queue type. The element type in the queue can be anything, so the type constraint is any:

type Queue[T any] []T

There are only four methods: Pop, Peek, Push, Size. The code is as follows:

type Queue[T any] []T

func (q *Queue[T]) Push(e T) {
  *q = append(*q, e)
}

func (q *Queue[T]) Pop(e T) (_ T) {
  if q.Size() > 0 {
    res := q.Peek()
    *q = (*q)[1:]
    return res
  }
  return
}

func (q *Queue[T]) Peek() (_ T) {
  if q.Size() > 0 {
    return (*q)[0]
  }
  return
}

func (q *Queue[T]) Size() int {
  return len(*q)
}

In the Pop and Peek methods, you can see the return value is _ T. This is the usage of named return values, but using underscore _ to indicate it's anonymous. This is not superfluous, but to represent the generic zero value. Since generics are used, when the queue is empty, a zero value needs to be returned. But since the type is unknown, a specific type cannot be returned. Using the above method, the generic zero value can be returned. You can also solve the zero value problem by declaring a generic variable. For a generic variable, its default value is the zero value of that type, as follows:

func (q *Queue[T]) Pop(e T) T {
    var res T
  if q.Size() > 0 {
    res = q.Peek()
    *q = (*q)[1:]
    return res
  }
  return res
}

Heap

In the queue example above, since there are no requirements for elements, the type constraint is any. But a heap is different. A heap is a special data structure that can determine the maximum or minimum value in O(1) time, so it has a requirement for elements: they must be sortable types. But the built-in sortable types are only numbers and strings, so when initializing a heap, a custom comparator needs to be passed in. The comparator is provided by the caller and must also use generics, as follows:

type Comparator[T any] func(a, b T) int

Below is a simple binary heap implementation. First, declare the generic struct, still using any for constraint so it can store any type:

type Comparator[T any] func(a, b T) int

type BinaryHeap[T any] struct {
  s []T
  c Comparator[T]
}

Several method implementations:

func (heap *BinaryHeap[T]) Peek() (_ T) {
  if heap.Size() > 0 {
    return heap.s[0]
  }
  return
}

func (heap *BinaryHeap[T]) Pop() (_ T) {
  size := heap.Size()
  if size > 0 {
    res := heap.s[0]
    heap.s[0], heap.s[size-1] = heap.s[size-1], heap.s[0]
    heap.s = heap.s[:size-1]
    heap.down(0)
    return res
  }
  return
}

func (heap *BinaryHeap[T]) Push(e T) {
  heap.s = append(heap.s, e)
  heap.up(heap.Size() - 1)
}

func (heap *BinaryHeap[T]) up(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  for parentIndex := i>>1 - 1; parentIndex >= 0; parentIndex = i>>1 - 1 {
    // greater than or equal to
    if heap.compare(heap.s[i], heap.s[parentIndex]) >= 0 {
      break
    }
    heap.s[i], heap.s[parentIndex] = heap.s[parentIndex], heap.s[i]
    i = parentIndex
  }
}

func (heap *BinaryHeap[T]) down(i int) {
  if heap.Size() == 0 || i < 0 || i >= heap.Size() {
    return
  }
  size := heap.Size()
  for lsonIndex := i<<1 + 1; lsonIndex < size; lsonIndex = i<<1 + 1 {
    rsonIndex := lsonIndex + 1

    if rsonIndex < size && heap.compare(heap.s[rsonIndex], heap.s[lsonIndex]) < 0 {
      lsonIndex = rsonIndex
    }

    // less than or equal to
    if heap.compare(heap.s[i], heap.s[lsonIndex]) <= 0 {
      break
    }
    heap.s[i], heap.s[lsonIndex] = heap.s[lsonIndex], heap.s[i]
    i = lsonIndex
  }
}

func (heap *BinaryHeap[T]) Size() int {
  return len(heap.s)
}

func NewHeap[T any](n int, c Comparator[T]) BinaryHeap[T] {
	var heap BinaryHeap[T]
	heap.s = make([]T, 0, n)
	heap.Comparator = c
	return heap
}

Usage:

type Person struct {
  Age  int
  Name string
}

func main() {
  heap := NewHeap[Person](10, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)
  })
  heap.Push(Person{Age: 10, Name: "John"})
  heap.Push(Person{Age: 18, Name: "mike"})
  heap.Push(Person{Age: 9, Name: "lili"})
  heap.Push(Person{Age: 32, Name: "miki"})
  fmt.Println(heap.Peek())
  fmt.Println(heap.Pop())
  fmt.Println(heap.Peek())
}

Output:

{9 lili}
{9 lili}
{10 John}

With generics, originally unsortable types can also use heaps after passing in a comparator. This is definitely more elegant and convenient than the old way of using interface{} for type conversion and assertion.

Object Pool

The original object pool could only use any type, requiring type assertion every time something was retrieved. After simple transformation with generics, this work can be eliminated.

package main

import (
	"bytes"
	"fmt"
	"sync"
)

func NewPool[T any](newFn func() T) *Pool[T] {
	return &Pool[T]{
		pool: &sync.Pool{
			New: func() interface{} {
				return newFn()
			},
		},
	}
}

type Pool[T any] struct {
	pool *sync.Pool
}

func (p *Pool[T]) Put(v T) {
	p.pool.Put(v)
}

func (p *Pool[T]) Get() T {
	var v T
	get := p.pool.Get()
	if get != nil {
		v, _ = get.(T)
	}
	return v
}

func main() {
	bufferPool := NewPool(func() *bytes.Buffer {
		return bytes.NewBuffer(nil)
	})

	for range 100 {
		buffer := bufferPool.Get()
		buffer.WriteString("Hello, World!")
		fmt.Println(buffer.String())
		buffer.Reset()
		bufferPool.Put(buffer)
	}
}

Summary

One of Go's major features is very fast compilation speed. Fast compilation is due to fewer optimizations during compilation. The addition of generics increases the compiler's workload and makes the work more complex, which inevitably slows down compilation. In fact, when Go 1.18 first introduced generics, it did cause slower compilation. The Go team wanted to add generics without slowing down compilation too much. If developers find it easy to use, the compiler suffers. Conversely, if the compiler is relaxed (the most relaxed being no generics at all), developers suffer. Today's generics are the product of compromise between these two.