Generico! Generics in go or is it worth it

March 15, 2022. It was a frosty spring day. The wind tried to prove that it was not a mistake and climb under jackets, sweaters and other wardrobe accessories, so that first-hand, wherever it was necessary, to bring spring mood through freshness. He wasn’t very good at it. And in any scenario. If a good jacket came across and did not let an intruder in, the wind could not tell about spring. If, however, it was possible to climb by the scruff of the neck or walk with an icy breath of freshness on the belly, the passer-by no longer understood this. He wrapped himself even more tightly and tried to get away from this spring mood as soon as possible. But this was not the only ambiguity. It was on March 15 that another ambiguity was introduced into the world, which provoked heated debate – the release of golang 1.18 along with the generic system.

The concept of generics itself is not new. The most famous coming of this concept to the world is java great and terrible. The concept itself is clear and even logical in appearance. In my opinion, the main thing that generics should have achieved was to remove the copy-paste of the code. Generics have appeared, allowing now to write unified functions instead of two or three for different data types, but with the same operations. It seems that the problem is solved, everyone rejoices, laughter is heard from all over, hats fly up, the crowd rejoices, fireworks burst in the sky! Or not at all? In order to rush headlong into solving a problem, the problem itself must exist, but was it?

In many places, when explaining generics, I met the implementation of a function that sums different numbers – int, float32, float64. Yes, the example shows what generic is, the copy-paste problem is solved. But how often do you write a function to add 2, 3 or even 4 numbers? All these examples leave a tart aftertaste of deceit. First, they lure you with big slogans, they say Breaking News, the breakthrough of the year, everyone is here, your life will not be the same! And you open the article and there they tell you how to add 2 + 2 (indeed, my life will not be the same – I will no longer believe the headlines of the articles!).

How about something more practical? I really liked the idea of ​​trying generics on the stack (especially at that moment I needed it in a small personal project). It is a fairly simple structure to understand and implement. In my opinion, this is the perfect test subject for experiments. In any scenario, one or another option will come in handy on the farm. Initially, I took a ready-made library, but then I decided to compare another implementation. Spoiler: I rewrote the library to generics and started using it in my project. And comparing the performance of the two solutions prompted me to this article.

Let’s look at the simplest implementation of a stack. If it is more convenient to see the code on a separate tab, the sources are located here.

package main

type (
	iNode struct {
		val  interface{}
		next *iNode
	}
	InterfaceStack struct {
		top *iNode
		len int
	}
)

func NewInterfaceStack() *InterfaceStack {
	return &InterfaceStack{}
}

func (istack *InterfaceStack) Push(val interface{}) {
	var n iNode = iNode{val: val, next: istack.top}
	istack.len += 1
	istack.top = &n
}

func (istack *InterfaceStack) Pop() interface{} {
	if istack.len <= 0 {
		return nil
	}
	istack.len -= 1
	var n *iNode = istack.top
	istack.top = n.next
	return n.val
}

func (istack *InterfaceStack) Peak() interface{} {
	if istack.len <= 0 {
		return nil
	}
	return istack.top.val
}

func (istack *InterfaceStack) Len() int {
	return istack.len
}

package main

type (
	gNode[NT any] struct {
		val  NT
		next *gNode[NT]
	}
	GenericStack[ST any] struct {
		top *gNode[ST]
		len int
	}
)

func NewGenericStack[GS any]() *GenericStack[GS] {
	return &GenericStack[GS]{}
}

func (gstack *GenericStack[ST]) Push(val ST) {
	var n gNode[ST] = gNode[ST]{val: val, next: gstack.top}
	gstack.len += 1
	gstack.top = &n
}

func (gstack *GenericStack[ST]) Pop() (res ST, exists bool) {
	if gstack.len <= 0 {
		exists = false
		return
	}
	gstack.len -= 1

	var n *gNode[ST] = gstack.top
	gstack.top = n.next
	return n.val, true
}

func (gstack *GenericStack[ST]) Peak() (res ST, exists bool) {
	if gstack.len <= 0 {
		exists = false
		return
	}
	return gstack.top.val, true
}

func (gstack GenericStack[ST]) Len() int {
	return gstack.len
}

There are no fundamental differences. The only thing is that the generic functions Pop and Peak return two arguments instead of one.

package main

import "fmt"

