Good article. Some related bits that other languages do:
Swift is able to avoid monomorphizing even when the type arguments have different GC shapes and allocation strategies. To do that, the dictionary (what Swift calls a "witness table") has entries for the functions the memory manager needs to allocate and trace a value of type argument's type.
Go's notion of dictionary and Swift's witness tables share a lot of DNA with how Haskell compiles generic code using type classes.
C#/.NET does an interesting hybrid approach. When source code is compiled to .NET bytecode, the generic code is only compiled once. Then at load time, the JIT will take that bytecode and monomorphize it to native code for each instantiation using a value type (primitive or struct). But instantiations of reference types all share a single JITTed implementation.
Go's approach to generics is decent. It gets some of the benefits with some of the downsides. When coding in Rust, I am always so desperate for better compile times, especially for "clean" compilation because I make heavy use of Nix for various things and that comes into play a lot. (I don't run all of my builds in Nix, but I use Nix for virtual machine based integration testing for example, and that would involve doing a clean Nix build of the program.) So I guess while I get why some people were disappointed when Go didn't choose full monomorphization I appreciate their commitment to keeping fast compile times a priority. And it is certainly a hell of a lot nicer to be able to do proper generics at the language level on maps and slices in any case.
Monomorphized generics alone don't do it, but pervasive use of monomorphized generics definitely can make binaries huge and make compile times slow. Zig may avoid it generally, but C++ doesn't.
(Even Go's generics did slow down compile times a bit at first.)
The biggest issue with stenciling is lack of inlining. So for example if the argument to a generic function is an array backed container, then element access will have to go through a method call that cannot be inlined.
Besides the call indirection, the compiler also loses optimization opportunities.
With the stenciling design many generic functions found in the C++ stl have to pay significant abstraction costs.
That is true. Moreover, in general the performance of generic code in Go isn't any better than interface-driven one. Generics are there in Go just for better type safety, and IMO that's sufficient already :)
Good article. Some related bits that other languages do:
Swift is able to avoid monomorphizing even when the type arguments have different GC shapes and allocation strategies. To do that, the dictionary (what Swift calls a "witness table") has entries for the functions the memory manager needs to allocate and trace a value of type argument's type.
Go's notion of dictionary and Swift's witness tables share a lot of DNA with how Haskell compiles generic code using type classes.
C#/.NET does an interesting hybrid approach. When source code is compiled to .NET bytecode, the generic code is only compiled once. Then at load time, the JIT will take that bytecode and monomorphize it to native code for each instantiation using a value type (primitive or struct). But instantiations of reference types all share a single JITTed implementation.
I'd be curious about the runtime cost of the extra lookup in case of Swift compared to Go.
Go's approach to generics is decent. It gets some of the benefits with some of the downsides. When coding in Rust, I am always so desperate for better compile times, especially for "clean" compilation because I make heavy use of Nix for various things and that comes into play a lot. (I don't run all of my builds in Nix, but I use Nix for virtual machine based integration testing for example, and that would involve doing a clean Nix build of the program.) So I guess while I get why some people were disappointed when Go didn't choose full monomorphization I appreciate their commitment to keeping fast compile times a priority. And it is certainly a hell of a lot nicer to be able to do proper generics at the language level on maps and slices in any case.
It's not generics making Rust compilation slow; Zig has monomorphized generics but is quite fast to compile.
Monomorphized generics alone don't do it, but pervasive use of monomorphized generics definitely can make binaries huge and make compile times slow. Zig may avoid it generally, but C++ doesn't.
(Even Go's generics did slow down compile times a bit at first.)
It's a bunch of things. LLVM is one of them. Zig moved away from it for reasons.
A related self-plug, but if anyone wants to see additional examples, I've written a detailed exploration of Go generics as part of a larger Go reverse engineering reference here: https://docs.google.com/document/d/1AG76FBur7aagm36o-hNbny1X...
The biggest issue with stenciling is lack of inlining. So for example if the argument to a generic function is an array backed container, then element access will have to go through a method call that cannot be inlined.
Besides the call indirection, the compiler also loses optimization opportunities.
With the stenciling design many generic functions found in the C++ stl have to pay significant abstraction costs.
Anyway, I like the go design.
That is true. Moreover, in general the performance of generic code in Go isn't any better than interface-driven one. Generics are there in Go just for better type safety, and IMO that's sufficient already :)
It's all tradeoffs. Fully monomorphized generics tend to blow up compile time.
Full monomorphization can also greatly increase code size and icache pressure. Especially if LTO was not possible.
I haven’t seen icache pressure causing performance degradation in the wild but it is in theory possible.