Generic Adapters in Go

13 August 2017

While playing about with ideas for generic types in Go, I have come up with what I’m calling a ‘Generic Adapter’.

The approach I’ve taken here is essentialy that described by Kevin Gillette in a 2013 Post to golang-nuts. It implements ‘erasure-style’ generics by wrapping the generic implementation of each method with an adapter function which handles type assertions for the caller.

type Container struct {
	T SomeType
	
	Set func(value SomeType) SomeType
}

type Int64Container struct {
	T int64
	
	Set func(value int64) int64
}

func myProgram() {
	c := &Int64Container{}
	generic.Factory(Container{}).Create(c)
}

Source code implementing a proof of concept can be found on Bitbucket. I can’t really say I recommend anyone using it, but it’s satisfying to show that it works!

Background

There has been a debate raging in the Go community about support for generic types since the language was first released.

Recently this has been rekindled by the announcement that the Go team would be looking for case studies to support the inclusion of new (potentially V1-incompatible) features in Go 2. They are currently collecting experience reports for why people would find generics useful in Go.

Many solutions have been suggested to add support within Go 1, the most pragmatic of which is generating new code from generic templates. This provides all of the benefits of generics without needing any additional support in the language. The disadvantage is that there’s an extra pre-compilation step to process the templates.

Why do people want generics?

Type safety

The canonical example of a generic type is probably a linked list. Go provides built-in generic slice and map types, but if you need something like a linked list or an ordered map, you need to implement them yourself.

Go provides a few container data structures, but they all operate on interface{} types. This means that you must include type assertions when you are getting elements out of the data structure.

Also, since the compiler can’t check which types should be added to the container, you (or a user of your code) could add arbitrary items without any compile or runtime warning until the item is retrieved and fails your type assertion.

Type documentation

If you pass an abstract container to other code, there is no attached information about which types you are using. This means the type must be noted in your documentation and kept up to date, but there’s no automatic check that this information is correct.

Libraries

If you are writing a data structure library, you don’t necessarily know the types that will be used ahead of time, and so can’t generate specialised implementations.

This comment by allowthere about code generation on Reddit captures the issue:

The thing is that this won’t help the one place generics are actually really useful - libraries.
You don’t need generics when writing your own code, and when you do, you can always cut and paste+grep.
The real need for generics is libraries. Let’s say I want to make a “better” channel library. Let’s say I want to make a growable channel.
Sure, I can make it for myself, and make a StringChan, IntChan, AcmeTypeChan, etc. But what if I want to share it?
I have to make an InterfaceChan.
This is where I would need generics, and where code-gen won’t help.

Performance

Performance, and to a smaller degree memory usage, are degraded by requiring data structures to use interfaces instead of concrete types. They add an extra level of indirection which can have an impact if the data structure is in a critical part of the code. Function calls can be inlined, but type assertions still need to be made when retrieving abstract types.

A few quick benchmarks show that setting a primitive int value into a slice of []interface{} is slower than a directly typed slice of []int, but the overhead for reading back that value with a type assertion is small:

BenchmarkInterfaceSliceSet-8              50000000               25.3 ns/op
BenchmarkPrimitiveSliceSet-8            2000000000               0.35 ns/op

BenchmarkInterfaceSliceGet-8            2000000000               0.47 ns/op
BenchmarkPrimitiveSliceGet-8            2000000000               0.30 ns/op

In practice, if a data structure is in an inner loop of a heavily used function, it’s probably advisable to cut out an abstract data structure altogether and use a raw slice or map if possible. On the other hand, the Go compiler is pretty good at optimising and inlining calls to these structures.

Generic Adapters

I’m sure this concept must have another name already, but I can’t find one yet. In essence, you can take a generic interface and create a type-safe wrapper which adapts typed functions to their generic counterparts.

Approach

There are two steps that the implementer of the generic type completes:

  • Define a generic type using func fields
  • Create a generic implementation and register it with the adapter library

There are additionally two steps required to use a specialised version of that type:

  • Create a struct matching the generic type, but with func fields specialised to the type you wan to use.
  • Use the adapter library to initialise an instance of the type

Func fields?

One limitation of this approach is that we can’t use interfaces directly, but must use function fields in a struct instead. The reason for this is that the Go reflection package doesn’t allow us to dynamically create implementations for interface types, but does allow us to create functions conforming to a given signature, and assign them to a field.

There is an open issue for this on GitHub, currently tagged for Go 1.10, so this may eventually be possible with just interfaces, which would be much nicer, as you could then use the generated wrapper with compatible interfaces.

Simple example

Here is a simple List interface, with a single generic parameter T. We aren’t claiming anything about the implementation yet:

type ListItem interface{}

type List struct {
	T ListItem

	Len    func() int
	Get    func(i int) ListItem
	Set    func(i int, item ListItem) ListItem
	Append func(item ListItem)
	Insert func(i int, item ListItem)
	Remove func(i int) ListItem
}

In fact, it is implemented using a slice. This is probably not a useful abstraction, but it illustrates our point:

type ListImpl struct {
	T     ListItem
	items []ListItem
}

func newList() interface{} {
	return &ListImpl{}
}

func (l *ListImpl) Len() int {
	return len(l.items)
}

func (l *ListImpl) Get(i int) ListItem {
	return l.items[i]
}

