44 ms·

How generics are implemented in Go 1.18

288 points by komuW 5y ago

elromulous 5y ago
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?
- endymi0n 5y ago
  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 in practice, we'll start to know soon.
  - kevin_thibedeau 5y ago
    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.
    - FooBarWidget 5y ago
      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.
      - pjmlp 5y ago
        D, Ada, Eiffel, Delphi go as counter example, and C++ modules are already proving a much better experience in VC++.
        FooBarWidget 5y ago
        Delphi didn't have generics. Not sure about more modern versions, but the power of the generics also impacts compile times. Java generics barely impact compile times at all but they're also nowhere as powerful as Rust and C++ ones.
        pjmlp 5y ago
        You stop using Delphi long time ago, I would say. To pick one of my examples, D templates and compile time metaprogramming are even more powerfull than Rust and C++ ones, yet it compiles just as fast.
        benibela 5y ago
        Delphi added generics in 2009 So it had them roughly as long as Go existed
      - yakubin 5y ago
        Rust does compile slower than Go, but it's not due to generics. It's mostly due to LLVM codegen and procedural macros. Go has the benefit of not relying on LLVM and not having procedural macros.
        codeflo 5y ago
        Absolutely true. I’d add that Rust is also doing a lot more expensive optimizations in release builds.
        jcelerier 5y ago
        Until recently Go didn't even use registers for passing arguments, it just put everything on the stack like in a 1965 textbook (https://go.googlesource.com/proposal/+/refs/changes/78/248178/1/design/40724-register-calling.md https://go.googlesource.com/proposal/+/refs/changes/78/24817...)
        eloff 5y ago
        If you mean for function calls, I believe you're correct, not taking into account inline functions. However, for code generation Go obviously uses registers since way before the 1.0 days.
        edflsafoiewq 5y ago
        A lot of the IR comes from expanding huge stacks of generic functions. I don't think the issue can't be neatly partitioned up like that.
        geodel 5y ago
        You are right of course about LLVM being source of slowness. In general discussion I see around is that all Rust's perf optimizations are to Rust's credit (nothing about LLVM optimization) while all woes around Rust's compile time lay at step of LLVM and Rust is not be blamed.
      - vyskocilm 5y ago
        There is tinygo with llvm backend and the build times are abysmal.
    - kenniskrag 5y ago
      Isn't that solved with c++ modules [1]? [1] https://en.cppreference.com/w/cpp/language/modules https://en.cppreference.com/w/cpp/language/modules
      - pjmlp 5y ago
        Yes, with VC++ offering the best experience currently.
        throwaway2037 5y ago
        I am confused. Why was this downvoted? Is GCC and Clang doing better? (Or another C++ compiler?)
        Kranar 5y ago
        Because the answer is false, modules do not solve the problem of having common/shared template instantiations. As for the comment about MSVC, it's mostly off topic, doesn't relate to the question that was asked (which had nothing to do with which compiler provides the best experience), and even if you accept that MSVC provides the best module experience, it's support for it is still very buggy and not suitable for anything other than experimenting and beta testing.
      - Kranar 5y ago
        Not really, in C++ templates still need to be instantiated in every module but modules don't have to each repeat the parsing of template definitions. The module that declares the template will do the job of parsing the template and producing some intermediate representation of it that other modules can consume. Okay that does save some amount of time but the overwhelming majority of time spent compiling templates is in instantiating them, not parsing them from literal text into an AST. Modules don't make instantiating templates any faster, it only makes parsing them faster.
        pjmlp 5y ago
        They sure do, make the most common expansions avaiable as extern templates.
    - josephg 5y ago
      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.
      - deleted 5y ago
        [deleted]
      - xigoi 5y ago
        Increases compared to what? If you don't use generics and write the code for each type manually, you'll end up with exactly the same thing.
        pshc 5y ago
        Increased compile time compared to doing polymorphism with an extra layer of indirection, I’m guessing
        zwieback 5y ago
        I often wonder about that - if I was going to write by hand I might end up extracting a simple interface, do some type coercion/promotion or some other trick to reduce the number of functions I need to write. I read about how .Net does Generics at the VM level and was very impressed, a good compromise between C++ "macro expansion" and Java "type erasure", both of which seem extreme. At the end of the day, though, when generics are present I stop worrying and just use List<int>, List<float>, List<char>, etc. without a second thought. The compiler, VM or runtime can deal with it although I might get punished in some way.
      - yakubin 5y ago
        Although monomorphization takes a significant chunk of a typical Rust compilation, it pales in comparison to LLVM codegen and execution of procedural macros. So although it's academically worthy of note, optimization-wise it's not where the focus should be. Personally, I'd like to see someday a Rust compiler which is not based on LLVM. Both Zig and Jai compile much faster when using their non-LLVM backends than when using LLVM, so Rust is not the odd one here either.
    - nicoburns 5y ago
      That's not true, Rust doesn't have those headers and has the same compile time issues as C++.
      - the-smug-one 5y ago
        Rust has macros and an expensive type system though, and compilation is getting faster.
  - shadowgovt 5y ago
    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.
    - pjmlp 5y ago
      Generics exist in languages since 1976, more than enough examples than focusing on C++ and Java.
      - shadowgovt 5y ago
        good point! What could the Go team glean from those languages to improve Go's generics implementation?
        pjmlp 5y ago
        Lots of things, here is their acknowledgement that it was a mistake to ignore them. > we were biased too much by experience with C++ without concepts and Java generics. https://go.googlesource.com/proposal/+/master/design/go2draft-generics-overview.md https://go.googlesource.com/proposal/+/master/design/go2draf...
    - kaba0 5y ago
      If they wanted to avoid problems they would have implemented the feature right away, instead of making it a second thought for a supposedly modern language.
  - Banana699 5y ago
    C# also made a similar tradeoff between purely generative generics of C++ and the type-erased generics of Java.
