5 ms·

How are they implemented? Compile time? With template expansion like D and C++?

mseepgood 5y ago
GC Shape Stenciling, a hybrid of stenciling and dictionaries: https://go.googlesource.com/proposal/+/refs/heads/master/design/generics-implementation-gcshape.md https://go.googlesource.com/proposal/+/refs/heads/master/des...
- rustnote 5y ago
  So there's a runtime cost for using generics?
  - wwarner 5y ago
    Yes, the same cost as calling a method through an interface. IIUC, the concrete implementation can change.
    - mseepgood 5y ago
      No, it does not have the same cost as calling a method through an interface.
  - Kranar 5y ago
    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.
    - arc619 5y ago
      > 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.
    - mseepgood 5y ago
      The hybrid approach is absolutely implemented: https://github.com/golang/go/blob/master/src/cmd/compile/internal/noder/stencil.go https://github.com/golang/go/blob/master/src/cmd/compile/int...
- Zababa 5y ago
  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.
  - mseepgood 5y ago
    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.
Kranar 5y ago
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.
- Joker_vD 5y ago
  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/ https://blog.ploeh.dk/2021/08/03/the-tennis-kata-revisited/
  - mseepgood 5y ago
    > Interestingly enough, upcoming Go 2's generics It will be Go 1.18, not Go 2.
    - Joker_vD 5y ago
      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/ 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?

GC Shape Stenciling, a hybrid of stenciling and dictionaries: https://go.googlesource.com/proposal/+/refs/heads/master/design/generics-implementation-gcshape.md https://go.googlesource.com/proposal/+/refs/heads/master/des...

rustnote 5y ago
So there's a runtime cost for using generics?
- wwarner 5y ago
  Yes, the same cost as calling a method through an interface. IIUC, the concrete implementation can change.
  - mseepgood 5y ago
    No, it does not have the same cost as calling a method through an interface.
- Kranar 5y ago
  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.
  - arc619 5y ago
    > 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.
  - mseepgood 5y ago
    The hybrid approach is absolutely implemented: https://github.com/golang/go/blob/master/src/cmd/compile/internal/noder/stencil.go https://github.com/golang/go/blob/master/src/cmd/compile/int...
Zababa 5y ago
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.
- mseepgood 5y ago
  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.

Kranar 5y ago

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.

Joker_vD 5y ago
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/ https://blog.ploeh.dk/2021/08/03/the-tennis-kata-revisited/
- mseepgood 5y ago
  > Interestingly enough, upcoming Go 2's generics It will be Go 1.18, not Go 2.
  - Joker_vD 5y ago
    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/ 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?