func (l *ListImpl) Set(i int, item ListItem) ListItem {
	existing := l.items[i]
	l.items[i] = item
	return existing
}

func (l *ListImpl) Append(item ListItem) {
	l.items = append(l.items, item)
}

func (l *ListImpl) Insert(i int, item ListItem) {
	l.items = append(l.items[:i], append([]ListItem{item}, l.items[i:]...)...)
}

func (l *ListImpl) Remove(i int) ListItem {
	existing := l.items[i]
	l.items = append(l.items[:i], l.items[i+1:]...)
	return existing
}

In this implementation, we are stating that we accept any specialisation of T which conforms to ListItem

Once we have these two types, we can register the implementation with the adapter library:

func init() {
	generic.Factory(List{}).
		Register(ListImpl{}, newList)
}

This is saying that ListImpl can be used as a generic implementation of List.

Now we can create a specialised type with the appropriate type assertions:

type Int64List struct {
	T int64
	
	Len    func() int
	Get    func(i int) int64
	Set    func(i int, item int64) int64
	Append func(item int64)
	Insert func(i int, item int64)
	Remove func(i int) int64
}

Notice that all occurrences of ListItem in the original List type have been replaced by int64. The type parameter T is also changed to indicate its type.

Finally, we create a new instance of the specialised type:

func NewInt64List() *Int64List {
	l := &Int64List{}
	generic.Factory(List{}).Create(l)
	return l
}

Calling the Create method on the factory will instantiate a new instance of the implementation and map its methods into the func fields on l.

Specialised implementations

So, now we have the generic adapter factory (I’m sure there are a few more design patterns that could be thrown in there), we can use the generic implementation with type-safe wrappers.

This addresses the first few use cases listed above: type safety, documentation and libraries.

However, if we want to address the performance issue, we still need a bit more. Go can’t dynamically generate new code at runtime, so it can’t optimise the generic implementation with knowledge of the concrete types.

Here’s where we can fall back on existing approaches: we can generate a specialised implementation using the concrete types before compilation, and register these as implementations of the generic types.

In this way we are making use of the factory pattern, providing the most appropriate implementation for the given situation.

Here’s an example of registering a specialised string list:

type StringListImpl struct {
	T     string
	items []string
}

// Type-specifc methods ...

func init() {
	generic.Factory(List{}).
		Register(StringListImpl{}, newStringList)
}

Performance

To be honest, it’s a bit slow:

BenchmarkDirectListCreate-8             2000000000               1.81 ns/op
BenchmarkGenericListCreate-8             1000000              1475 ns/op
BenchmarkSpecialisedListCreate-8         1000000              1734 ns/op

BenchmarkDirectListAppend-8             200000000                6.36 ns/op
BenchmarkGenericListAppend-8             2000000               739 ns/op
BenchmarkSpecialisedListAppend-8        10000000               164 ns/op

BenchmarkDirectListSet-8                2000000000               0.53 ns/op
BenchmarkGenericListSet-8                2000000               674 ns/op
BenchmarkSpecialisedListSet-8           10000000               170 ns/op

BenchmarkDirectListGet-8                2000000000               0.61 ns/op
BenchmarkGenericListGet-8                3000000               443 ns/op
BenchmarkSpecialisedListGet-8           10000000               172 ns/op

That’s not exactly a surprise, due to the use of reflection in the new method shims.

BenchmarkReflectTypeOf-8                300000000                5.51 ns/op
BenchmarkReflectValueOf-8               30000000                53.6 ns/op

DirectList* and SpecialisedList* are actually using the same underlying implementation, so it’s clear how much overhead this approach introduces. If the data structure you are adapting is a bit meatier, then this overhead may still be acceptable. Similarly if the data structure is not used in a performance-critical section of code.

When the function signature of the implementation matches the wrapper, we avoid as much reflection as possible by directly mapping to the implementation function, but there’s still an extra ~170ns/op. At first I thought this was because the function can’t be inlined, but this shouldn’t cause such a large overhead: calls through interface types can’t be inlined either, and that only adds ~2.5ns:

BenchmarkDirectListSet-8                2000000000               0.53 ns/op
BenchmarkInterfaceListSet-8             500000000                2.98 ns/op
BenchmarkFuncListSet-8                  500000000                3.04 ns/op
BenchmarkReflectFuncListSet-8           10000000               185 ns/op

I tried a couple of variations, including manually setting the func field to the method pointer from the implementation type, but this doesn’t seem to introduce more overhead than just using an interface.

If I use reflect.Value.Set to assign the method pointer to the func field, we suddenly get 180ns overhead. What’s going on?

It turns out that using reflection to assign a method pointer to a func field is not the same as doing it directly, and results in an extra instance of reflect.methodValueCall being created to wrap the method with a function. I don’t know if there is a better way of doing this. It looks like the compiler is able to generate a more efficient function -> method wrapper than is possible at runtime.

In summary: room for improvement.

Conclusion

There’s still plenty missing from the proof of concept implementation, but hopefully I’ve done the idea justice.

I’ve got some ideas for more extensions to the adapter to allow more complex use cases, but that will have to wait for a future date.

For now, the adapter provides runtime type safety checks to be added to a generic implementation of a data structure. It also allows specialised implementations, such as those generated from a template, to be registered and used where appropriate without changing the code that uses the generic type.

There are some drawbacks to using the adapted wrapper, such as performance and use of func fields, but maybe some people will find the benefits attractive.