Generics false dichotomy

[Ziad Hatahet]

Hi all,

I came across a set of recent slides about Go, given by Russ Cox. This one in particular stood out: http://talks.golang.org/2014/research.slide#24

I feel the options being presented are a sort of false dichotomy -- either (1) slow down the programmer, (2) slow down the compiler and bloat the binary, or (3) slow down the runtime.

There are many languages other than the ones presented that successfully employ generics. The D language authors claim that it compiles as fast -- or faster -- than Go. D is a very meta-programming heavy language. So clearly a solution is available; though with statements like the ones in the slide above, I keep getting the feeling other language implementations are being overlooked.

[Ian Lance Taylor]

You could be right. But without knowing the details of what the D
compiler is doing, it's impossible to tell. It's not sufficient to
point to some other language and say that it is possible to support
generics. We know that it is possible. If you want to argue about
approaches to generics, you need to describe an approach to generics.
It's especially good if you can base that approach on some other real
language. But it's not particularly helpful to cite a language
without describing the approach.

Ian

[Dave Cheney]

D, C#, Java, C++ may very well have implemented some for of templated or generic functions, but that does not change those three statements.

1. Is it easier or harder to write correct code in the languages above when they make heavy use of generic or templated functions and types ? 

2. If template processing or compiling of generic support were removed from those languages' compilers, would their compilation times be faster or slower ?

3. If (2) were done, are their various runtime support libraries smaller and/or faster, or slower and/or larger ?

Dave

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Jeremy Jackins]

False or not, that's a trichotomy.

[Daniel Fanjul]

Is this like the CAP theorem then, impossible to provide the three options simultaneously?

Which option(s) will be favoured in the design of generics for go, according to the goals?

On Thu, Feb 13, 2014 at 10:32 PM, Jeremy Jackins <jeremy...@gmail.com> wrote:

False or not, that's a trichotomy.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Daniel Fanjul Alcutén
Tools Engineer @Spotify AB

https://github.com/daniel-fanjul-alcuten

[Ken Allen]

You know I've heard Alexandrescu make that claim that D compiles faster than Go but that can't possibly be true in the general case because you can perform arbitrary computation at compile time. Compile-time D code is run in an interpreter IIRC so that part of it can't be all that fast anyway. It's a weird claim, I wonder if he was referring to something in particular or just knee-jerking (I heard him claim that in response to someone mentioning the go compiler speed video at one of his talks).

[Jesper Louis Andersen]

On Thu, Feb 13, 2014 at 11:45 PM, Daniel Fanjul <daniel.fan...@gmail.com> wrote:

Is this like the CAP theorem then, impossible to provide the three options simultaneously?

Which option(s) will be favoured in the design of generics for go, according to the goals?

Apart from the fact that CAP is a theorem and this is at best a conjecture. You need good formal definitions of all of the involved subjects (which is tremendously hard to pull off).

My hunch is that it is possible to get fast compilation of generics and produce efficient code in practice. But it will take some compiler complexity to pull it off. I am not sure I get why it has to be so efficient in execution though. In my book, the added abstraction benefit for the programmer outweighs most other things.

--
J.

[andrey mirtchovski]

> You know I've heard Alexandrescu make that claim that D compiles faster than
> Go but that can't possibly be true in the general case because you can
> perform arbitrary computation at compile time. Compile-time D code is run in
> an interpreter IIRC so that part of it can't be all that fast anyway. It's a
> weird claim, I wonder if he was referring to something in particular or just
> knee-jerking (I heard him claim that in response to someone mentioning the
> go compiler speed video at one of his talks).

http://www.digitalmars.com/d/archives/digitalmars/D/D_compilation_speed_vs._go_108831.html

[Benjamin Measures]

On Friday, 14 February 2014 17:02:15 UTC, andrey mirtchovski wrote:

http://www.digitalmars.com/d/archives/digitalmars/D/D_compilation_speed_vs._go_108831.html

Go was less than 6 months old (as an open source project) at that point. The discussed video was release-day, and even used make for build.

I think it's fair to say things in Go are very different now than when it was first released.

[andrey mirtchovski]

> I think it's fair to say things in Go are very different now than when it
> was first released.

I measured it. go build -a ./... inside src compiles roughly 340K
lines of code on my mac in 6.1 seconds, ~53K LOC/s. by Andrei's
counts, they were doing ~70K LOC/s

The D guys have thrown a lot of time behind making their compiler fast:

http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over-75/240158941

it's understandable if they want to make a few waves by thrashing Go.

[Benjamin Measures]

On Friday, 14 February 2014 21:31:58 UTC, andrey mirtchovski wrote:

go build -a ./... inside src compiles roughly 340K lines of code on my mac

How did you come up with that number?

Bringing it back on topic, even D has made its choice when it comes to the question, "Do you want slow programmers, slow compilers and bloated binaries, or slow execution?"

[andrey mirtchovski]

> How did you come up with that number?

i found all go files inside $GOROOT/src which did not have a different
operating system than the one I'm on as a target, and counted their
lines. if i exclude the tests from that count the number is close to
200k

[Benjamin Measures]

On Saturday, 15 February 2014 03:58:20 UTC, andrey mirtchovski wrote:

i found all go files inside $GOROOT/src which did not have a different
operating system than the one I'm on as a target

That's not all go build does. You should find out what it actually does (-n) before making up comparisons.

[andrey mirtchovski]

oh, that's right, sorry. i missed the part about the unicorns *rollseyes*

[minux]

it's easy to count total number of non-test Go source lines in the std library, just an exercise of go list -f:
$ go list -f $'{{range $x := .GoFiles}}{{$.Dir}}/{{$x}}\n{{end}}' std | xargs wc -l | grep total
  190780 total

i'm using tip.

[Rob Pike]

You almost never need xargs.

$ cat $(go list -f $'{{range $x :=
.GoFiles}}{{$.Dir}}/{{$x}}\n{{end}}' std) | wc -l
190782

-rob

[Benjamin Measures]

Doesn't that forget the c files compiled as part of pkg/runtime?

Further, whilst correlated, can you really measure compile kloc/s by measuring build time without taking into account what else the build tool might be doing?

[andrey mirtchovski]

> Further, whilst correlated, can you really measure compile kloc/s by
> measuring build time without taking into account what else the build tool
> might be doing?

