Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmp: new package with Ordered, Compare, Less; min, max as builtins #59488

Closed
ianlancetaylor opened this issue Apr 7, 2023 · 143 comments
Closed

Comments

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Apr 7, 2023

Update, May 17 2023: Current proposal at #59488 (comment).


(Edited to change the package from sort to cmp).

I propose adding a new package cmp, which will initially define the following:

// Ordered is a constraint that permits any ordered type: any type
// that supports the operators < <= >= >.
// If future releases of Go add new ordered types,
// this constraint will be modified to include them.
type Ordered interface { ... }

// Min returns the smallest of a and b. If a and b are equal, Min returns a.
func Min[T Ordered](a, b T) T

// Max returns the largest of a and b., If a and b are equal, Max returns a.
func Max[T Ordered](a, b T) T

The Min and Max functions are trivial but are widely used. The standard library contains 14 versions of Min and 7 versions of Max (not counting math.Min and math.Max). With such wide usage it's worth providing versions in the standard library.

The Ordered constraint is useful for Min and Max and also for sorting functions such as those in the x/exp/slices package. This would replace constraints.Ordered in the x/exp/constraints package. GitHub code search reports that constraints.Ordered appears in 2300 files in GitHub, so people do find it useful.

If we adopt this proposal, we would not add a constraints package to the standard library.

Ordered, Min, and Max are related to comparing values. Therefore, a package cmp is a reasonable location for them. We could also add them to the existing package sort.

Possible other additions to a cmp package would be names for the values returned by bytes.Compare and similar functions, such as cmp.Less (-1), cmp.Eq (0), and cmp.Greater (1). We could also add a function wrappers that reverses the sense of a less-than comparator, and one that reverses the sense of a byte.Compare style comparator.

We should define how Min and Max treat NaN values when instantiated with a floating-point type. I propose that if the first argument is a NaN then it will be returned, otherwise if the second argument is a NaN then it will be returned, otherwise compare with <. When comparing a negative zero and a positive zero, I propose that the first argument will be returned, as with equal values; that is both Min(0.0, math.Copysign(0.0, -1)) and Min(math.Copysign(0.0, -1), 0.0) will return 0.

Other languages

C++ puts std::min and std::max in <algorithm>. Go's standard library doesn't have anything comparable. The C++ <algorithm> header is a bit of a catch-all, including functions that Go has in sort and container/heap, and functions that Go might put into a possible iter package in the future.

Java has Math.min and Math.max, which are overloaded functions that take double, float, int, or long arguments. Go already has math.Min and math.Max, but since Go doesn't have overloading they only take float64 arguments. Most functions in Go's match package are most naturally defined for floating-point values, so even generic versions of them might not take all ordered values. And math.Ordered doesn't seem right.

Python has min and max builtin functions. There's no particular reasons to make these functions predeclared in Go, since we can write them directly in Go.

Rust has std::cmp::min and std::cmp::max. std::cmp also has the Rust equivalents of comparable and Ordered, and some support for comparator functions. This offers some support for using a cmp package in Go. On the other hand Rust's standard library has slice/vector sorting, and has various sorted container types, but as far as I know (which isn't far) doesn't have a general purpose sorting algorithm like the one in Go's sort package.

@gopherbot gopherbot added this to the Proposal milestone Apr 7, 2023
@apparentlymart
Copy link

apparentlymart commented Apr 7, 2023

These seem like good utilities to have in the standard library, and I think sort is an intuitive place to put them.

Did you consider making Min and Max be variadic instead, accepting an arbitrary number of arguments of the same type?

func Min[T Ordered](vals ...T) T
func Max[T Ordered](vals ...T) T

It would of course be possible to implement the variadic versions in terms of the two-argument versions in my own code if the standard library didn't offer a variadic version, so this is perhaps superflous, but since the variadic version could still be used with two arguments it doesn't seem like it loses any functionality to make it variadic.

(Perhaps there is a performance cost compared to just regular arguments? Is it significant?)

@apparentlymart
Copy link

apparentlymart commented Apr 7, 2023

It sounds like Ordered represents a partial order rather than a total order. Part of me wants that explicit in the name, but at the same time it doesn't seem super likely that there would ever be a "total order" interface alongside this -- at least not in package sort -- so probably just fine to leave it with a short name and just mention the expectation in the docs (as the example above does, albeit by reference to specific operators rather than using the term "partial order").

