paint-brush
Generic Programming in Goby@vgukasov
3,654 reads
3,654 reads

Generic Programming in Go

by Vladislav GukasovJune 2nd, 2022
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Generic Functions were added in Go in the 1.18 release of the language. These are functions defined with Type parameters, intended to be resolved with type information. The compiler uses these types to instantiate suitable versions, resolving any function overloading. The Map function takes a slice and a callback function that modifies each item and writes the item in a new slice `mapped` The function implementation looks similar to the integer mapping implementation for integer values. In practice, it gives the following features: code writing becomes comfortable for developers since there is no need to implement or generate code for every new data type.

Company Mentioned

Mention Thumbnail
featured image - Generic Programming in Go
Vladislav Gukasov HackerNoon profile picture

Introduction

Generic Programming in Go has always been awkward compared to other compiled languages. The most popular ways to implement it in Go are using interfaces, typecasting, and code-generation. But every method has its significant limitations. For instance, using interfaces requires implementing an interface for each data type. Typecasting leads to potential runtime errors. And in the case of code generation, we have to write generators, which takes a lot of time.


The article's primary goal is to understand how Generics work in Go and compare their performance with previous Generic Programming methods in Go. I will implement a popular function, "Map," that iterates over an array of data and transforms each element using a callback function.


The article code examples are stored in the Github repository.

Go Generic Functions

Generic functions were added in Go in the 1.18 release.

Generic functions refer to a mechanism for compile-time polymorphism, specifically parametric polymorphism. These are functions defined with Type Parameters, intended to be resolved with compile-time type information. The compiler uses these types to instantiate suitable versions, resolving any function overloading appropriately.


Generic functions in Go allow:

  • define type parameters for function and types.
  • define interface types as sets of types, including types that don’t have methods.
  • define type inference, which permits omitting type arguments in many cases when calling a function


In practice, it gives the following features:

  • code writing becomes comfortable for developers since there is no need to implement or generate code for every new data type
  • a compile-time type safety
  • a runtime type safety

Go Generic Function — Map Example

Let’s see how Generic Functions work in Go. And for the real-world example, we will use the Map function. The function takes a slice and a callback that modifies every item and returns a new slice.


The Map function implementation for integer values looks like this:


// Map modifies every item of list and returns a new modified slice.
func Map[T any](list []T, modify func(item T) T) []T {
	if list == nil {
		return nil
	}

	if modify == nil {
		return list
	}

	mapped := make([]T, len(list))
	for i, item := range list {
		mapped[i] = modify(item)
	}

	return mapped
}


There are two checks on nil values for a list and a callback function for safety. After that, there is a new slice with the same length as a list. Then, the function iterates through a list, modifies each item, and writes the item in a new slice mapped. An example of how the function works:


package main

func main() {
    // prints 2, 4, 6
    fmt.Println(Map([]int{1,2,3}, func(item int) int {
		return item * 2
	}))
}


However, if there is a need to use the Map function with another type, it needs to implement a new function. This architecture isn't scalable and hard to maintain. But using new Generic Functions, we can create a single function that will work with all types that we need:


// Map modifies every item of list and returns a new modified slice.
func Map[V any](list []V, modify func(item V) V) []V {
	if list == nil {
		return nil
	}

	if modify == nil {
		return list
	}

	mapped := make([]V, len(list))
	for i, item := range list {
		mapped[i] = modify(item)
	}

	return mapped
}


Type any is a new alias for interface{}.


The function implementation looks similar to the integer mapping implementation. The only difference is the function signature. Now there is a type parameter definition [V any] which means that the function can handle any type, but it should be the same type in a callback function modify func(item V) V) []V. Let’s see how the Map function works for different types:


package main

import (
	"fmt"
	"strings"
)

type person struct {
	name string
	age  int
}

func main() {
	// prints [2 4 6]
	fmt.Println(Map([]int{1, 2, 3}, func(item int) int {
		return item * 2
	}))

	// prints [HELLO WORLD]
	fmt.Println(Map([]string{"hello", "world"}, func(item string) string {
		return strings.ToUpper(item)
	}))

	// prints [{Linda 19} {John 23}]
	fmt.Println(Map([]person{{name: "linda", age: 18}, {name: "john", age: 22}}, func(p person) person {
		p.name = strings.Title(p.name)
		p.age += 1

		return p
	}))
}

Go Generic Functions Internals

This section will research how Generic Functions behave during compilation and program runtime.

Runtime type safety

For the research, I will use the following Go program:


package main

import (
	"fmt"
	"runtime"
	"strings"
)

type person struct {
	name string
	age  int
}

func main() {
	ints := []int{1, 2, 3}
	doubledInts := Map(ints, func(item int) int {
		return item * 2
	})

	// prints [2 4 6]
	fmt.Println(doubledInts)

	words := []string{"hello", "world"}
	capitalizedWords := Map(words, func(item string) string {
		return strings.ToUpper(item)
	})

	// prints [HELLO WORLD]
	fmt.Println(capitalizedWords)

	people := []person{{name: "linda", age: 18}, {name: "john", age: 22}}
	modifiedPeople := Map(people, func(p person) person {
		p.name = strings.Title(p.name)
		p.age += 1

		return p
	})

	// prints [{Linda 19} {John 23}]
	fmt.Println(modifiedPeople)

	runtime.Breakpoint()
}