that is the only comparison that has been made: old Go "make.bash" vs
whatever D uses. "build the standard library as it's usually done".
that comparison is fair vis-à-vis the claim Russ made in the video.
the go build that I posted was only to illustrate that things have not
changed many orders of magnitude since then. they might soon, but have
not yet.

as a community we shouldn't feel threatened, act defensive or question
assumptions as a knee-jerk reaction to someone calling us out on our
claims. D is a fine language, it may compile with speeds within the
same order of magnitude as 6g, it may be even faster. that's OK, I can
live with it. compilation speed isn't the only thing I'm here for.

[andrey mirtchovski]

full disclosure: when looking at "go build ./..." i opted to give Go
more than a fighting chance:

- _test.go files were counted as LOC
- CGO_ENABLED=0 was set (+2s otherwise)
- caches were about as warm as they can be

additionally, thrashing around in the directories looking for files to
compile (-n) takes .3s which I have not subtracted. the C code in
runtime took .024s. in the end, the go build is our measuring stick as
this is what everyone uses.

[minux]

right! thank you. xargs is redundant in this case.

i think the main purpose of xargs is to handle extremely long arguments. (I remembered that you critized modern unix for unable to handle arbitrarily long arguments. :))

[minux]

On Feb 15, 2014 12:48 AM, "Benjamin Measures" <saint....@gmail.com> wrote:
>
> On Saturday, 15 February 2014 05:16:13 UTC, minux wrote:
>>
>> On Feb 14, 2014 11:17 PM, "Benjamin Measures" <saint....@gmail.com> wrote:
>> > That's not all go build does. You should find out what it actually does (-n) before making up comparisons.
>> it's easy to count total number of non-test Go source lines in the std library, just an exercise of go list -f:
>> $ go list -f $'{{range $x := .GoFiles}}{{$.Dir}}/{{$x}}\n{{end}}' std | xargs wc -l | grep total
>>   190780 total
> Doesn't that forget the c files compiled as part of pkg/runtime?

we are talking about the speed of the Go compiler, not C compiler.

> Further, whilst correlated, can you really measure compile kloc/s by measuring build time without taking into account what else the build tool might be doing?

the problem is inherently subtle.

before Go 1.3, the compiler generates some kind of pseudo assembly instructions, which are not actually machine instructions, people might argue that it's not doing the full job of compiler as the code generation is not yet finished. Go 1.3 changes this aspect, so counting the time used by 6g makes sense.

how to only counting the time used by 6g is left as an exercise.

[Benjamin Measures]

On Saturday, 15 February 2014 07:11:59 UTC, minux wrote:

On Feb 15, 2014 12:48 AM, "Benjamin Measures" <saint....@gmail.com> wrote:
> Doesn't that forget the c files compiled as part of pkg/runtime?
we are talking about the speed of the Go compiler, not C compiler.

That's just the point. This sub-discussion began with

On Friday, 14 February 2014 21:31:58 UTC, andrey mirtchovski wrote:

I measured it. go build -a ./... inside src compiles roughly 340K 

lines of code on my mac in 6.1 seconds, ~53K LOC/s.

which ignores whatever else the build does, including c files.

[Benjamin Measures]

On Saturday, 15 February 2014 06:07:03 UTC, andrey mirtchovski wrote:

> Further, whilst correlated, can you really measure compile kloc/s by
> measuring build time without taking into account what else the build tool
> might be doing?

that is the only comparison that has been made: old Go "make.bash" vs
whatever D uses.

Except that it's not. Andrei wrote,

> The C code is not part of the measurement (and of the lines count) 

> because the purpose was to measure the speed of D compilation.

<http://www.digitalmars.com/d/archives/digitalmars/D/D_compilation_speed_vs._go_108831.html#N108850>

so there was clearly either a modified build, or measured a subset of the build.

"build the standard library as it's usually done".
that comparison is fair vis-à-vis the claim Russ made in the video.
the go build that I posted was only to illustrate that things have not
changed many orders of magnitude since then. they might soon, but have
not yet.

I would actually agree with you there and even suggest that the Go compiler's kloc/s is significantly less (in percentage terms) than the figure you came up with.

What I object to are "benchmarks" that are meaningless without parameters yet, as history proves, get quoted often enough and long enough until they become "truth". Andrei's figures are an example of this. I suspect dmd's compilation performance to be much less than his quoted figure (for example, were the unit tests [which are included in the d files] included in the kloc? What about comments? How many times is the compiler started up in the build?) but cannot reproduce as there are no parameters to back up his statement.

Without reproducable research they're just damned statistics.

as a community we shouldn't feel threatened, act defensive or question
assumptions as a knee-jerk reaction to someone calling us out on our
claims. D is a fine language, it may compile with speeds within the
same order of magnitude as 6g, it may be even faster. that's OK, I can
live with it. compilation speed isn't the only thing I'm here for.

To use a phase I first heard in this group, I think we're in violent agreement.

[jonathan....@gmail.com]

As someone who's done a bit of benchmarking, I feel compelled to point out that, questions of compilation speed aside, the Go compiler generally generates much better (faster) code than the DMD D compiler. The LDC and GDC D compilers may produce faster code than Go, but they use the LLVM and GCC as backends, which are of course less lightweight. 

An anecdote: I recently tried to compile a program that used a large static array (around 600mb). The Go compiler took around thirteen seconds and completed it, the DMD compiler ran for a while and then got killed by the OS.

[Michael Jones]

Since different languages represent more and less in a line of code, how is the metric meaningful? 

I wrote the fast string output routines for math/big; base 2 and 8 are faster in digits/sec than base 10, but they also need more digits to express the same number. Seems related to the KLOC/sec race. Better might be "compiling programs that do ${X/sec} "/per second, for X = sort 1M ints or invert 100x100 matrix, or ...

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[minux]

On Sat, Feb 15, 2014 at 9:41 AM, Michael Jones <m...@google.com> wrote:

Since different languages represent more and less in a line of code, how is the metric meaningful? 

I wrote the fast string output routines for math/big; base 2 and 8 are faster in digits/sec than base 10, but they also need more digits to express the same number. Seems related to the KLOC/sec race. Better might be "compiling programs that do ${X/sec} "/per second, for X = sort 1M ints or invert 100x100 matrix, or ...

perhaps a fairer benchmark metric is the combined time of compiler and executable runtime for

