Live data from Hacker News

How generics are implemented in Go 1.18

github.com

11–20 of 228 posts

Re: How generics are implemented in Go 1.18

#11
post #3

Earlier quoted context omitted.

In a nutshell, torn between the extreme ends of high compile-time cost and large code size of a C++ flavored implementation and the high runtime cost and dangers of boxing/unboxing (Java), Golang opted for "none of the above" and tried to limit complexity drivers / powerfulness / expressiveness / usefulness instead, keeping the impact on both compile time and run time low. About how well that decision will turn out i…

The compile time issues for C++ are entirely because of the creaky header mechanism that doesn't permit efficient parsing. Generics have worked fine in Ada since its inception. Any modern language can adopt the same process of tracking a formal abstract interface that is parsed once and expanded into concrete code as necessary.

The process of expanding genetic code into concrete code based on the types (monomorphizing) can also be an expensive process. At least, people in the rust world point to it a lot as a reason why some crates compile slowly. Monomorphizing multiplicatively increase how much code LLVM needs to process (and optimize).

Mind you, C/C++’s ridiculous header system is probably still a much bigger issue. Especially because C++ templates usually need to go in header files.

Re: How generics are implemented in Go 1.18

#13

Earlier quoted context omitted.

The compile time issues for C++ are entirely because of the creaky header mechanism that doesn't permit efficient parsing. Generics have worked fine in Ada since its inception. Any modern language can adopt the same process of tracking a formal abstract interface that is parsed once and expanded into concrete code as necessary.

Isn't that solved with c++ modules [1]? [1] https://en.cppreference.com/w/cpp/language/modules

Yes, with VC++ offering the best experience currently.

Re: How generics are implemented in Go 1.18

#14

Disclaimer: I only very occasionally touch Go code. Hasn't this been a very long time coming? Iirc there has been much dispute over this in the community. Can anyone weigh in on what the other options were?

I only occasional do language design / compiler writing projects, or work with compiler internals.

Most people are really bad at estimating the implementation complexity and tradeoffs inherent in various language features. I'd say that C++ serves as a warning to others... think before you add features to your language, or you'll end up a total mess, like C++. Java and C# gave us some interesting and subtle lessons about what does and does not work about language features like generics. C++'s templates are just a total mess, all around. Java's generics are kind of a funny compile-time feature and have a ton of limitations. C# generics have some downright nasty interactions with other parts of the type system, like operator overloading.

IIRC the designers of C# have some regrets about how generics and other features were implemented. This is from an in-person talk, I don't have anything to cite.

You should take almost nobody at face value when they talk about language features like generics, because there is almost nobody with direct experience both designing and implementing those features. You should be pretty skeptical about what I'm saying too, IMO. But do believe that the design tradeoffs for generics are a complicated enough to justify the wait.

The Golang approach seems to strike a balance between extreme approaches. The C++ approach is "pay for what you use" which, in practice, is actually an extremist language design philosophy. In C++ / Rust, you are supposed to pay for templates only in code size and not in runtime. Everything is fully instantiated. The Haskell approach is "one abstraction fits all, everything is a pointer, use an implementation dictionary, monomorphization is an optimization". Again, something of an extremist approach (similar to Java's, but the comparison with Go / Haskell is better because Go / Haskell both use implementation dictionaries).

A middle approach is actually somewhat novel, believe it or not.

Re: How generics are implemented in Go 1.18

#16
I thought this was something like traits, but it goes way beyond that.

Sub-dictionaries are described here: https://github.com/golang/proposal/blob/master/design/generi...

It looks like the compiler needs to walk down the entire call tree from the top-level generic and then compute new dictionaries for each called function. Since the compiler may not know the entire call tree, it may have to build nested dictionaries.

Wacky stuff!

Re: How generics are implemented in Go 1.18

#17

Earlier quoted context omitted.

The compile time issues for C++ are entirely because of the creaky header mechanism that doesn't permit efficient parsing. Generics have worked fine in Ada since its inception. Any modern language can adopt the same process of tracking a formal abstract interface that is parsed once and expanded into concrete code as necessary.

Rust also has (relatively) bad compile times due to generics. Not as bad as C++, but you can notice it's significantly worse than Go.

D, Ada, Eiffel, Delphi go as counter example, and C++ modules are already proving a much better experience in VC++.

Re: How generics are implemented in Go 1.18

#19
post #3

Earlier quoted context omitted.

In a nutshell, torn between the extreme ends of high compile-time cost and large code size of a C++ flavored implementation and the high runtime cost and dangers of boxing/unboxing (Java), Golang opted for "none of the above" and tried to limit complexity drivers / powerfulness / expressiveness / usefulness instead, keeping the impact on both compile time and run time low. About how well that decision will turn out i…

This summary concisely captures the key thing about generics that has kept them out of Go for so long: they weren't created in a vacuum. Go's developers had the flaws in C++ and Java's approaches to draw on in their attempt to find a better approach. Many people calling for generics to have been implemented sooner were fine with those flaws in the other languages, but the Go team wanted to do better than that.

Generics exist in languages since 1976, more than enough examples than focusing on C++ and Java.

Re: How generics are implemented in Go 1.18

#20

Disclaimer: I only very occasionally touch Go code. Hasn't this been a very long time coming? Iirc there has been much dispute over this in the community. Can anyone weigh in on what the other options were?

I only occasional do language design / compiler writing projects, or work with compiler internals. Most people are really bad at estimating the implementation complexity and tradeoffs inherent in various language features. I'd say that C++ serves as a warning to others... think before you add features to your language, or you'll end up a total mess, like C++. Java and C# gave us some interesting and subtle lessons ab…

C++ still has the dubious honor of being the only language where I encountered code that I could not compile because my machine lacked enough memory.

I'm sure that's possible in other languages, but the program I was trying to compile wasn't that complicated... It had just been written by someone who believed every concrete class needed an abstract interface it was implementing.

Post reply on HN