GC shape stenciling in Go generics | Hacker News Reader

GC shape stenciling in Go generics

rednafi.com

54 pointsingve13 comments

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.

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

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

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.

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.

icache pressure was the bane of my optimization work around 2002. Mostly because it fluctuated unpredictably even from fairly small fairly faraway changes. The system got large enough, with a long enough hot code path that was very hot, that it was almost pointless to benchmark a subsystem in isolation. Simplistic attempts to make any subsystem faster typically made the whole system slower.

In general, whatever subsystem took the cache misses showed up as the slow part, and I owned the very first component in the pipeline... It was fun to compile time disable my component to demonstrate that nothing got faster, though.

Reply on news.ycombinator.com