a particular problem.

[Jonathan Amsterdam]

Aren't we splitting hairs at this point? Whatever the exact relative speeds of dmd and 6g, it seems as if D doesn't pay too much of a compilation penalty for its generics, which is an existence proof that you can have generics and fast compilation.

Also, this is not a scale-independent problem. Meaning, say you had a compiler that runs at 1 MLOC/s. That means near-instant response for most compiles. If the speed halved because of generics, we'd be fine with that.

I personally think that with a proper persistent cache and "normal" programs (ones that did not exploit the Turing-completeness of the generics system), generics should add only a little time to an incremental compile.

[minux]

On Feb 15, 2014 8:51 PM, "Jonathan Amsterdam" <jbams...@gmail.com> wrote:
> Aren't we splitting hairs at this point? Whatever the exact relative speeds of dmd and 6g, it seems as if D doesn't pay too much of a compilation penalty for its generics, which is an existence proof that you can have generics and fast compilation.

the point is not that generics will necessarily slow down compilation. It's that you can't get all these:
1. fast compilation,
2. non-bloated binary,
3. efficient runtime
along with generics.

for example, we can just add generics as syntax sugar for a reflection-based solution, and that won't affect compilation speed much, but do you want that kind of generics?

[Aram Hăvărneanu]

On Sun, Feb 16, 2014 at 2:51 AM, Jonathan Amsterdam
<jbams...@gmail.com> wrote:
> D doesn't pay too much of a compilation penalty for its generics

D pays a huge penalty in compilation speed for generics. D generics
are turing complete, making compilation time potentially unbounded.
Dmd might build their standard library quickly, but this says nothing
about the fundamental issue.

Potentially unbounded compilation times are unacceptable for Go.

--
Aram Hăvărneanu

[jonathan....@gmail.com]

If anyone's interested, I just benchmarked an simple program implemented identically in D and Go (the only significant difference is the D one has to manually do the zero-initialisation at startup), involving array access and mutation. Dmd's version is v2.063, Go's is 1.2 linux/amd64. The running times of the resulting executables were almost identical (both about as fast as C for this simple task), but the Go version took around 0.33 seconds to compile and the D version took around 0.96 seconds. Note that this is a program that doesn't use generics, yet the Go compiler was still three times faster.

[jonathan....@gmail.com]

Oh, and if anybody wants to test it themselves, the D program is compiled with dmd D.d -O -release -inline.

[gordon...@gmail.com]

On Sunday, February 16, 2014 11:03:38 AM UTC+1, Aram Hăvărneanu wrote:

Potentially unbounded compilation times are unacceptable for Go.

Potentially unbounded run times are also unacceptable for Go.  So, Go shouldn't be Turing complete.

Not true, of course.  The potential is desired, even necessary.  What's undesired are actual unbounded run times (ignoring, of course, programs that are meant to run forever).

The same should hold true for compilation times.  The interesting questions regarding a Go compiler with generics, then, are:

 - What is the risk and cost of actual unbounded compilation time?  Are we willing to accept it?

 - What is the increase in compilation time for normal programs?

[Jan Mercl]

On Sun, Feb 16, 2014 at 12:36 PM, <gordon...@gmail.com> wrote:
> The same should hold true for compilation times. The interesting questions
> regarding a Go compiler with generics, then, are:
> - What is the risk and cost of actual unbounded compilation time? Are we
> willing to accept it?
> - What is the increase in compilation time for normal programs?

The history of C++ repeats from this point.

-j

[jonathan....@gmail.com]

I think it's worth bearing in mind that Go was created partially as a response to long C++ compile times at Google, so the designers aren't just interested in minimising compile times for 'normal' programs, they're interested in minimising compile times for really large programs.

[Gordon Klaus]

Good point.  "Normal" can mean very different things to different people.

What I meant by "normal" was programs that don't use generics recursively in such a way that could lead to unbounded compilation times.  I guess this corresponds to most people's conception of normal generics usage.

And I suppose that the penalty (in greater compilation time, run time, binary size) for such programs would be similar regardless of whether they are small or really large.

[Jonathan Barnard]

Maybe it's necessary to be more specific in what's meant by 'generics'. Generics need not imply any Turing-complete metaprogramming capability; Java for instance has generics, but lacks any capacity for compile-time metaprogramming.

[Russel Winder]

This entire thread is wrong-headed, and has the potential for putting
the Go community in a bad light. It smacks of the "my religion is better
than your religion and so anyone who disagrees with me is wrong and must
be eliminated, oh and by the way I am feeling a bit unsure of my
religion please reassure me" style of debate. There is no need for this
tribalism. I use both D and Go and love and hate both at various times,
but I have no need to feel insecure about my use of either language.
Good critiques are very valuable, but they need to be evidence based and
not emotionally based. Let's all just get more constructive.
--
Russel.
=============================================================================
Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel...@ekiga.net
41 Buckmaster Road m: +44 7770 465 077 xmpp: rus...@winder.org.uk
London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder

[Kevin Gillette]

On Sunday, February 16, 2014 4:36:05 AM UTC-7, gordon...@gmail.com wrote:

On Sunday, February 16, 2014 11:03:38 AM UTC+1, Aram Hăvărneanu wrote:

Potentially unbounded compilation times are unacceptable for Go.

Potentially unbounded run times are also unacceptable for Go.  So, Go shouldn't be Turing complete.

Not true, of course.  The potential is desired, even necessary.  What's undesired are actual unbounded run times (ignoring, of course, programs that are meant to run forever).

The same should hold true for compilation times.

[citation needed]

See <http://stackoverflow.com/a/189444> for an example of what C++ can push into the compilation phase. Of course, that's likely an extremely inefficient way to make a factorial calculation, even though it's a no-op at runtime. I seriously doubt that kind of meta-programming would have any place in Go, as would many of the things you can do with templates in C++; C++ templates aren't generics, they're a superset of the kind generics we may want for Go. Because of this, the same quirks and characteristics that apply to C++'s take on generics do not need to apply in whole to an approach used for Go. It may well be an untenable assumption that non-type-erasure generics must be compile-time turing complete.

[Gordon Klaus]

I see now that my last sentence was misleading (sorry for the bad writing!).  I only meant it to refer to the previous sentence about the undesirability of actually unbounded times, not also to the one before about the desired potential for unboundedness.

