Are they monomorphizing generics (compiling SomeFunc[int] and SomeFunc[float] separately) rather than using dynamic dispatch here? The mentions of instantiation in commit logs make me think they’re doing that, but I don’t see much explicit from the authors about whether it’s static or dynamic, and haven’t dug deeply.
From playing with the beta a little, a trivial function like Min[T constraints.Ordered](i, j T) T seems to take the same few cycles as the single-type version, but that doesn’t rule out that this only happens in simple-enough cases like inlineable functions. (I tested to update a Stack Overflow answer where folks complained about the non-generic solution.)
Ah, that fits, and this video also says it’s monomorphizing.
I’m surprised the blog and draft release notes don’t mention that generics should have essentially no runtime performance cost; might make some people feel safer starting to use ’em. (Generic functions leaning on interface calls seemed to be in consideration earlier on in the process.)
The current implementation is monomorphizing as far as I’ve been able to tell. One way to see this is on godbolt.org which will let you, with work, see the generated assembly code for code using generics on Go tip.
I suspect that this isn’t going to be documented because the Go developers don’t want to commit to it. The generics design was (is) specifically intended to allow for other compilation strategies, such as code that look more like Go dicts (which internally dispatch specific dict types to general dict code with suitable parameters). Whether not documenting it will let them change it later in practice is an open question; I suspect that people would be unhappy if the performance of generic code regressed from Go 1.18’s level in future Go versions (as it might if they switched implementation strategies for some generic code).
I don’t know if a monomorphizing initial implementation was planned from the start or if it fell out of how the early experimentation ‘try it out now’ implementation of Go generics, called ‘go2go’, worked by translating your Go with generics code to normal Go code, which obviously required monomorphizing it.
I suspect monomorphisation will stick around. The main issue with that approach is it can lead to large binaries. Still considering how Go likes to generate static executables, I don’t think binary size is a major concern for the project. I think they are trying to be cautious since this is one of those design decisions where it’s there the team doesn’t have a strong conviction on the right call.
Large binaries and long compile times. Fast build times has always been a major design goal & selling point for Go, so I would not be surprised if they fussed with this if it became clear that overuse was becoming a build-time footgun.
A hybrid strategy is possible where the compiler tries to be smart about when to monomorphize, to get the performance benefits where it matters, while avoiding it in places where the boost isn’t worth it for the build time hit. Though obviously that makes the runtime performance harder to reason about, and it’s hard to know how well the compiler can be taught to make these decisions.
Don’t you have to monomorphize in the absence of something like a vtable implementation or dynamic dispatch? What I mean is, unless runtime dispatch is implemented, don’t you have to concretize all types at compile time? I hope I’m not missing something.
I think it would be possible to use general techniques similar to how the Go runtime implements maps efficiently without generics, where under some circumstances you generate a more general chunk of code that only needs to be passed some basic type parameters of the specific types involved. Go always knows these specific types at compile time, so the question is whether it generates completely type-specific code for them (as it does currently) or if it can be clever enough to use a single parameterized version.
(We may see a certain amount of generics that are type-safe wrappers around maps. Since maps are already implemented this non-generics way, it might be tempting to recognize such generics and implement them similarly.)
Right, the most obvious alternative to monomorphization is to, instead of erasing type parameters on functions, convert them into an extra argument that is the vtable. The constraints on the type parameter tell you what the vtable needs to contain, and you know the concrete type at the call site, so you just have the compiler insert that extra argument (unless the type is itself a type parameter, in which case you can just pass down the vtable that was passed to you).
The hybrid strategy is more or less what GHC does for Haskell’s type classes.
In C++, templates are used in the ecosystem as a general-purpose preprocessor. Go fortunately has an easily parseable syntax so if you need a preprocessor, you can just write one yourself. This is pretty common, too.
Are they monomorphizing generics (compiling
SomeFunc[int]andSomeFunc[float]separately) rather than using dynamic dispatch here? The mentions of instantiation in commit logs make me think they’re doing that, but I don’t see much explicit from the authors about whether it’s static or dynamic, and haven’t dug deeply.From playing with the beta a little, a trivial function like
Min[T constraints.Ordered](i, j T) Tseems to take the same few cycles as the single-type version, but that doesn’t rule out that this only happens in simple-enough cases like inlineable functions. (I tested to update a Stack Overflow answer where folks complained about the non-generic solution.)Considering the design is based on the FeatherWeight Go paper, I think they make heavy use of monomorphisation.
Ah, that fits, and this video also says it’s monomorphizing.
I’m surprised the blog and draft release notes don’t mention that generics should have essentially no runtime performance cost; might make some people feel safer starting to use ’em. (Generic functions leaning on
interfacecalls seemed to be in consideration earlier on in the process.)The current implementation is monomorphizing as far as I’ve been able to tell. One way to see this is on godbolt.org which will let you, with work, see the generated assembly code for code using generics on Go tip.
I suspect that this isn’t going to be documented because the Go developers don’t want to commit to it. The generics design was (is) specifically intended to allow for other compilation strategies, such as code that look more like Go dicts (which internally dispatch specific dict types to general dict code with suitable parameters). Whether not documenting it will let them change it later in practice is an open question; I suspect that people would be unhappy if the performance of generic code regressed from Go 1.18’s level in future Go versions (as it might if they switched implementation strategies for some generic code).
I don’t know if a monomorphizing initial implementation was planned from the start or if it fell out of how the early experimentation ‘try it out now’ implementation of Go generics, called ‘go2go’, worked by translating your Go with generics code to normal Go code, which obviously required monomorphizing it.
I suspect monomorphisation will stick around. The main issue with that approach is it can lead to large binaries. Still considering how Go likes to generate static executables, I don’t think binary size is a major concern for the project. I think they are trying to be cautious since this is one of those design decisions where it’s there the team doesn’t have a strong conviction on the right call.
Large binaries and long compile times. Fast build times has always been a major design goal & selling point for Go, so I would not be surprised if they fussed with this if it became clear that overuse was becoming a build-time footgun.
A hybrid strategy is possible where the compiler tries to be smart about when to monomorphize, to get the performance benefits where it matters, while avoiding it in places where the boost isn’t worth it for the build time hit. Though obviously that makes the runtime performance harder to reason about, and it’s hard to know how well the compiler can be taught to make these decisions.
Don’t you have to monomorphize in the absence of something like a vtable implementation or dynamic dispatch? What I mean is, unless runtime dispatch is implemented, don’t you have to concretize all types at compile time? I hope I’m not missing something.
I think it would be possible to use general techniques similar to how the Go runtime implements maps efficiently without generics, where under some circumstances you generate a more general chunk of code that only needs to be passed some basic type parameters of the specific types involved. Go always knows these specific types at compile time, so the question is whether it generates completely type-specific code for them (as it does currently) or if it can be clever enough to use a single parameterized version.
(We may see a certain amount of generics that are type-safe wrappers around maps. Since maps are already implemented this non-generics way, it might be tempting to recognize such generics and implement them similarly.)
Right, the most obvious alternative to monomorphization is to, instead of erasing type parameters on functions, convert them into an extra argument that is the vtable. The constraints on the type parameter tell you what the vtable needs to contain, and you know the concrete type at the call site, so you just have the compiler insert that extra argument (unless the type is itself a type parameter, in which case you can just pass down the vtable that was passed to you).
The hybrid strategy is more or less what GHC does for Haskell’s type classes.
That’s a really good point. I’m curious what was discussed and decided.
[Comment removed by author]
Are there any estimates of how heavy use of generics would impact compile time ?
Yes, in the release notes.
Thank you. (exact paragraph)
Looks like Go is well on its way to becoming a somewhat pared-down C++ 😄 /s
In C++, templates are used in the ecosystem as a general-purpose preprocessor. Go fortunately has an easily parseable syntax so if you need a preprocessor, you can just write one yourself. This is pretty common, too.