func main() {
	// Interface
	istack := NewInterfaceStack()
	istack.Push(12)
	istack.Push(32)
	ival := istack.Pop();
	if ival != nil{
		if val, ok := ival.(int); !ok {
			panic("wrong type in interface stack")
		} else {
			fmt.Printf("Got '%v' from interface stack\n", val)
		}
    }
  
	// Generic
	gstack := NewGenericStack[int]()
	gstack.Push(54)
	gstack.Push(67)
	if val, exists := gstack.Pop(); exists {
		fmt.Printf("Got '%v' from generic stack\n", val)
	}
}

There is a sample code (and it not only compiles, but also runs without errors!) so you can turn on the couch critic mode and go through all aspects of these two approaches.

Implementation through interfaces. Universal for any type. Moreover, it allows you to store different objects on the same stack (especially true if you have one or two extra whole legs lying around, which would be nice to shoot at). And the size of the binary will be a couple of hundred bytes smaller compared to generics. And as for the minuses – you need to constantly do type conversion, carefully monitor what you put on the stack, think through error handling. There is a non-zero chance that a conversion error will have to be handled at a higher level, which means the code will be more confusing. And when refactoring, you can forget to change the type conversion in some place and look for a long time where the error is coming from.

And now it’s the turn of generics. We initially know what type, so we don’t need to convert anything, if somewhere we try to put an inappropriate type on the stack – the compiler will deal with it. Less code in use. If we need stacks of several types, then code generation will be shifted to the compiler and will not require additional effort on the part of the developer. Of the minuses – now you need to explicitly check for the presence of an element on the stack – either through the length or through the returned flag.

It seems to me that our couch analyst is arguing for generics! Reading duck is a perfect feature. But it all concerned only the style of the code. But what else do we have to compare? Performance! In the open spaces of the boundless Internet, very often in the argument “for generics” they argue with performance. Since there is no need for type conversion, it will work faster. And if everything is really clear with code readability – generics win here with transparency of use and less code, then with performance everything is not so clear. Usually they are limited to inferences: since less code is executed, it works more productively. Yes, the logic is clear, native and performance really depends on the number of operations performed. But how much faster? Actually, to answer this question, such a simple implementation of the stack was made. If suddenly you need the full version, then the generics are here and on the interfaces lies here.

Well, now the tests themselves. (code can still be found herebut there is only the latest version – it differs from the code in the spoilers a little).

package main

import "testing"

type iTestNode struct {
	val		int
}

func createINode(value int) iTestNode {
	return iTestNode{value}
}

func BenchmarkInterfaceSimpleType(b *testing.B) {
	st := NewInterfaceStack()
	val := 1
	for i := 0; i < b.N; i += 1 {
		st.Push(val)
		if _, ok := st.Pop().(int); !ok {
			panic("Wrong type of data in stack")
		}
	}
}

func BenchmarkInterfaceSimpleCustomType(b *testing.B) {
	st := NewInterfaceStack()
	node := createINode(12)
	for i := 0; i < b.N; i += 1 {
		st.Push(node)
		if _, ok := st.Pop().(iTestNode); !ok {
			panic("Wrong type of data in stack")
		}
	}
}

func BenchmarkInterfaceCustomTypePointer(b *testing.B) {
	st := NewInterfaceStack()
	node := createINode(12)
	for i := 0; i < b.N; i += 1 {
		st.Push(&node)
		if _, ok := st.Pop().(*iTestNode); !ok {
			panic("Wrong type of data in stack")
		}
	}
}

package main

import "testing"

type gTestNode struct {
	val      int64
}

func createGNode(value int) gTestNode {
	return gTestNode{value}
}

func BenchmarkGenericSimpleType(b *testing.B) {
	st := NewGenericStack[int]()
	val := 1
	for i := 0; i < b.N; i += 1 {
		st.Push(val)
		st.Pop()
	}
}

func BenchmarkGenericCustomType(b *testing.B) {
	st := NewGenericStack[gTestNode]()
	node := createGNode()
	for i := 0; i < b.N; i += 1 {
		st.Push(node)
		st.Pop()
	}
}

func BenchmarkGenericCustomTypePointer(b *testing.B) {
	st := NewGenericStack[*gTestNode]()
	node := createGNode()
	for i := 0; i < b.N; i += 1 {
		st.Push(&node)
		st.Pop()
	}
}

I will run not for the number of iterations, but for the duration of the test (i.e. through -benchtime=20s ). The test launch code itself will be like this: go test -bench=. -benchtime=20s. I will run all tests 5 times to determine the order.

