--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/CAB%3Df9xT9%2BYHA5qT2GmUAoQ-ne_a8RWg4uRKDXwSgdn0M5RxdTA%40mail.gmail.com.
But it's not fair to compare it to the container packages both because it will almost certainly perform much better than the container packages, and because the other major limitation of the container packages is usability, which any implementation of generics will address.
On Sep 17, 2020, at 7:24 PM, 'Austin Clements' via golang-dev <golan...@googlegroups.com> wrote:
On Thu, Sep 17, 2020 at 8:16 PM Austin Clements <aus...@google.com> wrote:But it's not fair to compare it to the container packages both because it will almost certainly perform much better than the container packages, and because the other major limitation of the container packages is usability, which any implementation of generics will address.I should clarify why I think it will perform better (partly because Ian said it will carry similar overhead about 60 seconds before I sent this claim :). Because the current containers (at least, the ones no one uses) use interface{}s in the data structures themselves, they force a level of indirection. Both stenciling and dictionary-passing will let us embed values directly in container types, significantly reducing the memory and GC overhead for storing scalar values (and slightly reducing it when storing pointer values by at least eliminating the "type" field implicit in the interface value). I think the container methods themselves would perform similarly to the interface{}-based ones. It will also save on the costs of type assertions for users of the containers, though that cost is probably small right now.
--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/CALgmw1-rfiqzGiwYVOknT5kv2HdnRxh-828cd0oPepS-dbd1LA%40mail.gmail.com.
What stops doing both? A compile time flag or even based on thresholds of generic types used. Similar to how a compiler decides on inlining.
I thought it was already said somewhere that there'd be no point to this whole generics proposal if the implementation carried a runtime cost. I don't think it'll be used as much if it's slow or GC heavy at runtime (like how nobody uses the container packages in std)I'd hope for a hybrid: stenciling but sharing instantiations when they had the same GC bitmap shape.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/CAFzRk0036aTkmR-wT89%3DBWFstPEboTXfAZp-Eq0nLodDaieAqw%40mail.gmail.com.
I believe Swift uses a “dictionary-passing” approach in its implementation of generics. There's a talk on it here: https://youtu.be/ctS8FzqcRugThey have a type system feature called "protocols," which are similar to interfaces. They use witness tables to capture the allocation, copying, and destruction of a value, as well as conform to its protocol.
The Go generics proposal is working its way through the proposal process. It's a very complicated proposal, which begs the question:If the generics proposal is accepted, how are we going to implement it?The Go team at Google has put some thought into this question all along, but we think now is the time to start thinking more seriously and widely about it. Hence this email. Note that the generics proposal is not accepted yet, so we'll have to discuss implementations without having a final accepted proposal in hand. Nevertheless, the outline of the proposal is pretty clear and provides a sufficient basis to consider implementation strategies, even if we might have to revise those strategies if changes to the proposal are forthcoming.Of course, if the proposal is declined we'll have wasted some work. If it is accepted in some form, however, we'll hopefully have accelerated the progress to an implementation.I've written up two design docs containing two possible strategies for implementing generics. They are:
- Stenciling. This strategy generates a separate implementation of a generic function for every instantiation (set of provided type arguments). This is more-or-less how C++ does generics.
- Dictionaries. This strategy generates a single implementation of a generic function which can handle all possible type arguments. This is kind-of how Java does generics, although the analogy is weaker than the stenciling-C++ one.
There may be other implementation strategies (including hybrids of the two above); these two are just to set the ball rolling on discussion.
What do people think? Which strategy do you like? What glaring showstopper are we forgetting?
On Friday, 18 September 2020 at 00:10:14 UTC+2 Keith Randall wrote:The Go generics proposal is working its way through the proposal process. It's a very complicated proposal, which begs the question:If the generics proposal is accepted, how are we going to implement it?The Go team at Google has put some thought into this question all along, but we think now is the time to start thinking more seriously and widely about it. Hence this email. Note that the generics proposal is not accepted yet, so we'll have to discuss implementations without having a final accepted proposal in hand. Nevertheless, the outline of the proposal is pretty clear and provides a sufficient basis to consider implementation strategies, even if we might have to revise those strategies if changes to the proposal are forthcoming.Of course, if the proposal is declined we'll have wasted some work. If it is accepted in some form, however, we'll hopefully have accelerated the progress to an implementation.I've written up two design docs containing two possible strategies for implementing generics. They are:
- Stenciling. This strategy generates a separate implementation of a generic function for every instantiation (set of provided type arguments). This is more-or-less how C++ does generics.
- Dictionaries. This strategy generates a single implementation of a generic function which can handle all possible type arguments. This is kind-of how Java does generics, although the analogy is weaker than the stenciling-C++ one.
There may be other implementation strategies (including hybrids of the two above); these two are just to set the ball rolling on discussion.What do people think? Which strategy do you like? What glaring showstopper are we forgetting?The way I'd write this today is using type switches over interface{} where I need to narrow the type. If the compiler rewrote to that, it would be "zero surprises" for me in terms of performance, so I'm wondering if that was considered before the Dictionaries suggestion? I could imagine many functions just plumb through to others without narrowing types, making dictionaries add overhead (memory and CPU) where it would be surprising to me.
At a high level, stenciling allows for better runtime performance, at the cost of larger binaries and slower compile times. Stenciling is also somewhat simpler to implement in the compiler. But those are generalizations and depend a lot on the code being compiled and the various mitigations (discussed in the design docs) that could be brought to bear.There are also lots of other smaller decisions we'll need to make about generics implementation. How do we modify the compiler's parser? Its internal type representation? What in the runtime needs to understand generics? All of these are also fair game for this discussion.And on a final note, I'd like to brainstorm about prep work we can do now that will make generics easier if/when the proposal gets accepted. We're obviously not going to have generics in for 1.16, but we might want to do some prep work in 1.16 for pieces we know we'll need, or think we'll need, for an eventual generics implementation. For example, I've been working on a prototype of variable-sized frames which would be useful for the dictionary proposal above, but might also be useful for other things, like reflect.Call. Another idea is cleaning up the compiler organization to make it easier to plug in a different typechecker.Process notes:- Let's start discussing the topics outlined above in this email thread. If the discussion gets verbose enough, we might want to move it somewhere else (e.g. a reddit thread). We'll cross that bridge when/if we get to it.- If you have specific edits to the docs linked above, you can mail me a CL.- This discussion is about implementation of the generics proposal, not the generics proposal itself. The line is a bit fuzzy, but if you're unsure you might consider discussing the generics proposal (currently happening on golang-nuts, search for the [generics] subject line) instead of posting here.
--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/9dd39010-d1b5-4de9-8e85-96c06f9c3d93n%40googlegroups.com.
On Fri, 18 Sep 2020 at 00:46, Brad Fitzpatrick <brad...@golang.org> wrote:I thought it was already said somewhere that there'd be no point to this whole generics proposal if the implementation carried a runtime cost. I don't think it'll be used as much if it's slow or GC heavy at runtime (like how nobody uses the container packages in std)I'd hope for a hybrid: stenciling but sharing instantiations when they had the same GC bitmap shape.This is what I'd expect too. It'll still need a dictionary so that you can invoke generic operations (there wouldbe a runtime cost similar to the runtime cost of invoking methods on an interface because method calls wouldbe indirect), but at least you can copy values around and look up items on the stack without extra cost.In general, you can share code between implementations that have the same alignment and GC bitmap shapewithout changing the code generation for function bodies much. I actually prototyped this as an idea some time ago using the current compilerand writing the instantiated code as if it had been generated automatically. I just updated it to use the latestsyntax - it's at https://github.com/rogpeppe/genericdemo and contains a working (well, it's lightly tested at least)version of the graph example from the original generics draft protocol.
On Fri, Sep 18, 2020 at 4:51 AM roger peppe <rogp...@gmail.com> wrote:On Fri, 18 Sep 2020 at 00:46, Brad Fitzpatrick <brad...@golang.org> wrote:I thought it was already said somewhere that there'd be no point to this whole generics proposal if the implementation carried a runtime cost. I don't think it'll be used as much if it's slow or GC heavy at runtime (like how nobody uses the container packages in std)I'd hope for a hybrid: stenciling but sharing instantiations when they had the same GC bitmap shape.This is what I'd expect too. It'll still need a dictionary so that you can invoke generic operations (there wouldbe a runtime cost similar to the runtime cost of invoking methods on an interface because method calls wouldbe indirect), but at least you can copy values around and look up items on the stack without extra cost.In general, you can share code between implementations that have the same alignment and GC bitmap shapewithout changing the code generation for function bodies much. I actually prototyped this as an idea some time ago using the current compilerand writing the instantiated code as if it had been generated automatically. I just updated it to use the latestsyntax - it's at https://github.com/rogpeppe/genericdemo and contains a working (well, it's lightly tested at least)version of the graph example from the original generics draft protocol.There's some discussion in the stenciling doc about deduplicating implementations, which I think would capture the case of two types that have identical GC bitmap shapes. Do you think that would be sufficient, or not?
On Fri, Sep 18, 2020 at 8:43 AM Tommie Gannert <tgan...@gmail.com> wrote:On Friday, 18 September 2020 at 00:10:14 UTC+2 Keith Randall wrote:The Go generics proposal is working its way through the proposal process. It's a very complicated proposal, which begs the question:If the generics proposal is accepted, how are we going to implement it?The Go team at Google has put some thought into this question all along, but we think now is the time to start thinking more seriously and widely about it. Hence this email. Note that the generics proposal is not accepted yet, so we'll have to discuss implementations without having a final accepted proposal in hand. Nevertheless, the outline of the proposal is pretty clear and provides a sufficient basis to consider implementation strategies, even if we might have to revise those strategies if changes to the proposal are forthcoming.Of course, if the proposal is declined we'll have wasted some work. If it is accepted in some form, however, we'll hopefully have accelerated the progress to an implementation.I've written up two design docs containing two possible strategies for implementing generics. They are:
- Stenciling. This strategy generates a separate implementation of a generic function for every instantiation (set of provided type arguments). This is more-or-less how C++ does generics.
- Dictionaries. This strategy generates a single implementation of a generic function which can handle all possible type arguments. This is kind-of how Java does generics, although the analogy is weaker than the stenciling-C++ one.
There may be other implementation strategies (including hybrids of the two above); these two are just to set the ball rolling on discussion.What do people think? Which strategy do you like? What glaring showstopper are we forgetting?The way I'd write this today is using type switches over interface{} where I need to narrow the type. If the compiler rewrote to that, it would be "zero surprises" for me in terms of performance, so I'm wondering if that was considered before the Dictionaries suggestion? I could imagine many functions just plumb through to others without narrowing types, making dictionaries add overhead (memory and CPU) where it would be surprising to me.I'm not entirely sure what you are suggesting. Do you mean that we type-erase, i.e. replace every occurrence of a generic type T with interface{}, then add casts in the appropriate places?I don't think this entirely works. What about:func index[T any](a []T, i int) T {return a[i]
}r := index[int64]([]int64{1,2,3}, 1)We can't just treat []T as []interface{}, because int and interface{} have different sizes, so the indexing computation required is type-dependent.
Same for the return value. The caller is expecting an 8-byte return value, not a 16-byte interface that it needs to cast. Especially if you do:f := index[int64]r := f([]int64{1,2,3}, 1)Maybe we could introduce wrappers functions for situations like this?
--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/CAB%3Df9xT9%2BYHA5qT2GmUAoQ-ne_a8RWg4uRKDXwSgdn0M5RxdTA%40mail.gmail.com.
I too feel that stenciling would be *simpler* to implement. It is not clear to me if slow C++ compile time issues apply here. Presumably each unique concrete type or functions constructed out of generics can be cached?
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/CA7196F5-BC29-4DAD-AB61-279D75E1F4D7%40iitbombay.org.
On Sat, 19 Sep 2020, 06:07 Bakul Shah, <ba...@iitbombay.org> wrote:I too feel that stenciling would be *simpler* to implement. It is not clear to me if slow C++ compile time issues apply here. Presumably each unique concrete type or functions constructed out of generics can be cached?What do you mean by that?
On Sep 19, 2020, at 1:45 AM, minux <mi...@golang.org> wrote:On Sat, Sep 19, 2020 at 3:25 AM roger peppe <rogp...@gmail.com> wrote:On Sat, 19 Sep 2020, 06:07 Bakul Shah, <ba...@iitbombay.org> wrote:I too feel that stenciling would be *simpler* to implement. It is not clear to me if slow C++ compile time issues apply here. Presumably each unique concrete type or functions constructed out of generics can be cached?What do you mean by that?
I think it means that we can make our go build cache caching not only objects built from whole packages,but also unique instantiations of generic functions and methods.In fact, while I thought about this, we probably can split the objects into two parts: non-generic part andgeneric instantiations, while the latter will not be saved in the package object file, but as standaloneobject files that will be pulled in as necessary by the linker. This avoids the other code bloat problemof C++ templates, where the C++ compiler must be conservative and generate implementationfor all used template instantiations in the output object file for each source file and relying on the linkerto dedup them. As the Go compiler knows about the cache, it can check to see if the implementationalready exists before recreating it.
Of course, we still need to be able to inline generic functions/methods, so only those parts that can'tbe inlined should be stored separately in the build cache.Furthermore, such a caching system might be able to support a more generic form of deduplicationby making it a content addressable cache keyed by the object code & its distinguishing metadata(e.g. for structs, only the types of fields are necessary part of the key, the name of the fields can bediscarded.)This generalized deduplication is not limited to generic code though, if we split the package objectfiles up into meaningful smaller parts that are separately cached.
> My thoughts on it
We should not assume that if generics land, that they will only be used as areplacement for current uses of code generation or type assertions. Even afew higher-order functions could cause a binary size and compile-time blowupif they are used everywhere. Things like map/filter/fold, channel manipulationfunctions, or error handling helpers.
> Things like map/filter/fold, channel manipulationfunctions, or error handling helpers.
Didn't though about it indeed. Then the combined approachseems reasonable:1) Generic types and their methods are via stenciling.2) Generic functions with type list constraints are via stenciling too.3) Generic functions with "generic" constraints are dictionary based.This seems mostly OK for our needs (can't say for everyone of course):
On Sep 21, 2020, at 11:29 AM, roger peppe <rogp...@gmail.com> wrote:
--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/CAJhgacj9Lyo1hJd6s1cnnxvXpbdQ-RafZSpBD%2B-ABgTU81Ymnw%40mail.gmail.com.
You mention recursive generic functions. This can become quite pathological if we're not careful about the rules.For example, here's a short program that generates over 300k different generic functions: https://go2goplay.golang.org/p/GjBIOAYc_uu