// Map modifies every item of list and returns a new modified slice.
func Map[T any](list []T, modify func(item T) T) []T {
	if list == nil {
		return nil
	}

	if modify == nil {
		return list
	}

	mapped := make([]T, len(list))
	for i, item := range list {
		mapped[i] = modify(item)
	}

	runtime.Breakpoint()

	return mapped
}


There are two runtime breakpoints for debug purposes. For convenience, I use JetBrains Goland IDEA to debug the code.


After running the program in debug mode we can see that the first call of the Map function contains the list with []int.



However, the following two function calls have different types in runtime:



Therefore, a specific, strictly defined type is passed from a caller function in runtime inside the Map function.

Also, in the main function all types are defined as well:



We can conclude, that Generics in Go do retain their type information at runtime, and in fact, Go does not know about the generic "template" at runtime - only how it was instantiated.


To make sure that type is retained during compilation, we can try to assign capitalizedWords []string to doubledInts []int:


	ints := []int{1, 2, 3}
	doubledInts := Map(ints, func(item int) int {
		return item * 2
	})

	words := []string{"hello", "world"}
	capitalizedWords := Map(words, func(item string) string {
		return strings.ToUpper(item)
	})

	doubledInts = capitalizedWords 


Here happens a compilation error:


./main.go:24:16: cannot use capitalizedWords (variable of type []string) as type []int in assignment


Therefore, Go does enforce type safety for generic types at runtime.

Runtime instantiation

Let’s see what happens if we try to inspect a Generic Function in runtime using reflection:


package main

import (
	"fmt"
	"reflect"
)

func main() {
	fmt.Println(reflect.TypeOf(Map))
}

// Map modifies every item of list and returns a new modified slice.
func Map[T any](list []T, modify func(item T) T) []T {
	if list == nil {
		return nil
	}

	if modify == nil {
		return list
	}

	mapped := make([]T, len(list))
	for i, item := range list {
		mapped[i] = modify(item)
	}

	return mapped
}


Trying to compile the program returns an error:


./main.go:9:29: cannot use generic function Map without instantiation


Therefore, Generics are not helpful in Go until instantiated. There is no way to refer to generic "templates" using reflection, which means it is not possible to instantiate new types using Generics at runtime. It is almost as if generic types do not exist in compiled Golang binaries.

Generic Functions Performance

We researched how Generic Functions work during compilation and runtime. The last important question is: how fast do they perform?


There are three different implementations of the Map function:


// Map modifies every item of list and returns a new modified slice.
func Map[T any](list []T, modify func(item T) T) []T {
   if list == nil {
      return nil
   }

   if modify == nil {
      return list
   }

   mapped := make([]T, len(list))
   for i, item := range list {
      mapped[i] = modify(item)
   }

   return mapped
}

// MapTyped modifies every item of list and returns a new modified slice. It works only with Integer values.
func MapTyped(list []int, modify func(item int) int) []int {
   if list == nil {
      return nil
   }

   if modify == nil {
      return list
   }

   mapped := make([]int, len(list))
   for i, item := range list {
      mapped[i] = modify(item)
   }

   return mapped
}

// MapAny modifies every item of list and returns a new modified slice. It works with Any type, so you should cast types by yourself.
func MapAny(list []any, modify func(item any) any) []any {
   if list == nil {
      return nil
   }

   if modify == nil {
      return list
   }

   mapped := make([]any, len(list))
   for i, item := range list {
      mapped[i] = modify(item)
   }

   return mapped
}


For benchmark, we use a list of integers []int{1,2,3} and a callback function that doubles each integer value:


func BenchmarkGenericMap(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Map([]int{1, 2, 3}, func(item int) int {
			return item * 2
		})
	}
}

func BenchmarkTypedMap(b *testing.B) {
	for i := 0; i < b.N; i++ {
		MapTyped([]int{1, 2, 3}, func(item int) int {
			return item * 2
		})
	}
}

func BenchmarkAnyMap(b *testing.B) {
	for i := 0; i < b.N; i++ {
		MapAny([]any{1, 2, 3}, func(item any) any {
			return item.(int) * 2
		})
	}
}


After calling the go test -bench=. -benchmem -v ./... command, we have the benchmark results that are described in the table below:


Map function type

Operations count

ns/op

bytes/op

allocs/op

Generic

42033705

28.90

24

1

Typed

41317022

29.16

24

1

Any (using type casting)

17563975

68.61

48

1


The benchmark takeaways:

  • the Generic Function has the same performance as a specifically-typed function implementation
  • on average, the Generic Function outperformed the Any (using type casting) implementation:
    • operations are ~2.4 times faster
    • consumed half the memory
  • the performance improvements were the result of removing the need to use a type casting

Conclusion

We researched what the Generic Functions are and how they work in Go. Also, we compared the Generic Functions' performance with previous Generic Programming methods. Finally, there are the main conclusions:

  • Generics allow to write a function only once and use it for different data types without any extra code. Therefore, it’s easier to scale and maintain.
  • Go Generic Functions are instantiated during compilation, and they aren’t presented in program runtime. That prevents unexpected behavior in a program and guarantees a type-safety.
  • Go Generic Functions have the same performance as a specifically-typed function implementation, but it’s preferable since there is no need to write a new function for each data type.

References

  1. Generic function - Wikipedia (https://en.wikipedia.org/wiki/Generic_function)
  2. An introduction to Generics - The Go Programming Language (https://go.dev/blog/intro-generics)
  3. Go generics the hard way (https://github.com/akutz/go-generics-the-hard-way)