Min and Max

4776 views
Skip to first unread message

Peter Froehlich

unread,
Apr 3, 2010, 5:06:46 PM4/3/10
to golang-nuts
Hi all,

This may not bother people very much, but I just noticed that there's
no package that exports Min and Max functions. Instead there are
several implementations in various places in the library, all private:

src/pkg/compress/flate/util.go:21
src/pkg/rand/rand_test.go:25
src/pkg/strconv/ftoa.go:403
src/pkg/testing/benchmark.go:81

If someone can suggest a good package to put them in, I'd be happy to
refactor. Oh, just noticed: The math package already has Fmin and Fmax
for float64. Add a few more versions there maybe?

Cheers,
Peter
--
Peter H. Froehlich <http://www.cs.jhu.edu/~phf/>
Senior Lecturer | Director, Johns Hopkins Gaming Lab

peterGo

unread,
Apr 3, 2010, 9:25:14 PM4/3/10
to golang-nuts
Peter,

There are a lot of possible variations: min and max, each of the
number types e.g. int32, int, int64, float32, etc., and different
parameter lists. For example,

// Minimum of a pair of int arguments
func MinInt(v1, v2 int) int {
if v1 <= v2 {
return v1
}
return v2
}

// Minimum of a slice of int arguments
func MinIntS(v []int) (m int) {
if len(v) > 0 {
m = v[0]
}
for i := 1; i < len(v); i++ {
if v[i] < m {
m = v[i]
}
}
return
}

// Minimum of a variable number of int arguments
func MinIntV(v1 int, vn ...int) (m int) {
m = v1
for i := 0; i < len(vn); i++ {
if vn[i] < m {
m = vn[i]
}
}
return
}


Peter

On Apr 3, 5:06 pm, Peter Froehlich <peter.hans.froehl...@gmail.com>
wrote:

Peter Froehlich

unread,
Apr 3, 2010, 9:55:55 PM4/3/10
to peterGo, golang-nuts
On Sat, Apr 3, 2010 at 9:25 PM, peterGo <go.pe...@gmail.com> wrote:
> There are a lot of possible variations: min and max, each of the
> number types e.g. int32, int, int64, float32, etc., and different
> parameter lists. For example,

True, true. I guess that suggests generating them from a template
instead, maybe in the style that the vector package is done. On the
other hand, apparently so far nothing besides int and float64 is
needed... :-D

> // Minimum of a slice of int arguments
> func MinIntS(v []int) (m int) {
>        if len(v) > 0 {
>                m = v[0]
>        }
>        for i := 1; i < len(v); i++ {
>                if v[i] < m {
>                        m = v[i]
>                }
>        }
>        return
> }

Personally, I'd make that thing panic() if the slice is empty. But
that's just me, I like asserts too after all, and I am no fan of the
new "default value" rule for maps either. :-D

> // Minimum of a variable number of int arguments
> func MinIntV(v1 int, vn ...int) (m int) {
>        m = v1
>        for i := 0; i < len(vn); i++ {
>                if vn[i] < m {
>                        m = vn[i]
>                }
>        }
>        return
> }

Thanks for that one, I must have missed the version of Go that
introduced types for ... parameters. I'll see how the vector stuff is
done and then I'll check how hard this would be to add to the math
package.

Raif S. Naffah

unread,
Apr 3, 2010, 10:10:36 PM4/3/10
to peterGo, golang-nuts
On Sat, 2010-04-03 at 18:25 -0700, peterGo wrote:
> ...

> There are a lot of possible variations: min and max, each of the
> number types e.g. int32, int, int64, float32, etc., and different
> parameter lists...

how about adding to the reflect package something like:

func Compare(a, b *reflect.Value) int {...}

which would return -1, 0, or 1 depending on a < b, a == b or a > b
respectively?

this could cater for the basic numeric and string types. if in addition
the implementation of this function applies some intelligent conversion
rules it can also be used to compare unsigned and signed numeric values.

finally, it can also cater for other types if for example a and b
implement the same type which in addition implements a Comparable
interface --to borrow from the Java library:

type Comparable interface {
Compare(that *reflect.Value) int
}


cheers;
rsn

signature.asc

Daniel Smith

unread,
Apr 3, 2010, 10:59:47 PM4/3/10
to Peter Froehlich, peterGo, golang-nuts
I might be odd, but I don't like the idea of having to import "math" to get min and max; I would like to see min() and max() become built-in functions like cap() or len(). I think expressions like "math.MinInt" will become tedious; even if you `import . "math"', it's annoying to use a different min() for each type of number. Also, I've seen many C/C++ projects where people who either didn't know/want to #include <math.h> have written their own min() and max() functions-- it's is no fun to try and make two such projects play nice together.