The point I was trying to make was only that the potential for unbounded compilation times is not reason enough on its own to dismiss Turing-complete generics.  However, I agree that there may well be other reasons to not have them in Go, such as their simply not being especially useful in day-to-day programming; but I don't have enough experience with meta-programming to make such a judgment.

[paulo....@gmail.com]

Anyone that used languages with module support in the early 80's has experienced fast compilation times.

Let's not forget Ada, Eiffel, Modula-3 and many other languages that enjoy generics, modules and have/had fast compilers available, even
if they are not well known to most blue collar developers.

[Benjamin Measures]

On Sunday, 16 February 2014 21:25:40 UTC, paulo....@gmail.com wrote:

Anyone that used languages with module support in the early 80's has experienced fast compilation times.

They also experienced working in 64KB RAM, which was a limit on the complexity of software.

Let's not forget Ada, Eiffel, Modula-3 and many other languages that enjoy generics, modules and have/had fast compilers available, even
if they are not well known to most blue collar developers.

Let's not forget that Eiffel only had formal generic parameters until 4.3, when it gained formal generic types. These, btw, look a lot like interface types.

Which brings us to the Go sort example of generics: func Sort(data Interface) takes a parameter of interface type with particular method set. The penalty for this sort of generics (no pun intended) is in the method tables which are computed at runtime (rather than statically, at compile time).

[jonathan....@gmail.com]