@randall77
Copy link
Contributor

When T is a float, we will need to describe behavior in all the special cases (NaN, +/- 0).

@AndrewHarrisSPU
Copy link

AndrewHarrisSPU commented Apr 7, 2023

When T is a float, we will need to describe behavior in all the special cases (NaN, +/- 0).

Is there any case for the sort ordering constraint to just not accept floats? The math.Min/Max functions have defined behavior that I'd assume sort would want to match anyways.

@randall77
Copy link
Contributor

Is there any case for the sort ordering constraint to just not accept floats?

Floats are certainly tricky. But most users probably don't hit and/or care about those weird cases. So from an ergonomic API view, allowing floats makes sense. It just complicates the implementation a bit, and requires a bit of extra doc for those who care.

@robpike
Copy link
Contributor

robpike commented Apr 7, 2023

I lean towards putting these in a separate cmp package, for several reasons. For starters, min and max are comparators, not really sorters. As you said, too, sort is already expansive, while the details of ordering can be neatly separated, implying they should be. And since floats are messy, with no total order, having their ordering delineated in a separate package provides a location on which focus on the difficulty, isolating the problem. It might even be there are variants of Ordered to deal with this.

Also,cmp.Min reads better than sort.Min; at least I think it does.

There is no harm in putting these things in a separate package, and the possibility of appreciable good accruing.

@apparentlymart
Copy link

I suppose this question about floats boils down to specifying how Min and Max will treat a situation where they are asked to compare a and b where a is neither less than or equal b nor greater than nor equal b.

It will presumably then need to make an essentially-arbitrary decision, but that decision ought to be subject to Go's compatibility promises. Is there a typical answer to this that users might expect from other languages, or is this literally a case of "just pick a behavior and document it"?

@ianlancetaylor
Copy link
Contributor Author

@apparentlymart In the general case variadic functions will be more expensive, because they require constructing a slice. Of course in general the functions will likely be inlined and the cost will disappear. But, especially since almost all existing examples I found take just two arguments, I think it's preferable to have the two argument version. We can consider adding variadic versions separately. I'm open to counter-argument.

Ordered is a constraint that describes the set of types that support the < operator and friends. This is exactly the set of types that the language spec describes as "ordered". So I think that Ordered is the right name even though arguably for floating-point types we only describe a partial ordering.

@randall77 I think the suggested documentation is clear about the behavior for ±0. I suppose we may have to document what happens for NaN. Sigh. I think my preference would be to say that if either value is a NaN, we will return either a or b but which one we return is unspecified. People who need more clarity can use math.Min.

@ianlancetaylor
Copy link
Contributor Author

@robpike I am fine with using a new cmp package if the preference leans that way. Anybody who prefer cmp to sort, please thumbs-up @robpike 's note. Thanks.

@apparentlymart
Copy link

apparentlymart commented Apr 7, 2023

I don't feel strongly about them being variadic; I was considering it only because it seemed like a more general form that could therefore be more broadly useful without losing the convenience of the two-argument case.

However, the fact that the other examples you found are not variadic does indeed seem to suggest that it's not necessary, and combining with the possible performance cost does seem to make the two-argument form seem like the better choice. A variadic version would be pretty simple to implement elsewhere when needed.

@Merovius
Copy link
Contributor

Merovius commented Apr 8, 2023

@randall77

It just complicates the implementation a bit, and requires a bit of extra doc for those who care.

As far as I know, the only way to implement this is via reflect (normal type-assertions/type-switches won't cover things like type F float64), which seems excessive. I'd assume most people would prefer a well-performing if a < b { return a } return b over something that might use reflect just to compare two values - even if it isn't correct in all cases.

If we had something like #45380 it would undoubtedly be simple, but that's still on ice.

Personally, I neither like the idea of adding a constraint that excludes floats, nor do I like the idea of adding an imprecise implementation for floats to the stdlib, nor do I like the idea of using reflect to add a precise version. So, unless we'd use some compiler/runtime shenanigans (which I'd resent a bit as well, because IMO user code should be able to solve this kind of problem as well) I'd be in favor of putting this off until we get something like #45380. For 3rd party code, the decision of using the simple-if-not-strictly-correct code is less problematic than for the standard library.

@fgm
Copy link

fgm commented Apr 8, 2023

