People's efficiency expectations for generics in 'Go 2' and patterns of use

June 19, 2020

The Go authors have recently come out with a blog entry on the next steps for generics and a new draft design based on interfaces instead of contracts. As it always is, one of the concerns raised in the draft is about the efficiency tradeoffs of any implementation.

Roughly speaking, there are two ways to implement generics. One is to generate fully specialized implementations every time a generic function or type is specialized to a concrete set of types; another is to compile only a single implementation and quietly pass hidden parameters to the implementation so that it can do its work, similar to how interfaces are implemented in Go (and also maps; most of the code of Go maps is generic, not specialized for each type of map). Fully specialized implementations are as fast as the compiler can make them with full knowledge of the types and functions involved, but they take longer to compile and result in more code in the final binary.

In thinking about this, it strikes me that there are two usage patterns (or at least extremes of usage patterns) for generics, based on what code people often write in Go today. I will call these type safe interfaces and single implementations respectively. The type safe interfaces usage pattern would use generics to implement a type safe version of what code is already doing with interface{} or somewhat more restrictive interfaces today. The proposal itself talks about Go using generics to implement type safe versions of things like container/list and sync.Map (here).

The single implementations usage pattern would use generics to condense what today is multiple copies of essentially the same code, specialized to various types, into a single block of code using generic types. These are the people who are tired of writing yet another copy of the function to generate a slice of all of the keys of a map of some new type. Their existing code could in theory be written once using interface{} and a lot of typecasts, but in practice repetition is better than all of the typecasts required (and the resulting possibility of runtime panics), especially since the underlying code is often reasonably simple and short.

People in the type safe interfaces usage pattern probably don't mind the potential speed overheads of a single unspecialized implementation, because they are already paying that penalty today. This does imply that such a generics implementation shouldn't perform worse than the interface based equivalent. People in the single implementations usage pattern are replacing hand specialized Go code with a generics implementation so they can write it only once. Some of them won't be willing to do this if there's a significant performance penalty as a result of such a conversion, and in general these people are willing to pay the compile time and space penalty for specialized implementations because they're already doing so today with their hand specialized code.

(Hopefully the Go compiler can find clever ways to often make the extra cost of unspecialized code very low, similar to how it implements maps efficiently.)


Comments on this page:

By Andrew at 2020-06-19 02:44:35:

In my mind the two patterns aren't terribly different — and if the "type safe interface" pattern means implementing things like container types and publishing them as libraries for people to use, then there might be millions of instantiations of those container types, but probably only one or a few in any given program, so the monomorphized version seems like the way to go.

The Featherweight Generic Go paper by Phil Wadler’s team https://arxiv.org/abs/2005.11710 suggests that they are planning an implementation based on monomorphization (C++ style) rather than uniform representation (interface{} style).

By cks at 2020-06-19 11:35:32:

The design draft officially calls it undecided. Monomorphization has the obvious advantages that it is easy to implement in a code translation tool (the current experimental tool published by the Go authors) and easy to reason about, but the compiler can play special tricks to make uniform code work.

My guess is that there is a lot of code that doesn't do anything more with generic types than call methods on them and copy them (including as function arguments and return values). The actual implementation of this could be done relatively straightforwardly by a single copy of general code for the generic functions along the model of maps (with support at the call sites, which might take small auto-generated thunk functions in some cases).

By James Antill at 2020-06-20 14:01:08:

With reference to Tony's post: https://www.youtube.com/watch?v=Dq0WFigax_c

Written on 19 June 2020.
« How applications autostart on modern Linux desktops
Removing unmaintained packages from your Fedora machine should require explicitly opting in »

Page tools: View Source, View Normal, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Fri Jun 19 00:25:27 2020
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.