How about this: do people want generics, or no-cost generics? I don't imagine it'd be too difficult to just give Go 2.0 syntactic sugar for the reflection-based generic programming that is currently possible. Sure it'd be slower than C++ style generics, but it wouldn't be any slower than the current style of generics (as it'd be identical, just with syntactic sugar). That would stop all the 'Go doesn't have generics' complaints, and if people complained about the speed it'd be a simple matter of pointing out that even reflection-based generics in Go are still faster than Python, Ruby and Scheme's generics (and maybe faster than C# Mono's and naive Haskell's) since the language as a whole is faster.

[and...@erdani.com]

On Thursday, February 13, 2014 12:19:17 PM UTC-8, Ziad Hatahet wrote:

Hi all,

I came across a set of recent slides about Go, given by Russ Cox. This one in particular stood out: http://talks.golang.org/2014/research.slide#24

I feel the options being presented are a sort of false dichotomy -- either (1) slow down the programmer, (2) slow down the compiler and bloat the binary, or (3) slow down the runtime.

There are many languages other than the ones presented that successfully employ generics. The D language authors claim that it compiles as fast -- or faster -- than Go. D is a very meta-programming heavy language. So clearly a solution is available; though with statements like the ones in the slide above, I keep getting the feeling other language implementations are being overlooked.

Thanks to Russel Winder who brought this interesting thread to my attention.

Please allow me to bring my own perspective to this. But first, regarding the measurements I've done: I always do my best to be able to stand behind my statements, and this is no exception. The speed measurements I made back in the day gave a fair shake to both compilers, to the best of my understanding and within the time box I allocated for the experiment. Moreover I stated my assumptions best I could (e.g. comments were not eliminated etc). The attempt was to make a fair albeit non-rigorous comparison of build times. I should note that a 80-line program written in both Go and D (which was presented in this thread) would essentially measure the speed of linking and as such would be not indicative of compilation speed.

I think, as has been noted, that for many people the notion of slow builds for compiled code comes from using C and C++'s modularity mechanisms, which are poor. Since C++ is so widespread for large programs where efficiency is a main concern, and since few other compiled languages have a comparable market shared, the prejudice that producing efficient code takes long times has been born. Both Go and D do a good job, in my opinion, at dispelling that.

On to generics. Do they make builds slower? The answer is, as many times is the case, "it depends".

To start with, there are trivial cases in which loops and compile-time recursion are used to slow down any compilation of a D program arbitrarily. But these are not really comparable because they do things that can't be achieved in Go proper.

On to the interesting cases - consider an important non-trivial algorithm such as edit (Levenshtein) distance, partition, kth largest element, or set intersection. For the D community it's a big deal that these algorithms are implemented "Once and Only Once", e.g. there is one implementation of edit distance that supports ASCII, UTF8, UTF16, UTF32 (all UTFs with or without those compound characters), genome sequences, and a even encodings that haven't even been invented yet - all with specialized implementations running at full speed leaving no
"room" below them that motivates a hand-written implementation for native speed.

This is a big deal for D. We consider it an important way to look at software; for my money it's quite the primary reason that I can't wait for the sun to go up every morning so I can work on it some more. At the same time, I completely understand how some people would go "meh" about that and would have a dim view on D and on the stuff I like to work on. And that's entirely fine. I myself have a dim view of languages that provide poor solutions to some problem, whilst permanently attempting to understand just how subjective I am.

Since that's a big deal to us, we don't consider it a may-or-may-not option, so we need to make it work. The way we make it work is by taking a generic edit distance function that only makes minimal commitments to its input - in fact so minimal, it can't be compiled into machine code. So the front-end parses the code and stores it in memory in a lightly structured format.

If the function is never used, there is a sunk cost: the generic function has been parsed already, and due to the white-box nature of D generics, it must be parsed whether or not it's used. So Go "wins". I should add that the sheer cost of just parsing is small albeit often measurable.

If the function is instantiated exactly once (e.g. for UTF8), the D compiler will pass that particular instantiation through all stages of compilation. Historically the D compiler did so more times than necessary, but recent changes greatly improve on that (without as of yet achieving zero redundant work). A design that eliminates unnecessary compilations is a challenge for any generics-laden system, but not a very difficult one.

If the function is instantiated several times for distinct types, a language without generics needs to opt for uniform representation of data and higher order functions (interfaces and pointers to functions). Inlining post that stage is, to my understanding, a challenge to non-generic language designs. The D compiler will generate separate native functions for each data representation, and as such will generate larger code overall, but faster code for each specialization. It is my perception that adoption of generic designs in C++ (both standard library and idioms commonly accepted as "modern" in user code) at the expense of traditional interface/indirection designs provides powerful evidence that such a tradeoff is worth making at least some of the time.

To achieve native speed for a generic algorithm, Go would need to opt for an interface/indirection based design and/or several specialized implementations. In the first case, compilation stays fast but siphons runtime speed away. In the second case, compilation is as fast as generics but it siphons away developer time spent on duplicated code.

It is entirely understandable if D's tenets are of no import to Go's ethos, and that's an important thing to keep in mind. I hope the above brings more nuance to blanket statements such as "generics would make compilation faster/slower".


Andrei 

[Kevin Gillette]

On Sunday, February 16, 2014 8:18:34 PM UTC-7, jonathan....@gmail.com wrote:

How about this: do people want generics, or no-cost generics? I don't imagine it'd be too difficult to just give Go 2.0 syntactic sugar for the reflection-based generic programming that is currently possible.

The reason people [should] want generics in Go is because it provides compiler-verifiable safety to type-agnostic algorithms; Java-style type erasure provides that. The reason that Go doesn't already have Java-style generics is because they're slow and memory inefficient, and the Java approach is even strictly better than what you're describing (which is merely syntactic sugar -- no stated implications in regards to safety).

That would stop all the 'Go doesn't have generics' complaints, and if people complained about the speed it'd be a simple matter of pointing out that even reflection-based generics in Go are still faster than Python, Ruby and Scheme's generics (and maybe faster than C# Mono's and naive Haskell's) since the language as a whole is faster.

From the testing I did about a year ago, heavy reflection-based generic algorithms in Go are much slower than equivalents in Python. Further, languages themselves aren't slow or fast -- their implementations are.

[jonathan....@gmail.com]

On Monday, 17 February 2014 20:48:53 UTC+11, Kevin Gillette wrote:

The reason people [should] want generics in Go is because it provides compiler-verifiable safety to type-agnostic algorithms; Java-style type erasure provides that. The reason that Go doesn't already have Java-style generics is because they're slow and memory inefficient, and the Java approach is even strictly better than what you're describing (which is merely syntactic sugar -- no stated implications in regards to safety).

I read a blog from one of the C# developers, although I can't find the address now, where he described C#'s style of reified generics as slower and more bloated than Java's. Ocaml, which is quite fast, also uses type erasure. Even Haskell does. So if you consider type erasure slow and memory inefficient, what's the alternative?

.From the testing I did about a year ago, heavy reflection-based generic algorithms in Go are much slower than equivalents in Python. Further, languages themselves aren't slow or fast -- their implementations are.

Wow, I didn't realise they were this slow. Like many Go programmers I haven't found much need for generics that couldn't be fulfilled by text/template. I just assumed they wouldn't be too slow as casting to and from void* in C isn't too slow (still slower than C++ templates, but faster than Python).

[Benjamin Measures]

On Monday, 17 February 2014 03:18:34 UTC, jonathan....@gmail.com wrote:

How about this: do people want generics, or no-cost generics?

No-cost generics don't exist[*]. Going back to the original question, "Do you want slow programmers, slow compilers and bloated binaries, or slow execution?"

[*] That is, unless you're already paying the price. Java gets it "for free" because "Java boxes everything implicitly" anyways.

I don't imagine it'd be too difficult to just give Go 2.0 syntactic sugar for the reflection-based generic programming that is currently possible.

The sort package is "generic" but doesn't use reflection. What "syntactic sugar" do you suggest to make this package better?

[jonathan....@gmail.com]

I don't have any problem with the sort package, actually, rather I meant syntactic sugar for when people want to make their own generic functions. For instance, so that someone can write:

func addThree(a, b, c Box) Box{
    return a + b + c
}

And you could call that as addThree(1, 2, 3) or addThree("I ", "eat ", "bread.") and at runtime it'd box the values you put in, then typecheck a. b and c to see if they were types that could be added to eachother, and if so then add them together and return the result, also boxed. Essentially it'd do the same as (define (add a b c) (+ a b c)) in Scheme.

[John Souvestre]

> Going back to the original question, "Do you want slow programmers, slow compilers and bloated binaries, or slow execution?"

 

Just my personal feeling:  If the percent change in each of the four options is the same (it really isn’t, is it?), then my first choice would be bloated binary.  I don’t much care if a 3M binary becomes 6M, for example.

 

My second choice would be slower compiles.  If I can save half the programmer time at the cost of doubling the compile time, then my development cycle would be much faster.

 

The last thing I would want is slow programmers, so unless I was up against the wall I’d sacrifice execution time next.

 

John

    John Souvestre - New Orleans LA

--

[John Souvestre]

> Going back to the original question, "Do you want slow programmers, slow compilers and bloated binaries, or slow execution?"

 

Follow-up question:  If Go were to have Generics, would the above four ailments exist in all Go programs, or just those which chose to use Generics?

 

John

    John Souvestre - New Orleans LA

 

[Benjamin Measures]

On Monday, 17 February 2014 10:57:40 UTC, johns wrote:

> Going back to the original question, "Do you want slow programmers, slow compilers and bloated binaries, or slow execution?"

Just my personal feeling:  If the percent change in each of the four options is the same (it really isn’t, is it?), then my first choice would be bloated binary.  I don’t much care if a 3M binary becomes 6M, for example.

My second choice would be slower compiles.

It's a question of three OR options:

Do you want:

a. slow programmers;

b. slow compilers and bloated binaries; or

c. slow execution?

You've chosen b: C++ templates.

[Alex Skinner]

Why runtime checks? Seems to me it would be faster and much safer for the compiler to implicitly detect types and error check at compile time. That way, in your example, if I tried to add say, structs, it would fail to compile rather than panic at runtime. It should also be faster at runtime on account of no reflection. I'm not really a huge proponent of generics, nor really well versed in design, so am ready to be educated on why this is a bad idea...

[jonathan....@gmail.com]

>Follow-up question:  If Go were to have Generics, would the above four ailments exist in all Go programs, or just those which chose to use >Generics?

Generics that bloated code wouldn't affect programs that didn't use generics. If the standard library used generics, however, then it'd be hard to avoid the bloat (see: the C++ STL, or Boost). Same for slow compiles. A generics implementation that reduced speed wouldn't affect programs that didn't use it... unless the stdlib or whatever other libraries you needed used it. Finally, a generics implementation that decreased programmer speed (like the current one) doesn't affect anybody who doesn't need to write generic code.

Note that bloated executable is connected to reduced executable speed, due to cache issues.

[jonathan....@gmail.com]

On Monday, 17 February 2014 22:08:46 UTC+11, Alex Skinner wrote:

Why runtime checks?  Seems to me it would be faster and much safer for the compiler to implicitly detect types and error check at compile time. That way, in your example, if I tried to add say, structs, it would fail to compile rather than panic at runtime.  It should also be faster at runtime on account of no reflection.  I'm not really a huge proponent of generics, nor really well versed in design, so am ready to be educated on why this is a bad idea...

It's not a bad idea, it's what most statically compiled languages with generics do. It just makes compilation slower, due to the compiler having to do extra work, and can make the code bloated; if a generic function is called with three different types of arguments at different parts of the program, it has to generate three versions of that function. Runtime checks are a compromise that wouldn't affect compile times but would make generic functions much slower.

[oju...@gmail.com]

I don't know if "easy of implementation" is an official requirement for Go, but that is very important in the long run. If the final choice is that Go isn't going to support templates just to keep compilers simple and easy to implement, I have no problem with that.

[jonathan....@gmail.com]

On Monday, 17 February 2014 22:41:51 UTC+11, oju...@gmail.com wrote:

I don't know if "easy of implementation" is an official requirement for Go, but that is very important in the long run. If the final choice is that Go isn't going to support templates just to keep compilers simple and easy to implement, I have no problem with that.

Go already supports templates: text/template. Any compiler would have to implement this, as it's part of the standard library. It's already possible to make simple generic functions with that library, so it wouldn't be hard for the compiler to use it to do so. Most people who want generics want more complicated, typesafe generics however, which are not so easy to implement. Nevertheless, if a simple generics solution was chosen then it wouldn't have a significant negative effect on ease of implementation.

The generics in C11 are an example of something relatively simple. From the Wikipedia article:

The following macro cbrt(x) translates to cbrtl(x), cbrt(x) or cbrtf(x) depending on the type of x:

#define cbrt(X) _Generic((X), long double: cbrtl, \
                              default: cbrt, \
                              float: cbrtf)(X)

[oju...@gmail.com]

Uh, pardon my C++ jargon. By "templates" I mean what you call "typesafe generics".

[Robert Johnstone]

That is not strictly true.  The compiler (or linker) can detect functions whose implementations are binary equivalent, and merge them.  This can be quite effective for systems that use type erasure to implement generics.  You maintain type safety, and eliminate some casts, but if you have functions with specialization, then obviously they won't be equivalent, but in that case multiple copies would be the desired result.

[Jonathan Amsterdam]

Here are some observations to counter the FUD of the "which slowness do you want?" trichotomy and the Godwinesque comparisons to C++ templates. Some have been mentioned before.

A generics system doesn't have to be Turing-complete.

There is a spectrum of implementations between generating a single, slow version of the code (erasure) and generating code for each and every instantiation. Go in particular lends itself to some obvious optimizations, because all types of the same size are equivalent with respect to initialization and copying. Thus a generic type that only initializes and copies its arguments, like a container, would only need to be instantiated once per size of argument type. Since most Go programs use pointers to large structs rather than the structs directly, in practice this would likely result in just a handful of instantiations: 1, 2, 4, 8, and 16 bytes, plus a few more for structs used by value. (Yes, with two generic arguments the number is squared, and with three, cubed; but those cases get increasingly rare as you increase the number of generic arguments.)

The programmer has some control over the tradeoff between amount of instantiation and run-time performance. You can write Tree[int], Tree[bool] and Tree[string] in your program, or you can write Tree[interface{}] three times. You have that same option today in Go, except that you have to copy code to get the former, so most people just use interface{}. Thus the language is pushing you to choose slow programs over slow compiles.

Most compilations are incremental.

Compilation is not scale-independent: you don't care if your compiler runs in the blink of an eye, or in two blinks. Similarly for binary size.

Compilation is easily parallelizable. It's linking that's the real bottleneck. A generic implementation does not necessarily have to slow down the linker. We don't really know either way because nobody really talks about this (except Russ, who points out that the C++ linker must spend time removing duplicates -- but that can be avoided with a persistent cache of instantiations). And could linking be parallelized?

[lmumar]

How I wish we can do something like this:

import "fmt"

type T generic

func max(a, b T) T {

  if a > b {

    return a

  } else {

    return b

  }

}

func main(){

  mi := max(10, 20)     `where:"T(int)"`

  mf := max(20.5, 30.5) `where:"T(float)"`

  fmt.Println(mi, mf)

}

oh well, got to keep dreaming..

[Andy Balholm]

The sort package provides an interesting example of how to implement generic algorithms using interfaces. But the performance doesn't match that of C++'s "slow compiler, bloated binaries" approach.

However, there is no reason that the compiler couldn't be enhanced in such a way that it would produce specialized versions of sort.Sort (or any similar function) that would be called when its parameter type is statically known at compile time. In these, the sort.Interface methods could be inlined, and they would be as fast as if they were written for sorting that specific type.

I think StrongTalk did a lot of this kind of thing, in order to get good performance out of an extremely dynamic language.

The main difficulty is, How should the compiler decide when to specialize functions for different interfaces and when not to? If it does it whenever there is any call of the function with a statically-known concrete type, we're definitely going down the "slow compiler, bloated binaries" road. If it makes some assessment of whether the performance would be worth it, there is the potential for unpredictable performance changes. Maybe there should be some way to mark the functions that should be specialized. 

[Benjamin Measures]

On Monday, 17 February 2014 10:55:19 UTC, jonathan....@gmail.com wrote:

On Monday, 17 February 2014 21:26:04 UTC+11, Benjamin Measures wrote:

The sort package is "generic" but doesn't use reflection. What "syntactic sugar" do you suggest to make this package better?

I don't have any problem with the sort package, actually, rather I meant syntactic sugar for when people want to make their own generic functions. For instance, so that someone can write:

func addThree(a, b, c Box) Box{
    return a + b + c
}

That'd require operator overloading, which in all probability isn't going to happen.

That aside, the following is perfectly doable as it is:

func addThree(a, b, c Adder) Adder {

return a.Add(b).Add(c)

}

http://play.golang.org/p/394xkY3J_W

No sugar required (unless what you really want is operator overloading).

[Benjamin Measures]

On Monday, 17 February 2014 15:37:23 UTC, lmumar wrote:

func max(a, b T) T {

  if a > b {

    return a

  } else {

    return b

  }

}

Before you carry on thinking Go needs generic types for this sort of thing, have you seen how the sort package does this?

[oju...@gmail.com]

So, maybe Robert Griesemer has a well formed opinion on the issue, because he is know as a co-creator of both Go and Strongtalk. See:

http://strongtalk.org/history.html

"Robert Griesemer wrote the interpreter, the interpreter generator, most of the compiler, and other VM stuff."

http://talks.golang.org/2009/go_talk-20091030.pdf

"Robert Griesemer, Ken Thompson, and Rob Pike started the project in late 2007."

[atila...@gmail.com]

Go's sort package is actually a shining example of why generics are desireable. It's interesting to read about "code bloat" for generics when the alternative is to implement everything over and over again by hand.

On the original issue of it being basically impossible to have generics and fast compilation, someone else said it better already on this thread: D compiles fast enough for this to be a moot point. When you get to 2 orders of magnitude faster than C++, it doesn't really matter anymore. For incremental builds, the bottleneck will be the linker anyway.

D compiles fast enough, comparable to Go. So, fast enough to not really matter. If you don't like generics and like writing Go, by all means write great code in your favourite language. That doesn't mean that fast compilation can only be achieved by not implementing generics/templates/compile-time evaluation. Or that Go should get generics. But the OP is right, it's a false trichotomy.

[Dan Kortschak]

On Mon, 2014-02-17 at 13:41 -0800, atila...@gmail.com wrote:
> Go's sort package is actually a shining example of why generics are
> desireable. It's interesting to read about "code bloat" for generics
> when the alternative is to implement everything over and over again by
> hand.

What? 3 lines? One of which is a minimum for having a generalisable
sort.

If we put that into the context of qsort, you need to provide num (Len()
int in Go idiom), size (Swap(int, int) in Go idiom) and compar
(Less(int, int) bool in Go idiom).

[paulo....@gmail.com]

It starts with three lines and ends up with everyone building their own workaround for not
having support for generics in the language.

I saw this before, it was part of Borland C++ for MS-DOS when templates started to be discussed at ISO
and built of pre-processor magic.

[jonathan....@gmail.com]

On Monday, 17 February 2014 23:37:23 UTC+8, lmumar wrote:

How I wish we can do something like this:

import "fmt"

type T generic

func max(a, b T) T {

  if a > b {

    return a

  } else {

    return b

  }

}

func main(){

  mi := max(10, 20)     `where:"T(int)"`

  mf := max(20.5, 30.5) `where:"T(float)"`

  fmt.Println(mi, mf)

}

It's not hard to roll your own if you need it. I just wrote this simple implementation, for instance; didn't take long, and only 115 lines of code. It's probably buggy, it's not robust, and it can't handle malformed syntax or do error checking, but it shows it's not hard to get started. Run it as "go++ -i=myGenericGoFile.go", and it will compile to the executable "myGenericGoFile++". The example you described would be written as:

package main

import "fmt"

func max<T>(a, b ~T) ~T {

  if a > b {
    return a
  } else {
    return b
  }
}

func main(){

  mi := max<int>(10, 20)
  mf := max<float32>(20.5, 30.5)
  fmt.Println(mi, mf)
}

It also supports multiple parameters (for instance, func MyFunc<A, B>() ). There are no doubt community packages out there for doing this that are far better developed, so if you find yourself missing generics then why not use one of them?

[Benjamin Measures]

On Monday, 17 February 2014 21:41:31 UTC, atila...@gmail.com wrote:

On the original issue of it being basically impossible to have generics and fast compilation

Nobody has said that, nor is it an/the original issue.

D compiles fast enough forhttp://d.puremagic.com/issues/show_bug.cgi?id=10693 this to be a moot point.

Some algorithms seem "fast enough", until you discover they're exponential time. If you can bubble sort 10k elements in a blink of an eye, what can possibly go wrong?

Likewise, with templates: http://d.puremagic.com/issues/show_bug.cgi?id=10693

[Benjamin Measures]

On Tuesday, 18 February 2014 00:29:28 UTC, Benjamin Measures wrote:

On Monday, 17 February 2014 21:41:31 UTC, atila...@gmail.com wrote:

D compiles fast enough forhttp://d.puremagic.com/issues/show_bug.cgi?id=10693 this to be a moot point.

Sorry for the finger slip. The quote should of course be:

On Monday, 17 February 2014 21:41:31 UTC, atila...@gmail.com wrote:

D compiles fast enough for this to be a moot point.

[jonathan....@gmail.com]

I'd just like to draw attention to this thoughtful post earlier in the thread by Andrei Alexandrescu, one of the lead designers of D. I suspect it may have been missed by many due to taking a long time to appear due to awaiting moderation.

[Dan Kortschak]

On Mon, 2014-02-17 at 15:28 -0800, paulo....@gmail.com wrote:
> It starts with three lines and ends up with everyone building their
> own workaround for not having support for generics in the language.

That may be the case generally, but it is a long bow to draw for sorting
which was what I was commenting on.

[Sean Talts]

+1; it's very interesting to hear from people who have been there before and Andrei's post is thorough and well thought out.

[atila...@gmail.com]

+1

[Henrik Johansson]

It is very funny actually with a thread that discusses a false dichotomy with a false dichotomy as a premise.

None of the creators of Go either overlooks the value of generics nor that an implementation one day may exist.

The original statements about generics as I interpret them is just that there are these potential trade offs and until we find a good compromise we will not add it.

Compilation speed is a factor but not the one and only factor.

I have now written a decent amount of Go, not nearly as much as many here but still not insignificant and I can say that there are very few times I have really missed generics.

It is not a statement of causality for sure but at least some indication that it may be less important than you might think. At least in everyday coding. I remember thinking along the lines of "no generics... not gonna fly" but I was wrong and that makes me value generics differently. Not more, not less only differently. If I was spending my time writing libraries I might feel differently.

End tiny rant.

/ Henrik

[akaariai]

On Monday, February 17, 2014 8:01:57 AM UTC+2, Andrei Alexandrescu wrote:

To achieve native speed for a generic algorithm, Go would need to opt for an interface/indirection based design and/or several specialized implementations. In the first case, compilation stays fast but siphons runtime speed away. In the second case, compilation is as fast as generics but it siphons away developer time spent on duplicated code.

Wouldn't it be possible to offer a "specialize me" option for generic types and methods? The system would be using interface based implementation except if asked to specialize. Executable bloat would be minimal, yet there would be no developer time spent on duplicated code. The coder just needs to declare which specializations are needed. If the profiler could tell time spent in generic methods for each different type, it would be easy to spot when you might need a specialized version.

The system would be something like:

type HeapItem generic Comparable
// Comparable is an interface implementing LessThan and Equal. HeapItem must implement it.
 
type Heap<HeapItem> interface {
    Insert(*HeapItem)
    RemoveMin() *HeapItem
}
// Compiler offers type safety for above methods.

type SlowHeap<HeapItem> struct {
    items []*HeapItem
}

func (*heap SlowHeap) Insert(item *HeapItem) {
    // Just append to the items
}

func (*heap SlowHeap) RemoveMin() *HeapItem {
    // Find & remove minimum item using LessThan and Equal methods of Comparable.
    // Internally everything uses plain HeapItem interaces
}

// Initialize a heap for MyType
myheap := SlowHeap<MyType>{}

// I want as fast as possible heap for MyOtherType
type MyOtherTypeHeap<MyOtherType> specializes SlowHeap<MyOtherType>
// MyOtherTypeHeap is specialized for MyOtherType - Interface overhead is gone, calls
// are inlined where possible.
myfasterheap = MyOtherTypeHeap{} // No need for type arguments due to type declaration above

// Wihtout the specializes keyword this just declares a new type, so that the
// generics type declaration is DRY
type MyOtherTypeHeap<MyOtherType> SlowHeap<MyOtherType>

It seems this does offer fast generics when they are really needed, yet binaries aren't bloated just by using generics.

I am sure something like this has been considered previously. So I guess the question is: why something like the above isn't good enough?

 - Anssi

[Oliver Plohmann]

Am Dienstag, 18. Februar 2014 10:20:59 UTC+1 schrieb akaariai:

On Monday, February 17, 2014 8:01:57 AM UTC+2, Andrei Alexandrescu wrote:

To achieve native speed for a generic algorithm, Go would need to opt for an interface/indirection based design and/or several specialized implementations. In the first case, compilation stays fast but siphons runtime speed away. In the second case, compilation is as fast as generics but it siphons away developer time spent on duplicated code.

Wouldn't it be possible to offer a "specialize me" option for generic types and methods? The system would be using interface based implementation except if asked to specialize. Executable bloat would be minimal, yet there would be no developer time spent on duplicated code. The coder just needs to declare which specializations are needed. If the profiler could tell time spent in generic methods for each different type, it would be easy to spot when you might need a specialized version.

The system would be something like:

type HeapItem generic Comparable

I believe something like that could be accomplished by adding a new feature for this to something like Gen.

[bugpowder]

Yes. With extra work for the programmer. 

[bugpowder]

On Tuesday, February 18, 2014 4:56:39 PM UTC+8, Henrik Johansson wrote:

None of the creators of Go either overlooks the value of generics nor that an implementation one day may exist.

How do you know this?

 

The original statements about generics as I interpret them is just that there are these potential trade offs and until we find a good compromise we will not add it.

So who's actively looking for that good compromise?

And are the tradefoffs real and absolutely necessary? We just know for sure that some people -- including Go core team-- think yes, and other people --including designers of other languages like Andrei-- think it's an invalid trichotomy.

[Henrik Johansson]

They have stated repeatedly on and off this list that they (to a varying degree i am sure) don't dismiss generics but want to find a good solution that fits the spirit of the language. That last was my ad-lib but probably not far from the truth.

Who is actively researching generics for Go? I have no idea, surely there someone?

[Benjamin Measures]

What, like this?

func max(a, b T) T {

  if a.GreaterThan(b) {

[Benjamin Measures]

On Wednesday, 19 February 2014 12:26:52 UTC, bugpowder wrote:

On Tuesday, February 18, 2014 4:56:39 PM UTC+8, Henrik Johansson wrote:

None of the creators of Go either overlooks the value of generics nor that an implementation one day may exist.

How do you know this?

The Go FAQ <http://golang.org/doc/faq#generics>, "Generics may well be added at some point."

The original statements about generics as I interpret them is just that there are these potential trade offs and until we find a good compromise we will not add it.

So who's actively looking for that good compromise?

Every man and his dog. Some with more or less compromise.

And are the tradefoffs real and absolutely necessary? We just know for sure that some people -- including Go core team-- think yes, and other people --including designers of other languages like Andrei-- think it's an invalid trichotomy.

Citations, please.

[Jérôme Champion]

For Go 1, I think it should be possible to find/decide on an idiomatic way to annotate package that can be specialized in an non-intrusive* way.

Then, let the community experiment with different programs to generate specialized package and if a good solution is found, it could even be incorporated in the go tools.

*in the comment section, or with tags or any other solution that keep the package compilable.

[Robert Johnstone]

Part of the problem is that the community does not yet have a clear idea of what is desired.  I see a lot of confusion over what exactly generics in Go would cover.  For example, do we treat package essentially like hygienic macros that can be compiled with specialized types?  Or, do we want to allow packages to contain types or functions that can be specialized?  Until there is a consensus on the granularity of the templates, it will be hard standardize how the packages should be annotated.

[snac...@google.com]

What i'd like to hear regarding this trichotomy is how exactly option 1 works. That is, what does the programmer do that the compiler can't? How does manually rewriting a container for every type you need it to contain create a binary less bloated than having the compiler do the same thing?

I imagine there is a reason, and understanding it is going to be key to thinking about a good compromise.

[Jonathan Amsterdam]

You don't manually rewrite a container for every type you need. Instead, you just write one version of the code that uses interface{}. Maybe after profiling you add one more, for type byte perhaps, because you have a lot of those and you notice space is a problem. And then you're done. The final program is just as big as it needs to be, and you can discover that size with wc. 

[Robert Johnstone]

This is an example of the confusion I referred to earlier.  Some proposals would use type erasure, which provides type safe containers without bloat (there is only one implementation).  Some proposals are based on packages that provide a default implementation with interfaces, but can also be specialized at import (which provides similar size profile to your suggestion, but without needing to copy any code).

[snac...@google.com]

Ah. So it's really a tetrachotomy (?) where, in the absence of a generics system, you can either make programmers copy/paste, or let them (essentially) cast void pointers. I thought the latter was implicitly off the table, and I'm much relieved to see that it's actually the former possibility that we're not considering.