Extrapolating a bit, if a builtin Ordered constraint also accepted types with some Compare method (name to be bikeshedded), could that be a path to supporting those same comparison operators on them ? I know this is not the original goal, but it would fit nicely along.

@Merovius
Copy link
Contributor

Merovius commented Apr 8, 2023

@fgm The standard library is converging on exporting two APIs to support "native" and "custom" operators. e.g. having slices.Equal and slices.EqualFunc. By that approach, we'd have to have Max and MaxFunc (etc). Which seems overkill to me.

For what it's worth, in my opinion there just is no unambiguously good way to support both "native" and "custom" operators. There are alternatives to the "two APIs" approach, but they have their own problems.

@leaxoy
Copy link

leaxoy commented Apr 8, 2023

One question, is it possible make Ordered an ordinary interface? Ordinary interface implemented by any user defined type would be more useful and general.

And, as rob mentioned, cmp package is more reasonable.

@randall77
Copy link
Contributor

@Merovius I think we can make the implementation fast and general. For example:

func Min[T Ordered](a, b T) T {
    if a != a || b != b { ... some special code ... }
    ... normal min code ...
}

The first line there will completely compile away for non-float types.
For floats, the first line will capture any NaN values, which we can then handle at our leisure.
It would require the normal min code to handle +/-inf and +/-0 correctly, but it probably would.

@fzipp
Copy link
Contributor

fzipp commented Apr 8, 2023

I'd rather like to see the cmp package name for something like #45200, which is more about equality for testing. I don't know if Ordered/Min/Max would fit into such a package.

@seebs
Copy link
Contributor

seebs commented Apr 8, 2023

So, I have conflicting desires:

  1. I want a min function that takes arbitrary numbers of things.
  2. I don't want to pay the slice overhead when the arbitrary number is 2.

@neild
Copy link
Contributor

neild commented Apr 8, 2023

slices.Min?

@earthboundkid
Copy link
Contributor

Note that a new cmp package was previously proposed here: #58559 (comment)

@earthboundkid
Copy link
Contributor

I lean towards having cmp.TotalOrdered which excludes floats and having a comment telling users to use math.Min/Max/Compare if they need floats. If someone really needs a generic sort that includes fast float missorting they can write it themselves trivially.

@gophun
Copy link

gophun commented Apr 8, 2023

@fzipp
Yes, github.com/google/go-cmp/cmp is a popular package in the Go ecosystem and it is recommended by Google's Go style guide, but if you need both in a test file you can always use an import alias:

import (
	"cmp"
	testcmp "github.com/google/go-cmp/cmp"
)

Proposal #45200 for "testing/cmp" could be changed to "testing/equal" or "testing/diff" or something else. It would require reflection, so it should be kept separate from the "cmp" package that is discussed here.

@jimmyfrasche
Copy link
Member

variadic Min/Max has some weird corners.

You want to keep the property that Min(x, Min(y, z)) = Min(x, y, Min(z)) = Min(x, y, z, Min[T]()) where T is the type of x, y, z so Min[T]() needs to return the greatest element of T. Likewise, Max[T]() must return the least element of T.

That probably seems academic but consider this innocuous line of code y < Min(xs...) when len(xs) = 0.

This has two consequences. There needs to be some way for these to get the greatest/least element of an arbitrary T which currently cannot be done without reflection and there is no greatest string so these can only be used for numbers.

You could have them panic when they receive an empty slice or make the signature something like Min(x T, xs ...T) T so that it cannot receive 0 values but then you have to do Min(xs[0], xs[1:]...) neither of which are especially ergonomic.

Binary Min/Max is simpler. Per @neild's suggestion, a slices.Min/slices.Max could also be added later once the language has the ability to statically inspect the type argument in some fashion.

@AndrewHarrisSPU
Copy link

AndrewHarrisSPU commented Apr 8, 2023

@fzipp

I'd rather like to see the cmp package name for something like #45200, which is more about equality for testing. I don't know if Ordered/Min/Max would fit into such a package.

There is some implicit conventional usage of cmp as an identifier for variables and functions in the standard library, for a function of two args returning -1/0/1, or the result of such a function. cmp is used as a parameter name for this style of function in sort.Find, slices.BinarySearchFunc, and slices.CompareFunc. Another abbrv. would be ord.