goos: linux
goarch: amd64
pkg: github.com/HoskeOwl/goSimpleStack
cpu: AMD Ryzen 7 4700U with Radeon Graphics         
BenchmarkGenericSimpleType-8                    313764921               77.92 ns/op
BenchmarkGenericCustomType-8                    317463438               71.97 ns/op
BenchmarkGenericCustomTypePointer-8             218245879              111.0 ns/op
BenchmarkInterfaceSimpleType-8                  213324286              113.0 ns/op
BenchmarkInterfaceSimpleCustomType-8            222740674              112.8 ns/op
BenchmarkInterfaceCustomTypePointer-8           218896858              111.9 ns/op

Not bad, the difference is not 2 times, but it is visible. Of course, for profit, you need the service to be really loaded. Otherwise, only the syntax remains of the pluses. But there are a few things that confuse me in these tests.

1) BenchmarkGenericCustomTypePointer is much out of time from other brothers;

2) in fact, here we have not only the stack operation code, but also the creation of objects. And what if the creation of objects is taken out of the loop? Well, so that everything is in an adult way – in general, it should not be taken into account through StopTimer and StartTimer.

goos: linux
goarch: amd64
pkg: github.com/HoskeOwl/goSimpleStack
cpu: AMD Ryzen 7 4700U with Radeon Graphics         
BenchmarkGenericSimpleType-8                    353000452               71.54 ns/op
BenchmarkGenericCustomType-8                    338031572               73.45 ns/op
BenchmarkGenericCustomTypePointer-8             323049594               73.77 ns/op
BenchmarkInterfaceSimpleType-8                  297199362               78.44 ns/op
BenchmarkInterfaceSimpleCustomType-8            298851950               81.57 ns/op
BenchmarkInterfaceCustomTypePointer-8           291001880               83.04 ns/op
PASS
ok      github.com/HoskeOwl/goSimpleStack       191.971s

“And they say that generics are not real!” – the only thing you want to shout after such a test. As soon as we start to remove parts of the program that are not related to the mechanisms of generics, the difference in performance is rapidly reduced. Plus, we see that BenchmarkGenericCustomTypePointer has returned to normal, so the problem is not in the implementation of the stack. But there is one more thing that also contributes – compiler optimization. Let’s turn it off by adding the notation //go:noinline for each benchmark function.

goos: linux
goarch: amd64
pkg: github.com/HoskeOwl/goSimpleStack
cpu: AMD Ryzen 7 4700U with Radeon Graphics         
BenchmarkGenericSimpleType-8                    323416230               72.84 ns/op
BenchmarkGenericCustomType-8                    325032516               71.51 ns/op
BenchmarkGenericCustomTypePointer-8             320308387               75.60 ns/op
BenchmarkInterfaceSimpleType-8                  290263794               81.65 ns/op
BenchmarkInterfaceSimpleCustomType-8            296999368               81.06 ns/op
BenchmarkInterfaceCustomTypePointer-8           291887139               82.64 ns/op
PASS
ok      github.com/HoskeOwl/goSimpleStack       190.310s

In all tests, the order was the same. And what did we get as a result? Yes, generics are faster, but not by much.

In summary: in my opinion, generics are a good start in golang. I would not say that with their release it is worth running and rewriting your entire old code base – most likely there will be no profit, in terms of performance. But I would recommend writing new code through generics. Readability will increase, and the number of situations in which you can shoot yourself in the foot will decrease.

And finally, for the most inquisitive – what will happen if we use a more complex one instead of a simple structure with one field? With the number of fields from 10.

goos: linux
goarch: amd64
pkg: github.com/HoskeOwl/goSimpleStack
cpu: AMD Ryzen 7 4700U with Radeon Graphics         
BenchmarkGenericSimpleType-8                    261289566               90.09 ns/op
BenchmarkGenericCustomType-8                    99811050               228.6 ns/op
BenchmarkGenericCustomTypePointer-8             291460882               80.94 ns/op
BenchmarkInterfaceSimpleType-8                  163295492              149.5 ns/op
BenchmarkInterfaceSimpleCustomType-8            84240980               285.6 ns/op
BenchmarkInterfaceCustomTypePointer-8           311288221               78.62 ns/op
PASS
ok      github.com/HoskeOwl/goSimpleStack       183.679s