- qbasic_forever 5y ago
  > Hasn't this been a very long time coming? That's a feature not a bug of golang. Major language changes like this by design are supposed to take a lot of time and thought to land.
- klodolph 5y ago
  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.
  - shadowgovt 5y ago
    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.
    - klodolph 5y ago
- deleted 5y ago
  [deleted]
edem 5y ago
- hactually 5y ago
  Too late for what?
kevingadd 5y ago
This approach (sharing code for various generic instances and passing in a blob of type information) is used for generics in some other languages/runtime environments - for example .NET will in many cases do code sharing like this where it will generate a reusable generic function that operates over many types and then pass it type information so it can operate properly instead of having to generate 50 different versions of a function like a C++ compiler does. This obviously can have some performance implications, but it makes sense to do it (especially in Go's case where what came before it was tons of virtual calls anyway). In .NET on Windows you can sometimes observe this because generic types in your stack traces (in the debugger) will be replaced with 'System.__Canon' [https://twitter.com/matthewwarren/status/1161249300401311745 https://twitter.com/matthewwarren/status/1161249300401311745] instead of the actual type - this indicates that the type was completely erased, so the current function could be running for any number of types and the type can't be identified based on the current instruction pointer. The shared code + blob approach becomes more necessary in an AOT compiled environment like Go (and you'll see it used more in AOT compiled modes for .NET) since you can no longer rely on being able to on-demand JIT some optimized code when a new type shows up.
c-linkage 5y ago
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/generics-implementation-gcshape.md#subdictionaries 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!
- codeflo 5y ago
  From the article you linked, those subdictionaries seem to support calling a function g[T1] inside a function f[T1, T2]. There’s a concept called polymorphic recursion, supported by languages like Haskell, which goes beyond that and allows using arbitrary derived types in a function, in particular, in recursive calks. My interpretation of the section in “non-monomorphisable functions” in the original article is that Go’s compilation strategy doesn’t handle that currently.
  - Ericson2314 5y ago
    These "GC shapes" a lot like GHC's "runtime reps": https://hackage.haskell.org/package/base-4.16.0.0/docs/GHC-Exts.html#t:RuntimeRep https://hackage.haskell.org/package/base-4.16.0.0/docs/GHC-E... GHC allows recursion that is "polymorphic in the types" but "monomorphic in the runtime reps". There is no reason why Go shouldn't allow polymorphic recursion that is "monomorphic in the gc shapes" either, though they might not have bothered to allow it yet.
    - lalaithion 5y ago
      I think they do; the problem is that Go puts way less things behind a pointer than Haskell does. Every struct is its own runtime representation. If you change the example in https://github.com/golang/go/issues/48018 https://github.com/golang/go/issues/48018 to use a pointer indirection, I think it should work.
shadowgovt 5y ago
Something I haven't been able to pull up yet: what does the addition of generics do the `reflect` package? I assume it needs to be extended to deal with reflection through generics?
- jerf 5y ago
  All types are concrete at run time, so, no it doesn't end up needing changes: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#reflection https://go.googlesource.com/proposal/+/refs/heads/master/des... "We do not propose to change the reflect package in any way. When a type or function is instantiated, all of the type parameters will become ordinary non-generic types. The String method of a reflect.Type value of an instantiated type will return the name with the type arguments in square brackets. For example, List[int]. "It's impossible for non-generic code to refer to generic code without instantiating it, so there is no reflection information for uninstantiated generic types or functions."
  - Ericson2314 5y ago
    Note that with this change, only "gcshapes" are static at runtime. Any other information reflection needs would have to come from the dictionary. That would bloat the dictionaries.
cryptos 5y ago
Do Go generics support covariance and contravariance?
- Kranar 5y ago
  Go does not have subtypes, so your question is not applicable.
  - lamontcg 5y ago
    Can you use generics to create a container of an interface or does it only support concrete types as generics?
    - deleted 5y ago
      [deleted]
    - deleted 5y ago
      [deleted]
  - whateveracct 5y ago
    It does have subtyping relationships via interface. It absolutely has subtypes in the co/contravariance. In theory, a slice of structs that implement an interface should be able to be used as a slice of that interface. But due to the implementation, that requires a full copy.
    - ithkuil 5y ago
      No it's not due to the implementation, it's due to the language specification: there is no general subtyping. You can see it this way: there is implicit syntactic sugar that creates an interface value (pointer + type info) when you assign a value of type T to a variable of type interface I where T implements I. This happens on variable assignment, function parameter bindings and return value bindings. A slice of Is is just a very different type from a slice of Ts. The assignment magic sugar works, but it works at the level of slice elements, not the whole slice.
colesantiago 5y ago
When is generics officially coming into Go? I thought it would be in February as promised?
- belak 5y ago
  The original plan was to release in February, but in the Beta 2 release [1], they said this: "Because we are taking the time to issue a second beta, we now expect that the Go 1.18 release candidate will be issued in February, with the final Go 1.18 release in March." It looks like there are still a few release blockers [2]. I'd imagine RC is fairly soon though. EDIT: as mentioned by _fz_ below, RC1 has already released. Seems like the full release will most likely still be in March. [1]: https://go.dev/blog/go1.18beta2 https://go.dev/blog/go1.18beta2 [2]: https://github.com/golang/go/issues?q=is%3Aopen+label%3Arelease-blocker+milestone%3AGo1.18 https://github.com/golang/go/issues?q=is%3Aopen+label%3Arele...
  - _fz_ 5y ago
    > I'd imagine RC is fairly soon though. RC1 was released two weeks ago.
    - belak 5y ago
      Thanks! Good catch! I was going off blog posts and didn't see that there was a download for RC1.
    - LukeShu 5y ago
      Well, not quite 2 weeks ago; it'll be 2 weeks on Thursday. I say this because policy is to issue a release "no sooner than two weeks after" issuing the release candidate. https://go.dev/s/release https://go.dev/s/release
- aaronbee 5y ago
  go1.18 is coming out soon with generics. The first release candidate came out 2 weeks ago. You can track the open issues here: https://github.com/golang/go/milestone/201 https://github.com/golang/go/milestone/201
layer8 5y ago
Does Go support separate compilation? The approach sounds like a change in the implementation of a generic function (changing the gcshapes) could cause client code to break unless it is recompiled as well. What am I missing?
- whateveracct 5y ago
  Go is all from source
  - Groxx 5y ago
    Except for plugins. But plugins are pretty darn niche, and feel more experimental than anything: https://pkg.go.dev/plugin https://pkg.go.dev/plugin
    - LukeShu 5y ago
      Note that if a plugin and the main program have any packages in common, the build-hash (Go binaries include a hash for each included package) must be identical between the program and the plugin. If the hashes don't match, then the program's `plugin.Open(…)` call will return an error. So if there is a package in common such that an implementation change could cause something like a cgshape change, well the cgshape change won't matter since any implementation change will change the package's build-hash. And so everything will need recompiled anyway, regardless of whether the cgshape changed or not.
      - Groxx 5y ago
        Interesting I hadn't caught that requirement before. It both kinda makes sense and kinda doesn't... and sadly throws some cold water on a few "it'd be fun to try to do X" ideas I've had floating around in my head. I suppose there's always RPC-like options.
      - EE84M3i 5y ago
        Does this even include the standard library?
slx26 5y ago
Programming languages are lacking because they are too stuck in the "implementation plane" while trying to deal with lots of "system design" problems. Generics, traits, interfaces, union types and others are fundamentally targeted at giving developers more expressive power to describe the systems we are designing. We know there are many parts we could swap around, using different implementations, connecting some pieces here and there... and the system should make sense and work. We can see that it must work! But these features are trying to resolve problems from a very closely-connected but still different domain, and that's why we see so much friction when trying to use them. We try to encode system-level patterns in the implementation, and there's gonna be friction. We can see that these features give us power, and that's why we like them, but we also see the problems they cause, and that's when we get cold feet and say "yeah... maybe it's not such a great idea". I'm actually really happy to get generics in golang, and I'm happy with the team giving it as much thought as they need, but we are only gonna get so far within the current paradigm of trying to model the universe from a few text files. Generics are nice, but we shall do better in the future!
- geodel 5y ago
  Right. Basically Go team is lacking big picture thinkers like this[1] 1. https://dilbert.com/strip/1994-12-17 https://dilbert.com/strip/1994-12-17
  - zozbot234 5y ago
    Go generics were designed with plenty of cooperation from the PL research community. While some complexity to the design may be unavoidable, it's the farthest thing from just having a hacked-together feature with no "big picture" thinking underneath. Very similar to how generics were added to Java, in fact/
  - slx26 5y ago
    Golang is my favorite language, and I really like the approach that the team takes. A few days ago I shared here some interesting comments from Griesemer on Golang enums. But sure, let's not give any ideas or question anything ever again, someone might get offended.
majewsky 5y ago
By the way, are there any projects underway to produce a library of the most common basic template functions? I'm very much looking forward to unifying some of my most copy-pasted functions when 1.18 is out, but I would like to unify on a central library right away.
- ainar-g 5y ago
  It's partially being done in the x/exp module to prototype it thoroughly before including it into the stdlib. See: * https://pkg.go.dev/golang.org/x/exp/constraints https://pkg.go.dev/golang.org/x/exp/constraints * https://pkg.go.dev/golang.org/x/exp/maps https://pkg.go.dev/golang.org/x/exp/maps * https://pkg.go.dev/golang.org/x/exp/slices https://pkg.go.dev/golang.org/x/exp/slices
  - vlunkr 5y ago
    Cool. I'd love to see this become part of the stdlib rather than competing external packages.
    - newuser94303 5y ago
      If it becomes part of the stdlib, the update cycle will match the language. For now, improvements will come a lot faster as an external package
    - dpatterbee 5y ago
      I believe the goal is for stdlib packages to be added with 1.19 once they have some real-world use. For now they're in x/exp to allow changes before that release.
    - shp0ngle 5y ago
      They want to be able to break backwards compatibility, so they can experiment more. If they put it in stdlib, they cannot break it anymore.
mbrodersen 5y ago
I think the Haskell compiler GHC is using a similar approach (directories) to implement type classes.
kerkeslager 5y ago
So maybe 7-8 years ago, I got into a bunch of arguments with people on Hacker News because I said that Go's type system was ineffective without generics. At that time, Gophers leaped to defend it, going so far as to say that it's better because it's simple. Oh and it was really important to Gophers that Go compiles in a single pass (which I argued is only relevant for truly enormous codebases like Google's). A few years later we had go generate. Which I argued was a glorified C macro system to get around the lack of generics. Oh and everybody forgot about the single-pass thing, I guess. Now in this thread there are a bunch of people commenting that they can't wait to combine all their copy pasted code using a generics which are implemented via a tree traversal that actually kind of complicated the idea of what a pass even is (I think memoization could make this linear, but at the cost of memory?). This is a language that seemingly insists on breaking the wheel. Notice I didn't say reinventing, because in over a decade they haven't actually gotten a working version of the wheel out yet. I mean seriously, Go was released in 2009: if I'm not mistaken, C# had a pretty good generic system already, and there were a bunch of other workable options to copy from less-mainstream languages. Not that copying has helped: they copied coroutines from other languages, but failed to present a coherent memory sharing model (just copy Erlang FFS), which severely limits the usefulness of coroutines. Every few years someone gets me to try Go out again and I discover, yet again, that it's still struggling with problems that were solved before it existed. It's a shame that this language has stolen so much mind share from more deserving languages.
- agumonkey 5y ago
  The cycles and waves in human groups is pretty weird to witness.
- vgchh 5y ago
  Well let perfect not be the enemy of the good. The reality is that Go is wildly successful in practice for good reasons that have been hashed numerous times. As a result tons of Cloud software is written in Go. There is nothing Go needs to be ashamed on. Its mindshare is a result of a good choice people made at a certain point in time. A better language will win at its own merits.
  - 5y ago
sigmaml 5y ago
I made a crude proposal for generics in 2011[1], in which I proposed a pair of concepts ("storage class" and "type class") that are somewhat similar to the concept of this "gcshape". I proposed it as a compromise between full monomorphisation and runtime code generation. [1] http://oneofmanyworlds.blogspot.com/2011/11/draft-2-of-proposal-for-generics-in-go.html http://oneofmanyworlds.blogspot.com/2011/11/draft-2-of-propo...

288 points by komuW 5y ago

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?

endymi0n 5y ago
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 in practice, we'll start to know soon.
- kevin_thibedeau 5y ago
  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.
  - FooBarWidget 5y ago
    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.
    - pjmlp 5y ago
      D, Ada, Eiffel, Delphi go as counter example, and C++ modules are already proving a much better experience in VC++.
      - FooBarWidget 5y ago
        Delphi didn't have generics. Not sure about more modern versions, but the power of the generics also impacts compile times. Java generics barely impact compile times at all but they're also nowhere as powerful as Rust and C++ ones.
        pjmlp 5y ago
        You stop using Delphi long time ago, I would say. To pick one of my examples, D templates and compile time metaprogramming are even more powerfull than Rust and C++ ones, yet it compiles just as fast.
        benibela 5y ago
        Delphi added generics in 2009 So it had them roughly as long as Go existed
    - yakubin 5y ago
      Rust does compile slower than Go, but it's not due to generics. It's mostly due to LLVM codegen and procedural macros. Go has the benefit of not relying on LLVM and not having procedural macros.
      - codeflo 5y ago
        Absolutely true. I’d add that Rust is also doing a lot more expensive optimizations in release builds.
        jcelerier 5y ago
        Until recently Go didn't even use registers for passing arguments, it just put everything on the stack like in a 1965 textbook (https://go.googlesource.com/proposal/+/refs/changes/78/248178/1/design/40724-register-calling.md https://go.googlesource.com/proposal/+/refs/changes/78/24817...)
        eloff 5y ago
        If you mean for function calls, I believe you're correct, not taking into account inline functions. However, for code generation Go obviously uses registers since way before the 1.0 days.
      - edflsafoiewq 5y ago
        A lot of the IR comes from expanding huge stacks of generic functions. I don't think the issue can't be neatly partitioned up like that.
      - geodel 5y ago
        You are right of course about LLVM being source of slowness. In general discussion I see around is that all Rust's perf optimizations are to Rust's credit (nothing about LLVM optimization) while all woes around Rust's compile time lay at step of LLVM and Rust is not be blamed.
    - vyskocilm 5y ago
      There is tinygo with llvm backend and the build times are abysmal.
  - kenniskrag 5y ago
    Isn't that solved with c++ modules [1]? [1] https://en.cppreference.com/w/cpp/language/modules https://en.cppreference.com/w/cpp/language/modules
    - pjmlp 5y ago
      Yes, with VC++ offering the best experience currently.
      - throwaway2037 5y ago
        I am confused. Why was this downvoted? Is GCC and Clang doing better? (Or another C++ compiler?)
        Kranar 5y ago
        Because the answer is false, modules do not solve the problem of having common/shared template instantiations. As for the comment about MSVC, it's mostly off topic, doesn't relate to the question that was asked (which had nothing to do with which compiler provides the best experience), and even if you accept that MSVC provides the best module experience, it's support for it is still very buggy and not suitable for anything other than experimenting and beta testing.
    - Kranar 5y ago
      Not really, in C++ templates still need to be instantiated in every module but modules don't have to each repeat the parsing of template definitions. The module that declares the template will do the job of parsing the template and producing some intermediate representation of it that other modules can consume. Okay that does save some amount of time but the overwhelming majority of time spent compiling templates is in instantiating them, not parsing them from literal text into an AST. Modules don't make instantiating templates any faster, it only makes parsing them faster.
      - pjmlp 5y ago
        They sure do, make the most common expansions avaiable as extern templates.
  - josephg 5y ago
    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.
    - deleted 5y ago
      [deleted]
    - xigoi 5y ago
      Increases compared to what? If you don't use generics and write the code for each type manually, you'll end up with exactly the same thing.
      - pshc 5y ago
        Increased compile time compared to doing polymorphism with an extra layer of indirection, I’m guessing
      - zwieback 5y ago
        I often wonder about that - if I was going to write by hand I might end up extracting a simple interface, do some type coercion/promotion or some other trick to reduce the number of functions I need to write. I read about how .Net does Generics at the VM level and was very impressed, a good compromise between C++ "macro expansion" and Java "type erasure", both of which seem extreme. At the end of the day, though, when generics are present I stop worrying and just use List<int>, List<float>, List<char>, etc. without a second thought. The compiler, VM or runtime can deal with it although I might get punished in some way.
    - yakubin 5y ago
      Although monomorphization takes a significant chunk of a typical Rust compilation, it pales in comparison to LLVM codegen and execution of procedural macros. So although it's academically worthy of note, optimization-wise it's not where the focus should be. Personally, I'd like to see someday a Rust compiler which is not based on LLVM. Both Zig and Jai compile much faster when using their non-LLVM backends than when using LLVM, so Rust is not the odd one here either.
  - nicoburns 5y ago
    That's not true, Rust doesn't have those headers and has the same compile time issues as C++.
    - the-smug-one 5y ago
      Rust has macros and an expensive type system though, and compilation is getting faster.
- shadowgovt 5y ago
  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.
  - pjmlp 5y ago
    Generics exist in languages since 1976, more than enough examples than focusing on C++ and Java.
    - shadowgovt 5y ago
      good point! What could the Go team glean from those languages to improve Go's generics implementation?
      - pjmlp 5y ago
        Lots of things, here is their acknowledgement that it was a mistake to ignore them. > we were biased too much by experience with C++ without concepts and Java generics. https://go.googlesource.com/proposal/+/master/design/go2draft-generics-overview.md https://go.googlesource.com/proposal/+/master/design/go2draf...
  - kaba0 5y ago
    If they wanted to avoid problems they would have implemented the feature right away, instead of making it a second thought for a supposedly modern language.
- Banana699 5y ago
  C# also made a similar tradeoff between purely generative generics of C++ and the type-erased generics of Java.
qbasic_forever 5y ago
> Hasn't this been a very long time coming? That's a feature not a bug of golang. Major language changes like this by design are supposed to take a lot of time and thought to land.
klodolph 5y ago
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.
- shadowgovt 5y ago
  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.
  - klodolph 5y ago
deleted 5y ago
[deleted]

edem 5y ago

hactually 5y ago
Too late for what?

kevingadd 5y ago

This approach (sharing code for various generic instances and passing in a blob of type information) is used for generics in some other languages/runtime environments - for example .NET will in many cases do code sharing like this where it will generate a reusable generic function that operates over many types and then pass it type information so it can operate properly instead of having to generate 50 different versions of a function like a C++ compiler does. This obviously can have some performance implications, but it makes sense to do it (especially in Go's case where what came before it was tons of virtual calls anyway). In .NET on Windows you can sometimes observe this because generic types in your stack traces (in the debugger) will be replaced with 'System.__Canon' [https://twitter.com/matthewwarren/status/1161249300401311745 https://twitter.com/matthewwarren/status/1161249300401311745] instead of the actual type - this indicates that the type was completely erased, so the current function could be running for any number of types and the type can't be identified based on the current instruction pointer. The shared code + blob approach becomes more necessary in an AOT compiled environment like Go (and you'll see it used more in AOT compiled modes for .NET) since you can no longer rely on being able to on-demand JIT some optimized code when a new type shows up.

c-linkage 5y ago

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/generics-implementation-gcshape.md#subdictionaries 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!

codeflo 5y ago
From the article you linked, those subdictionaries seem to support calling a function g[T1] inside a function f[T1, T2]. There’s a concept called polymorphic recursion, supported by languages like Haskell, which goes beyond that and allows using arbitrary derived types in a function, in particular, in recursive calks. My interpretation of the section in “non-monomorphisable functions” in the original article is that Go’s compilation strategy doesn’t handle that currently.
- Ericson2314 5y ago
  These "GC shapes" a lot like GHC's "runtime reps": https://hackage.haskell.org/package/base-4.16.0.0/docs/GHC-Exts.html#t:RuntimeRep https://hackage.haskell.org/package/base-4.16.0.0/docs/GHC-E... GHC allows recursion that is "polymorphic in the types" but "monomorphic in the runtime reps". There is no reason why Go shouldn't allow polymorphic recursion that is "monomorphic in the gc shapes" either, though they might not have bothered to allow it yet.
  - lalaithion 5y ago
    I think they do; the problem is that Go puts way less things behind a pointer than Haskell does. Every struct is its own runtime representation. If you change the example in https://github.com/golang/go/issues/48018 https://github.com/golang/go/issues/48018 to use a pointer indirection, I think it should work.

shadowgovt 5y ago

Something I haven't been able to pull up yet: what does the addition of generics do the `reflect` package? I assume it needs to be extended to deal with reflection through generics?

jerf 5y ago
All types are concrete at run time, so, no it doesn't end up needing changes: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#reflection https://go.googlesource.com/proposal/+/refs/heads/master/des... "We do not propose to change the reflect package in any way. When a type or function is instantiated, all of the type parameters will become ordinary non-generic types. The String method of a reflect.Type value of an instantiated type will return the name with the type arguments in square brackets. For example, List[int]. "It's impossible for non-generic code to refer to generic code without instantiating it, so there is no reflection information for uninstantiated generic types or functions."
- Ericson2314 5y ago
  Note that with this change, only "gcshapes" are static at runtime. Any other information reflection needs would have to come from the dictionary. That would bloat the dictionaries.

cryptos 5y ago

Do Go generics support covariance and contravariance?

Kranar 5y ago
Go does not have subtypes, so your question is not applicable.
- lamontcg 5y ago
  Can you use generics to create a container of an interface or does it only support concrete types as generics?
  - deleted 5y ago
    [deleted]
  - deleted 5y ago
    [deleted]
- whateveracct 5y ago
  It does have subtyping relationships via interface. It absolutely has subtypes in the co/contravariance. In theory, a slice of structs that implement an interface should be able to be used as a slice of that interface. But due to the implementation, that requires a full copy.
  - ithkuil 5y ago
    No it's not due to the implementation, it's due to the language specification: there is no general subtyping. You can see it this way: there is implicit syntactic sugar that creates an interface value (pointer + type info) when you assign a value of type T to a variable of type interface I where T implements I. This happens on variable assignment, function parameter bindings and return value bindings. A slice of Is is just a very different type from a slice of Ts. The assignment magic sugar works, but it works at the level of slice elements, not the whole slice.

colesantiago 5y ago

When is generics officially coming into Go? I thought it would be in February as promised?

belak 5y ago
The original plan was to release in February, but in the Beta 2 release [1], they said this: "Because we are taking the time to issue a second beta, we now expect that the Go 1.18 release candidate will be issued in February, with the final Go 1.18 release in March." It looks like there are still a few release blockers [2]. I'd imagine RC is fairly soon though. EDIT: as mentioned by _fz_ below, RC1 has already released. Seems like the full release will most likely still be in March. [1]: https://go.dev/blog/go1.18beta2 https://go.dev/blog/go1.18beta2 [2]: https://github.com/golang/go/issues?q=is%3Aopen+label%3Arelease-blocker+milestone%3AGo1.18 https://github.com/golang/go/issues?q=is%3Aopen+label%3Arele...
- _fz_ 5y ago
  > I'd imagine RC is fairly soon though. RC1 was released two weeks ago.
  - belak 5y ago
    Thanks! Good catch! I was going off blog posts and didn't see that there was a download for RC1.
  - LukeShu 5y ago
    Well, not quite 2 weeks ago; it'll be 2 weeks on Thursday. I say this because policy is to issue a release "no sooner than two weeks after" issuing the release candidate. https://go.dev/s/release https://go.dev/s/release
aaronbee 5y ago
go1.18 is coming out soon with generics. The first release candidate came out 2 weeks ago. You can track the open issues here: https://github.com/golang/go/milestone/201 https://github.com/golang/go/milestone/201

layer8 5y ago

Does Go support separate compilation? The approach sounds like a change in the implementation of a generic function (changing the gcshapes) could cause client code to break unless it is recompiled as well. What am I missing?

whateveracct 5y ago
Go is all from source
- Groxx 5y ago
  Except for plugins. But plugins are pretty darn niche, and feel more experimental than anything: https://pkg.go.dev/plugin https://pkg.go.dev/plugin
  - LukeShu 5y ago
    Note that if a plugin and the main program have any packages in common, the build-hash (Go binaries include a hash for each included package) must be identical between the program and the plugin. If the hashes don't match, then the program's `plugin.Open(…)` call will return an error. So if there is a package in common such that an implementation change could cause something like a cgshape change, well the cgshape change won't matter since any implementation change will change the package's build-hash. And so everything will need recompiled anyway, regardless of whether the cgshape changed or not.
    - Groxx 5y ago
      Interesting I hadn't caught that requirement before. It both kinda makes sense and kinda doesn't... and sadly throws some cold water on a few "it'd be fun to try to do X" ideas I've had floating around in my head. I suppose there's always RPC-like options.
    - EE84M3i 5y ago
      Does this even include the standard library?

slx26 5y ago

Programming languages are lacking because they are too stuck in the "implementation plane" while trying to deal with lots of "system design" problems. Generics, traits, interfaces, union types and others are fundamentally targeted at giving developers more expressive power to describe the systems we are designing. We know there are many parts we could swap around, using different implementations, connecting some pieces here and there... and the system should make sense and work. We can see that it must work! But these features are trying to resolve problems from a very closely-connected but still different domain, and that's why we see so much friction when trying to use them. We try to encode system-level patterns in the implementation, and there's gonna be friction. We can see that these features give us power, and that's why we like them, but we also see the problems they cause, and that's when we get cold feet and say "yeah... maybe it's not such a great idea". I'm actually really happy to get generics in golang, and I'm happy with the team giving it as much thought as they need, but we are only gonna get so far within the current paradigm of trying to model the universe from a few text files. Generics are nice, but we shall do better in the future!

geodel 5y ago
Right. Basically Go team is lacking big picture thinkers like this[1] 1. https://dilbert.com/strip/1994-12-17 https://dilbert.com/strip/1994-12-17
- zozbot234 5y ago
  Go generics were designed with plenty of cooperation from the PL research community. While some complexity to the design may be unavoidable, it's the farthest thing from just having a hacked-together feature with no "big picture" thinking underneath. Very similar to how generics were added to Java, in fact/
- slx26 5y ago
  Golang is my favorite language, and I really like the approach that the team takes. A few days ago I shared here some interesting comments from Griesemer on Golang enums. But sure, let's not give any ideas or question anything ever again, someone might get offended.

majewsky 5y ago

By the way, are there any projects underway to produce a library of the most common basic template functions? I'm very much looking forward to unifying some of my most copy-pasted functions when 1.18 is out, but I would like to unify on a central library right away.

ainar-g 5y ago
It's partially being done in the x/exp module to prototype it thoroughly before including it into the stdlib. See: * https://pkg.go.dev/golang.org/x/exp/constraints https://pkg.go.dev/golang.org/x/exp/constraints * https://pkg.go.dev/golang.org/x/exp/maps https://pkg.go.dev/golang.org/x/exp/maps * https://pkg.go.dev/golang.org/x/exp/slices https://pkg.go.dev/golang.org/x/exp/slices
- vlunkr 5y ago
  Cool. I'd love to see this become part of the stdlib rather than competing external packages.
  - newuser94303 5y ago
    If it becomes part of the stdlib, the update cycle will match the language. For now, improvements will come a lot faster as an external package
  - dpatterbee 5y ago
    I believe the goal is for stdlib packages to be added with 1.19 once they have some real-world use. For now they're in x/exp to allow changes before that release.
  - shp0ngle 5y ago
    They want to be able to break backwards compatibility, so they can experiment more. If they put it in stdlib, they cannot break it anymore.

mbrodersen 5y ago

I think the Haskell compiler GHC is using a similar approach (directories) to implement type classes.

kerkeslager 5y ago

So maybe 7-8 years ago, I got into a bunch of arguments with people on Hacker News because I said that Go's type system was ineffective without generics. At that time, Gophers leaped to defend it, going so far as to say that it's better because it's simple. Oh and it was really important to Gophers that Go compiles in a single pass (which I argued is only relevant for truly enormous codebases like Google's). A few years later we had go generate. Which I argued was a glorified C macro system to get around the lack of generics. Oh and everybody forgot about the single-pass thing, I guess. Now in this thread there are a bunch of people commenting that they can't wait to combine all their copy pasted code using a generics which are implemented via a tree traversal that actually kind of complicated the idea of what a pass even is (I think memoization could make this linear, but at the cost of memory?). This is a language that seemingly insists on breaking the wheel. Notice I didn't say reinventing, because in over a decade they haven't actually gotten a working version of the wheel out yet. I mean seriously, Go was released in 2009: if I'm not mistaken, C# had a pretty good generic system already, and there were a bunch of other workable options to copy from less-mainstream languages. Not that copying has helped: they copied coroutines from other languages, but failed to present a coherent memory sharing model (just copy Erlang FFS), which severely limits the usefulness of coroutines. Every few years someone gets me to try Go out again and I discover, yet again, that it's still struggling with problems that were solved before it existed. It's a shame that this language has stolen so much mind share from more deserving languages.

agumonkey 5y ago
The cycles and waves in human groups is pretty weird to witness.
vgchh 5y ago
Well let perfect not be the enemy of the good. The reality is that Go is wildly successful in practice for good reasons that have been hashed numerous times. As a result tons of Cloud software is written in Go. There is nothing Go needs to be ashamed on. Its mindshare is a result of a good choice people made at a certain point in time. A better language will win at its own merits.
- 5y ago

sigmaml 5y ago

I made a crude proposal for generics in 2011[1], in which I proposed a pair of concepts ("storage class" and "type class") that are somewhat similar to the concept of this "gcshape". I proposed it as a compromise between full monomorphisation and runtime code generation. [1] http://oneofmanyworlds.blogspot.com/2011/11/draft-2-of-proposal-for-generics-in-go.html http://oneofmanyworlds.blogspot.com/2011/11/draft-2-of-propo...