edit: From the example of slices.BinarySearchFunc, ord.Cmp[E,T] func(E,T) int seems like a fit as a component of algorithms that really need a cmp; BinarySearchFunc seems like evidence that these algos exist and should be written in this style in Go. An ord.Min or ord.Max employ the builtin definition of < ... I'm not sure there's much use for constraints like ord.Total, ord.Partial, ord.Numeric but they at least read naturally to me.

@earthboundkid
Copy link
Contributor

I like ord, but it should be ord.Compare (not Cmp) to match strings.Compare and math.Compare.

@zigo101
Copy link

zigo101 commented Apr 9, 2023

If Go will supported some ordered types which are hard to be described in type constraints, then it would better to add a builtin ordered type IMO.

@ianlancetaylor
Copy link
Contributor Author

@go101 Yes, if Go ever supports ordered struct or array types, then it will be necessary to do something like define ordered as a predeclared constraint, similar to comparable. But there is no particular reason to think that that will happen. If it does happen, we can always write type Ordered ordered and existing programs will continue to work.

@ianlancetaylor
Copy link
Contributor Author

I'm not personally excited about a package name "ord", but I could see order.Ordered, order.Min, order.Max. I do tend to think that "sort" or "cmp" would be preferable, though. Unfortunate that there is already a popular package named "cmp" (of course it's not impossible to have two packages named "cmp", it's just unfortunate).

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/498515 mentions this issue: gopls/internal/lsp: add min/max builtin

gopherbot pushed a commit to golang/tools that referenced this issue May 30, 2023
For golang/go#59488

Change-Id: I43d9a5b644a9c3ce647a11f9e2b647093b070c9f
Reviewed-on: https://go-review.googlesource.com/c/tools/+/498515
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
gopherbot pushed a commit that referenced this issue Jun 4, 2023
Updates #59488

Change-Id: If873b81fb7f0e28b84a3e5c2ff89426b3e289d5d
Reviewed-on: https://go-review.googlesource.com/c/go/+/498495
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
gopherbot pushed a commit to golang/tools that referenced this issue Jun 5, 2023
For golang/go#59488

Change-Id: I93680138c90750454b4d94af6dc84fe942c9dd34
Reviewed-on: https://go-review.googlesource.com/c/tools/+/498516
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Robert Findley <rfindley@google.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/501355 mentions this issue: math: document that Min/Max differ from min/max

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/501697 mentions this issue: doc/go1.21: mention new cmp package

gopherbot pushed a commit that referenced this issue Jun 8, 2023
For #59488

Change-Id: I73ee4d1d8b9d8e6f0aad9e3bb98729aaa0f06a47
Reviewed-on: https://go-review.googlesource.com/c/go/+/501697
TryBot-Bypass: Ian Lance Taylor <iant@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/501825 mentions this issue: doc/go1.21: add heading for cmp package

gopherbot pushed a commit that referenced this issue Jun 11, 2023
For #59488.
For #58645.

Change-Id: Ia9b76d49825dd74f7e52d829ec6d47e6c2addd76
Reviewed-on: https://go-review.googlesource.com/c/go/+/501825
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Auto-Submit: Dmitri Shuralyov <dmitshur@golang.org>
TryBot-Bypass: Dmitri Shuralyov <dmitshur@google.com>
gopherbot pushed a commit that referenced this issue Jun 15, 2023
For #59488
Fixes #60616

Change-Id: Idf9f42d7d868999664652dd7b478684a474f1d96
Reviewed-on: https://go-review.googlesource.com/c/go/+/501355
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Rob Pike <r@golang.org>
Run-TryBot: Ian Lance Taylor <iant@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
@philpennock
Copy link

Double-check something: @rsc wrote:

The proposal in this issue, then, is:

  1. Add min and max as builtins to the spec and compiler. They accept 1 or more arguments of a uniform ordered type T and return type T (min(x,y,z) has same type as x+y+z). The leftmost minimum/maximum or NaN value in the argument list (leftmost is only an observable part of the definition for floats and strings).

In testing this out with the Go playground with gotip, min() seems to be returning the rightmost NaN, not the leftmost. I tested by using math.Float64frombits(...) to create multiple distinct NaNs.

https://go.dev/play/p/v-F_sKZp62W?v=gotip

Was this a deliberate change in behavior, or is it a mistake to be fixed before 1.21 final?

@ianlancetaylor
Copy link
Contributor Author

