GC shape stenciling in Go generics

https://rednafi.com/go/gc-shape-stenciling/

by ingve • 11 days ago

53 13 11 days ago

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.

rednafi3• 6 days ago

I'd be curious about the runtime cost of the extra lookup in case of Swift compared to Go.

jaeyoungkim• 6 days ago

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...

jchw2• 6 days ago

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.

logicchains• 6 days ago

It's not generics making Rust compilation slow; Zig has monomorphized generics but is quite fast to compile.

rednafi3• 6 days ago

It's a bunch of things. LLVM is one of them. Zig moved away from it for reasons.

jchw2• 6 days ago

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.)

zbentley• 6 days ago

Doing generics in a new Rust project’s types by “dyn”-ing everything you can and then falling back to monomorphized “true” generics after benchmarking is (or will be, when dyn compatibility for more layouts is added) a pretty okay way to go, I’ve found. Not without struggle and syntactic noise, but superior to the alternative.

drivebyhooting2• 6 days ago

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.

nasretdinov• 6 days ago

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 :)

rednafi3• 6 days ago

It's all tradeoffs. Fully monomorphized generics tend to blow up compile time.

GC shape stenciling in Go generics

Related Stories