[HN Gopher] How generics are implemented in Go 1.18
___________________________________________________________________
How generics are implemented in Go 1.18
Author : komuW
Score : 172 points
Date : 2022-03-01 18:39 UTC (4 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| slx26 wrote:
| 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!
| [deleted]
| turminal wrote:
| Some of the people behind go are the living example of how far
| you can get with a bunch of text files and a good model around
| them.
|
| (The answer is _very_ far)
| geodel wrote:
| Right. Basically Go team is lacking big picture thinkers like
| this[1]
|
| 1. https://dilbert.com/strip/1994-12-17
| zozbot234 wrote:
| 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/
| kevingadd wrote:
| 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]
| 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.
| cryptos wrote:
| Do Go generics support covariance and contravariance?
| Kranar wrote:
| Go does not have subtypes, so your question is not applicable.
| whateveracct wrote:
| 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.
| codeflo wrote:
| It's not just a random implementation artifact. Since all
| slices in Go are mutable, it logically wouldn't make sense
| to upcast them while keeping the reference. That would mean
| the ability to put other objects in the slice. Same for
| pointers.
|
| That's a basic fact of type safety that people often get
| wrong. For example, the JVM famously allows upcasting
| arrays, with very surprising results.
| ithkuil wrote:
| 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.
| lamontcg wrote:
| Can you use generics to create a container of an interface or
| does it only support concrete types as generics?
| [deleted]
| [deleted]
| colesantiago wrote:
| When is generics officially coming into Go? I thought it would be
| in February as promised?
| [deleted]
| didip wrote:
| 1.18 milestone still have a few issues left.
| https://github.com/golang/go/milestone/201
| belak wrote:
| 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
|
| [2]:
| https://github.com/golang/go/issues?q=is%3Aopen+label%3Arele...
| _fz_ wrote:
| > I'd imagine RC is fairly soon though.
|
| RC1 was released two weeks ago.
| belak wrote:
| Thanks! Good catch! I was going off blog posts and didn't
| see that there was a download for RC1.
| LukeShu wrote:
| 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
| aaronbee wrote:
| 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
| majewsky wrote:
| 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 wrote:
| 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/maps
|
| * https://pkg.go.dev/golang.org/x/exp/slices
| vlunkr wrote:
| Cool. I'd love to see this become part of the stdlib rather
| than competing external packages.
| layer8 wrote:
| 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?
| ainar-g wrote:
| There are "shared" and "c-shared" build modes[1], if that's
| what you mean. The latter is fairly obvious. The former is so
| rarely used that there was a proposal to remove it, but it
| turned out that some people did actually use it, but almost
| exclusively because of license terms.
|
| [1]: https://pkg.go.dev/cmd/go#hdr-Build_modes
| whateveracct wrote:
| Go is all from source
| Groxx wrote:
| Except for plugins. But plugins are pretty darn niche, and
| feel more experimental than anything:
| https://pkg.go.dev/plugin
| LukeShu wrote:
| 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.
| Laremere wrote:
| While (iirc) Go uses caching in its build system internally, it
| builds quickly enough that this is not a concern.
| uluyol wrote:
| This is also true in C++ templates, and C macros for that
| matter.
| edem wrote:
| hactually wrote:
| Too late for what?
| c-linkage wrote:
| 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!
| codeflo wrote:
| 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 wrote:
| These "GC shapes" a lot like GHC's "runtime reps": https://ha
| ckage.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.
| shadowgovt wrote:
| 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 wrote:
| All types are concrete at run time, so, no it doesn't end up
| needing changes:
| 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 wrote:
| 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.
| elromulous wrote:
| 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?
| qbasic_forever wrote:
| > 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.
| endymi0n wrote:
| 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 wrote:
| 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 wrote:
| 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.
| yakubin wrote:
| 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 wrote:
| Absolutely true. I'd add that Rust is also doing a lot
| more expensive optimizations in release builds.
| jcelerier wrote:
| 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/+/ref
| s/changes/78/24817...)
| eloff wrote:
| 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.
| pjmlp wrote:
| D, Ada, Eiffel, Delphi go as counter example, and C++
| modules are already proving a much better experience in
| VC++.
| kenniskrag wrote:
| Isn't that solved with c++ modules [1]?
|
| [1] https://en.cppreference.com/w/cpp/language/modules
| Kranar wrote:
| 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 wrote:
| Yes, with VC++ offering the best experience currently.
| josephg wrote:
| 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.
| jcelerier wrote:
| > 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.
|
| IDK about that. A project I'm working on is template-
| heavy in a major way, entirely header-only (~15kloc of
| this: https://github.com/celtera/avendish/blob/main/inclu
| de/avnd/c... more or less) but with a barely correctly
| set-up dev environment with clang and PCH (a couple lines
| in CMake), ninja and mold, individual rebuilds are pretty
| much instant ; a complete rebuild which on my machine
| builds 49 libraries and 38 executables takes a whopping 7
| seconds, CMake included.
| [deleted]
| yakubin wrote:
| 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 wrote:
| > Although monomorphization takes a significant chunk of
| a typical Rust compilation, it pales in comparison to
| LLVM codegen
|
| It's not the monomorphization itself that takes a long
| time, it's the LLVM codegen due to all the extra code
| being generated from duplicated function implementations.
| I've heard macros slow for largely the same reason, it's
| not the macro execution itself that's slow, it's
| compiling all the generated code.
| xigoi wrote:
| 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.
| zwieback wrote:
| 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.
| pshc wrote:
| Increased compile time compared to doing polymorphism
| with an extra layer of indirection, I'm guessing
| nicoburns wrote:
| That's not true, Rust doesn't have those headers and has
| the same compile time issues as C++.
| the-smug-one wrote:
| Rust has macros and an expensive type system though, and
| compilation is getting faster.
| shadowgovt wrote:
| 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.
| kaba0 wrote:
| 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.
| pjmlp wrote:
| Generics exist in languages since 1976, more than enough
| examples than focusing on C++ and Java.
| Banana699 wrote:
| C# also made a similar tradeoff between purely generative
| generics of C++ and the type-erased generics of Java.
| klodolph wrote:
| 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.
| jayd16 wrote:
| >C# generics have some downright nasty interactions with
| other parts of the type system, like operator overloading.
|
| Operators are static methods so why is that surprising or
| nasty?
| klodolph wrote:
| It affects method overloading too, I should have said
| "method overloading".
|
| Just take a look at the rules for method overloading in C#,
| or take a look at one of the various C# compilers to see
| how methods are resolved.
| shadowgovt wrote:
| 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 wrote:
| I've done that in lots of languages, but it usually means I
| was trying to crash the compiler :-)
|
| I remember there was some simple way to crash a Haskell
| compiler with an out of memory error by defining a series
| of types, where each successive type required twice as much
| memory as the previous type to represent.
| nosefrog wrote:
| I wasn't able to run the Clojure compiler in 2012 on a $150
| dollar chromebook because it would OOM... but I blame
| myself for that one :P
| [deleted]
___________________________________________________________________
(page generated 2022-03-01 23:00 UTC)