@philpennock It was a deliberate change based on further consideration of implementation considerations. See #59488 (comment) . We decided that if any argument is a NaN, the result would be a NaN, but we aren't specifying the exact NaN value. This seems consistent with operations like addition of two NaN values.

@philpennock
Copy link

Ah, sorry, it wasn't clear that was changing the proposed contract of returning the earliest, but looking now, I see that reading in there. Thank you.

@ianlancetaylor
Copy link
Contributor Author

It was a good question, we kind of skated over that during the implementation. At least I think the docs are correct.

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/514596 mentions this issue: cmd/compile: implement float min/max in hardware for amd64 and arm64

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/514775 mentions this issue: cmd/compile: implement float min/max in hardware for riscv64

gopherbot pushed a commit that referenced this issue Aug 1, 2023
Update #59488

Change-Id: I89f5ea494cbcc887f6fae8560e57bcbd8749be86
Reviewed-on: https://go-review.googlesource.com/c/go/+/514596
Reviewed-by: Keith Randall <khr@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
gopherbot pushed a commit that referenced this issue Jan 26, 2024
CL 514596 adds float min/max for amd64, this CL adds it for riscv64.

The behavior of the RISC-V FMIN/FMAX instructions almost match Go's
requirements.

However according to RISCV spec 8.3 "NaN Generation and Propagation"
>> if at least one input is a signaling NaN, or if both inputs are quiet
>> NaNs, the result is the canonical NaN. If one operand is a quiet NaN
>> and the other is not a NaN, the result is the non-NaN operand.

Go using quiet NaN as NaN and according to Go spec
>> if any argument is a NaN, the result is a NaN

This requires the float min/max implementation to check whether one
of operand is qNaN before float mix/max actually execute.

This CL also fix a typo in minmax test.

Benchmark on Visionfive2
goos: linux
goarch: riscv64
pkg: runtime
         │ float_minmax.old.bench │       float_minmax.new.bench        │
         │         sec/op         │   sec/op     vs base                │
MinFloat             158.20n ± 0%   28.13n ± 0%  -82.22% (p=0.000 n=10)
MaxFloat             158.10n ± 0%   28.12n ± 0%  -82.21% (p=0.000 n=10)
geomean               158.1n        28.12n       -82.22%

Update #59488

Change-Id: Iab48be6d32b8882044fb8c821438ca8840e5493d
Reviewed-on: https://go-review.googlesource.com/c/go/+/514775
Reviewed-by: Mauri de Souza Meneguzzo <mauri870@gmail.com>
Run-TryBot: M Zhuo <mengzhuo1203@gmail.com>
Reviewed-by: Joel Sing <joel@sing.id.au>
Reviewed-by: Cherry Mui <cherryyz@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
ezz-no pushed a commit to ezz-no/go-ezzno that referenced this issue Feb 18, 2024
CL 514596 adds float min/max for amd64, this CL adds it for riscv64.

The behavior of the RISC-V FMIN/FMAX instructions almost match Go's
requirements.

However according to RISCV spec 8.3 "NaN Generation and Propagation"
>> if at least one input is a signaling NaN, or if both inputs are quiet
>> NaNs, the result is the canonical NaN. If one operand is a quiet NaN
>> and the other is not a NaN, the result is the non-NaN operand.

Go using quiet NaN as NaN and according to Go spec
>> if any argument is a NaN, the result is a NaN

This requires the float min/max implementation to check whether one
of operand is qNaN before float mix/max actually execute.

This CL also fix a typo in minmax test.

Benchmark on Visionfive2
goos: linux
goarch: riscv64
pkg: runtime
         │ float_minmax.old.bench │       float_minmax.new.bench        │
         │         sec/op         │   sec/op     vs base                │
MinFloat             158.20n ± 0%   28.13n ± 0%  -82.22% (p=0.000 n=10)
MaxFloat             158.10n ± 0%   28.12n ± 0%  -82.21% (p=0.000 n=10)
geomean               158.1n        28.12n       -82.22%

Update golang#59488

Change-Id: Iab48be6d32b8882044fb8c821438ca8840e5493d
Reviewed-on: https://go-review.googlesource.com/c/go/+/514775
Reviewed-by: Mauri de Souza Meneguzzo <mauri870@gmail.com>
Run-TryBot: M Zhuo <mengzhuo1203@gmail.com>
Reviewed-by: Joel Sing <joel@sing.id.au>
Reviewed-by: Cherry Mui <cherryyz@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests