GC Shape Stenciling, a hybrid of stenciling and dictionaries: https://go.googlesource.com/proposal/+/refs/heads/master/des...

How does that compare to other approaches for generics? I know that you can do monomorphisation, which usually increases the executable size and compilation time, and usually gives faster code, but I don't know about other approcahes.

The two approaches are stenciling (what you call monomorphisation) and dictionaries. Stenciling/monomorphization increases binary size, compilation time and TLB/cache pressure. The dictionaries-only approach has more runtime cost. This hybrid is a middle ground of both.

So there's a runtime cost for using generics?

The linked article is a proposal but at least when I tried Go a couple of weeks ago, it did not use that approach and to the best of my knowledge that proposal has not yet been implemented. Instead as of now Go uses the straight forward approach of generating one implementation for every instantiation just like C++ compilers do.

The upside is there is no runtime cost to using generics, the downside is there is significant compile time and link time cost to generics.

> the downside is there is significant compile time and link time cost to generics.

Are we talking statistically significant or productivity significant compile time cost? Go has a fairly fast compiler, it would be a shame if generics made that a less stand-out feature.

The hybrid approach is absolutely implemented: https://github.com/golang/go/blob/master/src/cmd/compile/int...

Yes, the same cost as calling a method through an interface. IIUC, the concrete implementation can change.

No, it does not have the same cost as calling a method through an interface.

Yes, which I find unfortunate but I can respect that approach as it's likely the simplest way of implementing it and Go does want to avoid heavy abstraction in its type system.

The downside is you can't do something like have a function pointer to the generic itself or specify generic members of a dyn trait/interface or otherwise treat the generic as a first class value (although you can treat specific instantiations of it as first class). The generic is basically syntactic sugar for a macro like substitution system. C++ and other languages that take the monomorphization route all have this restriction, whereas languages with more "first-class" support for generics like C# don't and hence do allow the moral equivalent of a virtual template.

C# mostly gets away with it because it has JIT support for it; in the end you still need to generate code for every data-size it's used with. Obviously, if all data are passed by reference you'd only need to generate code for the size of the pointer.

Even in C#, generics are sort-of second class:

    interface IMyLovelyADT { R Accept<R>(IMyLovelyADTVisitor<R> visitor); }

is not isomorphic to

    Func<IMyLovelyADTVisitor<R>, R>

The interface is strictly more flexible because it's non-generic, see my comment at [0] for an actual code example (it's quite long) if you're interested, but the gist is "you need a non-generic wrapper interface IMyLovelyADT: it essentially does the same job as Haskell's forall, since generic types are not quite proper types in C#'s type system. Interestingly enough, upcoming Go 2's generics will not support this scenario: a method inside an interface will be able to use only the generic parameters that the interface itself declares."

[0] https://blog.ploeh.dk/2021/08/03/the-tennis-kata-revisited/

> Interestingly enough, upcoming Go 2's generics

It will be Go 1.18, not Go 2.

They've been discussed as one of the several "feature proposals for Go 2.0" for couple of years, the playground for them is called "https://go2goplay.golang.org/", the issues with them go into "cmd/go2go" tag on Github, so that's why I called them "Go 2's generics".

And weren't they supposed to be in Go 1.17 but then got delayed?