In my ideal world, min() and max() would take two numeric parameters of any type (but they'd have to be the same type) and return the smaller/larger value (which would be the same type as the parameters). But I'm not sure how feasible it would be for the compiler to do that in the absence of generics.

That said, having min and max functions in math would be a big improvement over the current state of affairs; I have various min and max functions scattered throughout my go projects...


--
To unsubscribe, reply using "remove me" as the subject.



--
Daniel Smith
http://www.schaumburggoclub.org/

Norman Yarvin

unread,
Apr 4, 2010, 2:00:35 AM4/4/10
to Daniel Smith, Peter Froehlich, peterGo, golang-nuts
On Sat, Apr 03, 2010 at 08:59:47PM -0600, Daniel Smith wrote:

>I might be odd, but I don't like the idea of having to import "math" to get
>min and max; I would like to see min() and max() become built-in functions
>like cap() or len().

That doesn't seem like an odd desire; min and max are certainly used in a
wider variety of applications than, say, sine and cosine functions are.

>In my ideal world, min() and max() would take two numeric parameters of any
>type (but they'd have to be the same type) and return the smaller/larger
>value (which would be the same type as the parameters).

Why just two parameters? max(a,b,c) has an obvious meaning.

--
Norman Yarvin http://yarchive.net

Daniel Smith

unread,
Apr 4, 2010, 2:43:14 AM4/4/10
to Norman Yarvin, Peter Froehlich, peterGo, golang-nuts
On Sun, Apr 4, 2010 at 12:00 AM, Norman Yarvin <yar...@yarchive.net> wrote:
Why just two parameters?  max(a,b,c) has an obvious meaning.

Well, that would be great, too, but it's not essential. It could also be extended to take a single slice and return the largest value, I suppose. But I didn't want to ask for the moon... :)

Norman Yarvin

unread,
Apr 4, 2010, 12:41:35 PM4/4/10
to Daniel Smith, Peter Froehlich, peterGo, golang-nuts
On Sun, Apr 04, 2010 at 12:43:14AM -0600, Daniel Smith wrote:
>On Sun, Apr 4, 2010 at 12:00 AM, Norman Yarvin <yar...@yarchive.net> wrote:
>
>> Why just two parameters? max(a,b,c) has an obvious meaning.
>>
>
>Well, that would be great, too, but it's not essential. It could also be
>extended to take a single slice and return the largest value, I suppose. But
>I didn't want to ask for the moon... :)

If you were going to make min and max built-in, with all that implies --
a special piece of code for it in the compiler, a special section in the
language definition, and the programmer having to remember that it is
special -- you might as well make them have every meaning they can
reasonably bear. But when arguing for that, the question is: what makes
min and max so special and unique that they deserve a place in the
compiler and in the language definition, rather than in the standard
libraries? Having them take generic types is a feature that would be
useful for a lot of other things, too. Are min and max used so much more
often than those other things?

Charlie Dorian

unread,
Apr 4, 2010, 1:16:12 PM4/4/10
to golang-nuts
What do you propose that Max(a, b complex) should return? Not all
numeric types may be compared using the full range of comparison
operators.

Ryanne Dolan

unread,
Apr 4, 2010, 1:33:24 PM4/4/10
to Peter Froehlich, golang-nuts

Peter,

Go will probally inline those at some point, but I suspect not if they're in a separate package.

Ryanne
- from my phone -

Michael Hoisie

unread,
Apr 4, 2010, 2:53:57 PM4/4/10
to golang-nuts
I think having a built-in min and max would be useful.

On Apr 4, 10:33 am, Ryanne Dolan <ryannedo...@gmail.com> wrote:
> Peter,
>
> Go will probally inline those at some point, but I suspect not if they're in
> a separate package.
>
> Ryanne
> - from my phone -
>

> On Apr 3, 2010 4:07 PM, "Peter Froehlich" <peter.hans.froehl...@gmail.com>

peterGo

unread,
Apr 4, 2010, 5:06:58 PM4/4/10
to golang-nuts
Peter

Here's the set of Min() functions for ints, rewritten, with a uniform
structure, to illustrate a pattern. The pattern encapsulates the min
algorithm in the fundamental MinInt() function and expression LTInt().
The MinIntS() and MinIntV() functions then become wrapper functions,
merely reflecting the data structure of their parameters. The same
pattern applies for both min, i.e. LT(), and max, i.e. GT(), and for
all numeric types for which LT() and GT() are valid.

This pattern could be used as the basis for deriving a numeric type
agnostic code generation template, perhaps using interface{}, like the
Go vector package.

// Less Than for a pair of int arguments
func LTInt(v2, v1 int) bool {
return v2 < v1
}

// Minimum of a pair of int arguments

func MinInt(v1, v2 int) (m int) {
m = v1
if LTInt(v2, v1) {
m = v2
}
return
}

// Minimum of a slice of int arguments
func MinIntS(v []int) (m int) {
if len(v) > 0 {
m = v[0]
}
for i := 1; i < len(v); i++ {

m = MinInt(m, v[i])
}
return
}

// Minimum of a variable number of int arguments
func MinIntV(v1 int, vn ...int) (m int) {
m = v1

if len(vn) > 0 {
m = MinInt(m, MinIntS(vn))
}
return
}


Peter

On Apr 3, 9:55 pm, Peter Froehlich <peter.hans.froehl...@gmail.com>
wrote:

Daniel Smith

unread,
Apr 5, 2010, 1:24:53 AM4/5/10
to Norman Yarvin, Peter Froehlich, peterGo, golang-nuts
Responding to everyone at once:


On Sun, Apr 4, 2010 at 12:16 PM, Charlie Dorian <cldo...@gmail.com> wrote:
What do you propose that Max(a, b complex) should return?  Not all
numeric types may be compared using the full range of comparison
operators.

I don't know off the top of my head what max/min mean on complex numbers, but it seems like that's an issue to be resolved when/if we get a complex number type.

On Sun, Apr 4, 2010 at 11:41 AM, Norman Yarvin <yar...@yarchive.net> wrote:
If you were going to make min and max built-in, with all that implies --
a special piece of code for it in the compiler, a special section in the
language definition, and the programmer having to remember that it is
special -- you might as well make them have every meaning they can
reasonably bear.  But when arguing for that, the question is: what makes
min and max so special and unique that they deserve a place in the
compiler and in the language definition, rather than in the standard
libraries?  Having them take generic types is a feature that would be
useful for a lot of other things, too.  Are min and max used so much more
often than those other things?

This is a good objection, and I only have partial answers.

If we had generics, I would instead advocate for min and max functions somewhere easily accessible; I dislike the "Int" part more than the "math." part of "math.MaxInt". If enough such functions [1] can be thought of, I think I would make a "common" package and put them there (and ideally, the "common" package's contents would be useful, clear, and few, so that `import . "common"` would become a normal import).

But we don't have generics and seems like it's going to be a while; something has to be done in the meantime or everyone will end up with half a dozen different min/max implementations. I'd be unhappy if we got stuck using "math.MaxInt" everywhere because so much code had been written by the time we got generics that no one wanted to change it.

So I guess my point is that there currently isn't a good way to write these functions-- therefore the compiler/language should help us out. Whenever we do get generics, they could be moved out to a package transparently (e.g., the complier could insert a `import . "common"` line inside source files), if that is desirable. The current built-in "copy" is presumably built-in for the same reasons and should suffer the same fate.

[1] there are probably other functions with similar usage frequencies; I may not be a typical use case, but I'd place the copy() built-in and a hypothetical compare() function which compared two arrays for equality (an analog of the copy() function) in the same category. There are probably a few others.

jimmy frasche

unread,
Apr 5, 2010, 1:28:11 AM4/5/10
to Daniel Smith, Norman Yarvin, Peter Froehlich, peterGo, golang-nuts
On Sun, Apr 4, 2010 at 10:24 PM, Daniel Smith <luken...@gmail.com> wrote:
> I don't know off the top of my head what max/min mean on complex numbers,
> but it seems like that's an issue to be resolved when/if we get a complex
> number type.

We do have complex numbers. The complex numbers are unordered.

Daniel Smith

unread,
Apr 5, 2010, 1:57:02 AM4/5/10
to jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, golang-nuts
Oh wow, you're right-- whoops, somehow I missed those. Sweet! And now that I think about it more, I wouldn't expect max/min to accept complex numbers, or any type that can't be compared with <.

Peter Williams

unread,
Apr 5, 2010, 2:36:55 AM4/5/10
to jimmy frasche, Daniel Smith, Norman Yarvin, Peter Froehlich, peterGo, golang-nuts

Complex numbers have a magnitude (also known as the absolute value or
modulus) which could be used to satisfy the requirements of min/max
functions.

Peter

Steven

unread,
Apr 5, 2010, 2:37:57 AM4/5/10
to Daniel Smith, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, golang-nuts

The only logical comparison of complex numbers would be by their
moduli, in the general case. However, this could be done by taking the
modulus of each argument, just as you would if you were doing other
specific comparisons. Unfortunately, while real and imag are built in,
there's no mod or arg. You'd have to do it yourself/use a library
function.

jimmy frasche

unread,
Apr 5, 2010, 2:40:37 AM4/5/10
to Steven, Daniel Smith, Norman Yarvin, Peter Froehlich, peterGo, golang-nuts
There are infinite complex numbers that satisfy each moduli. If you
have a list of three complex numbers such that one has moduli 1 and
the others have moduli 2, then the number of moduli 1 is in this case
the clear minimum value but which of the two numbers of moduli 2 are
the max?

Norman Yarvin

unread,
Apr 5, 2010, 5:27:04 AM4/5/10
to Peter Williams, jimmy frasche, Daniel Smith, Peter Froehlich, peterGo, golang-nuts

It's much better to leave it undefined. That conforms to the normal
mathematical usages, which have it undefined. When people convert a
routine from real to complex arithmetic, it helps if they get an error
message for any calls to min or max: it lets them know they have to
replace those calls. Exactly what to replace them with would take some
decision-making: it might be the maximum of the real part of the number,
the maximum absolute value, or something else.

Kyle Consalus

unread,
Apr 5, 2010, 12:05:57 PM4/5/10
to Daniel Smith, Norman Yarvin, Peter Froehlich, peterGo, golang-nuts
I've not yet found the lack of a common 'max'/'min' to be an issue.

Most of the time, I just do:

if x < 4 {
   x = 4
}

Or the like. 
It's absurdly simple, convenient, and with the current absence of inlining, more efficient than a function.

I'm not sure it is worth importing another package or changing the language spec to turn those obvious
three lines into one.

Then again, I'm also not terrifically offended by multiple implementations of "min/max" sitting around.
Such functions are really quite small and not particularly error prone, so it seems plausible to me that the cost of
repeating them is less than the cost of adding dependencies.

I think it'd be nice if generic functions like "min" and "max" could be implemented simply in Go, but based on my
experience, trying to remove the duplication is fixing something that isn't really a practical problem.

On Sun, Apr 4, 2010 at 10:24 PM, Daniel Smith <luken...@gmail.com> wrote:

Charlie Dorian

unread,
Apr 5, 2010, 12:19:00 PM4/5/10
to golang-nuts
CL 874041, currently under review, is a complex math package. The
function cmath.Abs returns the modulus; cmath.Phase returns the
argument.

Charlie Dorian

unread,
Apr 5, 2010, 12:45:09 PM4/5/10
to golang-nuts
As you pointed out, "The complex numbers are unordered. "

If modulus were used for the comparison, then:
min(-2, 1) = -2
min(-2+0i, 1+0i) = 1

chris dollin

unread,
Apr 5, 2010, 12:52:11 PM4/5/10
to Kyle Consalus, Daniel Smith, Norman Yarvin, Peter Froehlich, peterGo, golang-nuts
On 5 April 2010 17:05, Kyle Consalus <cons...@gmail.com> wrote:
I've not yet found the lack of a common 'max'/'min' to be an issue.

Most of the time, I just do:

if x < 4 {
   x = 4
}

Or the like. 
It's absurdly simple, convenient, and with the current absence of inlining, more efficient than a function.

It's a bit of a mess when the max/min is the argument to a function.
You have to leave expression-space for statement-space, since Go
has no conditional expression.

Chris

--
Chris "unconditionally" Dollin

Alexandru Plugaru

unread,
Jul 26, 2011, 3:34:09 PM7/26/11
to golan...@googlegroups.com
So are there any plans to inline min/max at this point?

John Asmuth

unread,
Jul 26, 2011, 3:45:36 PM7/26/11
to golan...@googlegroups.com
I think there are many things that people would like to have as built-ins, mostly because the built-ins are allowed to be generic.

I'd rather we just had generics.

jam...@gmail.com

unread,
Jul 5, 2013, 12:39:35 PM7/5/13
to golan...@googlegroups.com
I agree. Coming from C++ and learning Go now, I am missing templates the most (though generics as in Java would suffice given the cool interface duck typing lark), followed soon after by things like a lack of function overloading with different arguments (or any form of default arguments), and lack of ternary operator.

Kevin Gillette

unread,
Jul 7, 2013, 4:04:10 PM7/7/13
to golan...@googlegroups.com, jam...@gmail.com
On Friday, July 5, 2013 10:39:35 AM UTC-6, jam...@gmail.com wrote:
I am missing templates the most (though generics as in Java would suffice given the cool interface duck typing lark), followed soon after by things like a lack of function overloading with different arguments (or any form of default arguments), and lack of ternary operator.

All of which were considered and deliberately excluded from the language.

Robert Melton

unread,
Jul 7, 2013, 4:59:54 PM7/7/13
to Kevin Gillette, golang-nuts, jam...@gmail.com
Isn't the door for generics still open if they can find a way to implement them that isn't atrocious?

As for the other three points.  
- Function overloading ... 1 function name, 27 implementations... left out for a reason. 
- Default arguments can be emulated in various ways if you really want them, but isn't being explicit nice?
- Ternary operator ... if ternary operator comes up in a "top 4 gripes" the language is doing incredibly well -- also, they are both pointless and evil to my mind. 

--
Robert Melton

Kevin Gillette

unread,
Jul 7, 2013, 11:49:58 PM7/7/13
to golan...@googlegroups.com, Kevin Gillette, jam...@gmail.com
On Sunday, July 7, 2013 2:59:54 PM UTC-6, Robert Melton wrote:
Isn't the door for generics still open if they can find a way to implement them that isn't atrocious?

That's pretty much the criterion for the inclusion of anything. Most things that C++ added to C are atrocious in their appearance and design, and many of those concepts are atrocious regardless of their particular language implementation, hence most things that C++ innovated will never make it into Go (and surely not in their C++ form).
 
As for the other three points.  
- Function overloading ... 1 function name, 27 implementations... left out for a reason.

More generally, it encourages the programmer to be non-deliberate in their API design. It also results in lack of clarity regarding behavior -- this would be somewhat mitigated if one of the implementations must designated as primary and all other overloaded implementations must call the primary, ensuring that behavior is equivalent regardless of arguments/types involved and that all other implementations are simply convenience wrappers.
 
- Default arguments can be emulated in various ways if you really want them, but isn't being explicit nice?

Being explicit is desirable for readability. If you mean that allowing explicit default arguments rather than emulating them is nicer, it'd be ironic since default arguments are all about implicitness.
 
- Ternary operator ... if ternary operator comes up in a "top 4 gripes" the language is doing incredibly well -- also, they are both pointless and evil to my mind.

The ternary operator is a bane to readability, has subtly different (and always subtle) semantics among different languages, especially in terms of associativity; most programmers don't know how they work, and expressions involving nested ternaries often lead to stowaway bugs for corner cases that start wreaking havok well after you've forgotten what the code was supposed to do in the first place. Several languages claim to "do them right" (in terms of associativity), but for readability sake, "doing them right" should involve requiring parentheses to surround each ternary expression.

John Nagle

unread,
Jul 8, 2013, 12:17:27 AM7/8/13
to golan...@googlegroups.com
On 7/7/2013 8:49 PM, Kevin Gillette wrote:
> On Sunday, July 7, 2013 2:59:54 PM UTC-6, Robert Melton wrote:
>
>> Isn't the door for generics still open if they can find a way to implement
>> them that isn't atrocious?
>>
>
> That's pretty much the criterion for the inclusion of anything.

It's really hard to fit user-defined generics into Go. Most of
the obvious ways lead to horrid messes.

Go does have parameterized types. Channels and maps are
parameterized types. It just doesn't have user-defined parameterized
types.

Building in a few more generic functions might be worthwhile.
"min" and "max" as built-ins would not be out of place.
A few other useful operations:

- a built-in "deep copy' for any type which is nonrecursive (i.e.
cannot result in a pointer to itself, and thus represents at worst
a tree of finite depth

- a built-in conversion from a struct type to an array of interfaces

- a built in conversion from an array of interfaces to a struct type

These are all common operations which can be done with reflection,
but slowly, and can be done very efficiently with code generated
for the specific type involved. The last two come up in marshalling
and unmarshalling, as when talking to a database or dissecting JSON
or XML.

Unless there's a significant performance win over a reflection-based
solution, it's probably not worth the trouble to add a generic function.

John Nagle

Tor Langballe

unread,
Jul 8, 2013, 10:07:56 AM7/8/13
to golan...@googlegroups.com
I notice I actually need a function Maximize(a*, b) more than anything else; (and Minimize)

I need to set a value a to another value b if b > a. This avoids having to repeat a long variable name too:

rect.min.x = Max(rect.min.x, x)

becomes

Maximize(&rect.min.x, x)

Personally, I have a folder "util" of shadow-packages beginning with "u" and then the same word as a standard package, that adds functionality that might typically perhaps have belonged in that package; Thus I have:

umath.MaxInt64(a, b int64) int64
and umath.Maximize(a *int64, b int64)

in my umath package

Thomas Dybdahl Ahle

unread,
Aug 20, 2013, 8:35:28 PM8/20/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo
Right, so the ideal situation would be to use interfaces.
If we could make 'func max(interface{<}, interface{<}) bool' and have it work on basic types. How awesome would it be?

Kyle Lemons

unread,
Aug 20, 2013, 10:15:27 PM8/20/13
to Thomas Dybdahl Ahle, golang-nuts, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo
On Tue, Aug 20, 2013 at 5:35 PM, Thomas Dybdahl Ahle <lob...@gmail.com> wrote:
Right, so the ideal situation would be to use interfaces.
If we could make 'func max(interface{<}, interface{<}) bool' and have it work on basic types. How awesome would it be?

How would you interpret `max(3.5, "foo")`?  Both of those types have a < operator.

On Monday, April 5, 2010 7:57:02 AM UTC+2, Daniel Smith wrote:
Oh wow, you're right-- whoops, somehow I missed those. Sweet! And now that I think about it more, I wouldn't expect max/min to accept complex numbers, or any type that can't be compared with <.

On Mon, Apr 5, 2010 at 12:28 AM, jimmy frasche <soapbo...@gmail.com> wrote:
On Sun, Apr 4, 2010 at 10:24 PM, Daniel Smith <luken...@gmail.com> wrote:
> I don't know off the top of my head what max/min mean on complex numbers,
> but it seems like that's an issue to be resolved when/if we get a complex
> number type.

We do have complex numbers. The complex numbers are unordered.



--
Daniel Smith
http://www.schaumburggoclub.org/

--
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.

Liigo Zhuang

unread,
Aug 21, 2013, 12:58:07 AM8/21/13
to Robert Melton, Kevin Gillette, golang-nuts, jam...@gmail.com

2013/7/8 Robert Melton <rme...@gmail.com>
+1
+1
+1
+10086 for generics
 
--
Robert Melton

--
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.
 
 

Dan Kortschak

unread,
Aug 21, 2013, 1:33:31 AM8/21/13
to Liigo Zhuang, Robert Melton, Kevin Gillette, golang-nuts, jam...@gmail.com
The C++ room is down the corridor.

Kevin Gillette

unread,
Aug 21, 2013, 1:50:44 AM8/21/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo
Syntax is generally not considered the "hard" part of putting any further kind of generic programming into Go. For those "generics" aspects that are not yet covered, there's a fundamental tradeoff that nobody knows an effective way around, and which the community as a whole is not willing to choose either of the existing implementation routes: explosion of generated code, or erasure-style with low runtime efficiency (albeit, yes, static verification).

That said, the _syntactic_ difficulty in specifying a max is that you must also specify a relationship _between_ function parameters, specifically that all parameters are the same type.

Luke Mauldin

unread,
Aug 21, 2013, 12:59:04 PM8/21/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo
Kevin,

I liked the way you differentiated between the runtime aspect of generics and the syntactic difficulty of adding them to the language.  I have read several of the generic discussions and that is a good distinction that is not often clearly understood.


All,

For the runtime part of the discussion, what about implementing generics similar to Microsoft's approach with C#?  If I understand it correctly, they generate separate runtime code for each value type but all pointer types share the same runtime code.  For example, if a program constructs these four lists:  List<int>, List<bool>, List<string>, List<CustomType>.  List<int> and List<bool> would have unique code but List<string> and List<CustomType> would share a common "template" based on a pointer type.


Luke

GreatOdinsRaven

unread,
Aug 21, 2013, 1:21:38 PM8/21/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo
The CLR/C# approach was already discussed and rejected. The approach that MS took (which I'm a big fan of) has a lot of nuances that make its implementation difficult. I've been trying fruitlessly to find the reasons for it, I could only find this: https://groups.google.com/forum/#!topic/golang-nuts/PYJayE50JZg%5B76-100-false%5D. There was another discussion that was more specific and it had something to do with how an "interface" in CLR land doesn't jive with an "interface" in Go land. 

Another interesting thread I remember had someone proposing Ada-style generics (wish I knew Ada better...) 

I think it's safe to say that generics are *not* going to make it into Go at least until Go 2, it doesn't seem to be even a blip on the radar. At this point, either we copy-pasta code, or we go the interface{} + reflection route and that's all there is to it. 

Luke Mauldin

unread,
Aug 21, 2013, 1:43:23 PM8/21/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo
I completely understand that we will not see generics in Go until at least Go 2.  However, can anyone help me understand a high-level overview of some of the nuances that would make implementation of the CLR generic approach difficult in Go?

Luke

luz...@gmail.com

unread,
Aug 21, 2013, 2:07:49 PM8/21/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo


On Wednesday, August 21, 2013 7:43:23 PM UTC+2, Luke Mauldin wrote:
I completely understand that we will not see generics in Go until at least Go 2.  However, can anyone help me understand a high-level overview of some of the nuances that would make implementation of the CLR generic approach difficult in Go?
  
I'm no expert, and I didn't follow previous generics discussions, but the .NET JIT compiler generates the code at run time to avoid code bloat:

"At run time, the actual machine code produced depends on whether the specified types are value or reference type. If the client specifies a value type, the JIT compiler replaces the generic type parameters in the IL with the specific value type, and compiles it to native code. However, the JIT compiler keeps track of type-specific server code it already generated. If the JIT compiler is asked to compile the generic server with a value type it has already compiled to machine code, it simply returns a reference to that server code."

AFAIK Go doesn't have a JIT compiler or intermediate language or runtime code generation.

Luke Mauldin

unread,
Aug 21, 2013, 2:58:40 PM8/21/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
Although Go doesn't have a JIT compiler, I would think its regular compiler could generate all of the necessary code at compile time and the amount of code would be "as small as possible" due to features like code sharing, etc.  
How does Go support such efficient "generic" maps/slices?  What are the factors limiting those solutions from solving the general runtime generic solution?

Luke

Kevin Gillette

unread,
Aug 23, 2013, 11:10:44 PM8/23/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
Code sharing is computationally suboptimal most of the time -- type erasure (essentially treating everything like an interface{} value) has the most code sharing potential, but is more often than not considerably slower than specialization (which results in binary bloat, and potentially processor cache inefficiency).  Some things can be done efficiently with respect to code sharing, such as slice element handling (e.g. reversing a slice), since the only type-dependent variable involved would be the size of the element type.

On the other hand, something like a type-generic Max function is more involved... You could optimistically say that we only need one *primary* specialized version for each numeric type family (ints, uints, floats, and complex types), wherein each family's specialized version internally uses the greatest precision type in that familiy (i.e. all int handling uses int64 internally). However, to get to the point of using the family-generic implementation at runtime, the parameters must be converted to the internally-used type, meaning that the family-generic implementation must either, 1) be wrapped for each concrete type in that family, or 2) an erasure-style wrapper must be generated which takes something like an interface{} at runtime and type-asserts it to the internally used type.

The problem with #1 is that comparison (and many things people pine over lack of generics for) do not require enough instructions compared to conversion to warrant any kind of code sharing (in this case, there'd be more code involved to adapt each type in a family to its implementation then there would be in making a self-contained specialized implementation for each type). People would also want to abuse the generics mechanism: if `func Less(x, y T) bool` can satisfy `func(x, y int8) bool`, then why not specify the generic implementation as `func Less(x T1, y T2) bool`, and have the compiler figure out every combination of inter-convertible types you ask for, so that it can satisfy `func(x int8, y int64) bool` and `func(x int64, y int8) bool` ? This could easily add megabytes worth of generated code just to satisfy the lazy/undisciplined whims of the programmer.

The problem with #2 is that we already have that -- the language changes involved would pretty much just be a sugar coating on top of the reflection system, and compared to type-specific code, reflection is plain slow. Some of that slowness can be mitigated by the presence of a JIT optimizer, but that makes binaries a bit thicker and adds overhead in a number of places; to counteract the thickness, using shared libraries is often found to be an acceptable solution, but for a language ecosystem like Go's, where ease of deployment is considered a fundamental characteristic, for many of us the shared-library solution would be more trouble than it's worth.

Regarding the .NET style solution (which I know nothing about): there may exist solutions with less drastic tradeoffs when used with a language designed around that solution. If it's said that there would be trouble adapting it for Go because of differing conceptualizations of interfaces, I would not be surprised (and would further be unsurprised if the .NET solution fundamentally could never be adapted to work with Go because of those differing assumptions). In this case, it's sounding like C# generics would have Java-esque memory problems if it generated all potentially needed specializations at compile time -- in many ways, Go tries to keep the role of the runtime light: handling anything related to scheduling/concurrency and garbage collection, but not much beyond that, while the .NET runtime seems to take a much more active role.

Luke Mauldin

unread,
Aug 26, 2013, 10:10:59 AM8/26/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
Kevin,

Thank you for the very detailed response.  It was very helpful.  I have one additional question, how were the problems you discussed resolved with the implementation of slices and maps?  

Luke

atomly

unread,
Aug 26, 2013, 12:02:00 PM8/26/13
to Kevin Gillette, golang-nuts, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
What about option #3, generic template for the general case,, but JIT compiler makes specialized copies for types that are used often?

Also, what do you mean by Java-esque memory problems?

:: atomly ::

[ ato...@atomly.com : www.atomly.com  : http://blog.atomly.com/ ...
[ atomiq records : new york city : +1.347.692.8661 ...
[ e-mail atomly-new...@atomly.com for atomly info and updates ...


--

Kevin Gillette

unread,
Aug 26, 2013, 4:44:16 PM8/26/13
to golan...@googlegroups.com, Kevin Gillette, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
On Monday, August 26, 2013 10:02:00 AM UTC-6, atomly wrote:
What about option #3, generic template for the general case, but JIT compiler makes specialized copies for types that are used often?

There are Go specific "cultural" downsides to this: 1) unless the JIT outputs bytecode to be interpreted rather than machine code to be directly executed, we'd have to give up non-executable memory pages, which is a security feature (we don't like trading security for features here, and it's not good enough for inclusion if it needs to be interpreted). 2) possibly with the exception of a completely non-optimizing JIT, or rather specialized JITs, they can be large enough that they'd warrant a shared lib (they can be larger than the rest of the current runtime combined), and most of us seem to like statically linked builds. Either one of those issues would be enough to make the option unattractive for use in Go.
 
Also, what do you mean by Java-esque memory problems?

I'm alluding to the JVM being known for having a comparatively very large memory overhead (a hello world program running in JVM can potentially cost dozens of megabytes in the resident set). Since the CLR allows for more (straightforward) runtime dynamism than something like C++, it'd be insufficient to only give the runtime access to those template specializations which are known at compile time to be needed, so within those requirements, either all possible specializations would need to be generated at compile time, or as they already do, a JIT system would be needed. Precompiling all possible specializations (which from what I've seen of .NET, could easily be combinatorial) could produce very large binaries.

Kevin Gillette

unread,
Aug 26, 2013, 4:50:27 PM8/26/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
On Monday, August 26, 2013 8:10:59 AM UTC-6, Luke Mauldin wrote:
Kevin,

Thank you for the very detailed response.  It was very helpful.  I have one additional question, how were the problems you discussed resolved with the implementation of slices and maps?

 The algorithms for handling maps and slices are comparatively simple. Slices can have a custom code generation per used type while maintaining a very small footprint, and the map implementation probably only needs a type-specific hash function and size-of-type information for each combination of key and value.

Both of these, in their current implementation _could_ have had "generic" implementations if we had generics, but that doesn't mean the best approach would have been a "generics" implementation. If and when Go gets generics, that does not mean that it will include all aspects of generic programming that other languages have. For example, it's much less likely that we'll ever get operator overloading (we could have had those already, but we've intentionally avoided them).

Luke Mauldin

unread,
Aug 26, 2013, 7:34:31 PM8/26/13
to golan...@googlegroups.com, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
So the Go compiler examines all of the slices in the program and generates a small amount of custom code for each unique slice type?

Luke

Kyle Lemons

unread,
Aug 26, 2013, 7:58:38 PM8/26/13
to Luke Mauldin, golang-nuts, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
last time I checked, I thought it simply generated the code for a "copy" or "append" inline, based on the size of the type.


--

Kevin Gillette

unread,
Aug 27, 2013, 12:00:25 PM8/27/13
to golan...@googlegroups.com, Luke Mauldin, jimmy frasche, Norman Yarvin, Peter Froehlich, peterGo, luz...@gmail.com
On Monday, August 26, 2013 5:58:38 PM UTC-6, Kyle Lemons wrote:
last time I checked, I thought it simply generated the code for a "copy" or "append" inline, based on the size of the type.

On Mon, Aug 26, 2013 at 4:34 PM, Luke Mauldin <lukem...@gmail.com> wrote:
So the Go compiler examines all of the slices in the program and generates a small amount of custom code for each unique slice type?

@Luke: what Kyle said is what I meant. Slice operations are really that cheap -- for most of what you can do with a slice, the number of instructions involved are fewer (and cheaper) to do it inline than the number involved to push args on a stack and call either a type-specific or generic implementation (thus even if we had generics, it'd be hard to claim they'd be better for this purpose than what we're currently doing). Likewise, maps are also a solved problem, and last time I looked, they have enough differences to not be a useful reference of comparison to the problems with implementing generics in Go.
Reply all
Reply to author
Forward
0 new messages