math: add Compare and Compare32

[zhangyunhao116]

The slices.Sort doesn't support sorting slices of floating-point numbers containing Not-a-number (NaN) values, It's not very intuitive.

Once the slices package is merged into stdlib, the sort.{TYPE}s(e.g. sort.Ints, sort.Float64s) APIs may be semi-deprecated. But the slices package doesn't provide a simple way to sort slices of floats containing NaNs, it recommends using slices.SortFunc(x, func(a, b float64) bool {return a < b || (math.IsNaN(a) && !math.IsNaN(b))}), this function is very complex compared to using sort.Float64s.

Related CL: https://go-review.googlesource.com/c/exp/+/446155

[gopherbot]

Change https://go.dev/cl/446155 mentions this issue: slices: Sort support sorting slices of floating-point numbers containing NaN values

[dsnet]

This is related to #33440. @smasher164 mentions the existence of a total-ordering predicate that could be used to sort floats with NaNs.

[ianlancetaylor]

CC @eliben @randall77

[randall77]

Once the slices package is merged into stdlib, the sort.{TYPE}s(e.g. sort.Ints, sort.Float64s) APIs may be semi-deprecated.

I don't think they will, using sort.Float64s will be fine forever.

I think the only advantage of slices.Sort is that it will work on slices of named float64s (e.g. type F float64; a := []F{5,4,3}; slices.Sort(a), that won't work using sort.Float64s). And in that rare case one can use the described workaround.

[zhangyunhao116]

Since Go1.18 is released, many users use the slices.Sort to replace sort.{TYPE}s, because the former is faster and more clear in almost all cases. From the point of view of the users, the former looks more like a replacement of the latter, they have almost the same function in fact except the slices.Sort doesn't support sorting slices containing NaNs.

The main concern is that users don't notice this special case, and the replacement may break their codes.

[earthboundkid]

I think it's worth adding documentation to slices.Sort that sorting a float won't work. Maybe also there could be a comparator function in sort.

[eliben]

I think it's worth adding documentation to slices.Sort that sorting a float won't work. Maybe also there could be a comparator function in sort.

The documentation for Sort is currently:

Sort sorts a slice of any ordered type in ascending order. Sort may fail to sort correctly when sorting slices of floating-point numbers containing Not-a-number (NaN) values. Use slices.SortFunc(x, func(a, b float64) bool {return a < b || (math.IsNaN(a) && !math.IsNaN(b))}) instead if the input may contain NaNs.

Is this not sufficient documentation, @carlmjohnson ?

[eliben]

@zhangyunhao116 I'm not a big fan of this proposal at this time. The problem with sorting floats is clearly documented and a workaround is provided. It's easy to sort using SortFunc

[earthboundkid]

That seems good to me.

In #50340 I think there was talk about adding sort.Compare which would take a comparable and return -1, 0, 1. If something like that is ever added there should also be CompareFloat, but it's not necessary on its own.

[zhangyunhao116]

The problem with sorting floats is clearly documented and a workaround is provided. It's easy to sort using SortFunc

Agree that the special case is clearly documented and has a workaround, but it's nice to support all the special cases as sort.{TYPE}s does :)

I did a simple poll about slices.Sort at my work. The question is

The slices.Sort sorts a slice of any ordered type in ascending order. Intuitively, you think the function is

A. A replacement of sort.{TYPE}s APIs, has the same output, and support all special cases.
B. slices.Sort and sort.{TYPE}s APIs exist side by side, and they may have different outputs in special cases.

51 people joined it, 82.4% (42) selected A, and 17.6% (9) selected B. Looks like many users of this API doesn't notice the special case.

[zhangyunhao116]

The proposal still need more discussions, it's a rare case, and It's merely not as users intuitively expected. The slices.Sort work very well for all the general cases.

[rsc]

Special casing the generic type being float64 would solve sorting []float64, but it wouldn't solve sorting []struct {x float64}.

I don't see how we can special case this reasonably. Callers should not sort slices with NaNs in them.

[dsnet]

What if instead, we provided a function in the math package like:

package math

// FloatCompare compares x to y according to the
// total-ordering predicate in IEEE-754, section 5.10.
// The result will be 0 if a == b, -1 if a < b, and +1 if a > b.
func FloatCompare[F constraints.Float](a, b F) int

// FloatLess reports whether a is less than b according to the
// total-ordering predicate in IEEE-754, section 5.10.
func FloatLess[F constraints.Float](a, b F) bool {
    return FloatCompare(a, b) < 0
}

Thus, usage with the slices package can be something like:

var fs []MyFloat32
slices.SortFunc(fs, math.FloatLess[MyFloat32])

This would solve both the NaN issue from this issue and the -0 vs +0 issue from #33440.

More complicated composite cases like #56491 (comment) can be handled by passing a user-defined less function to slices.SortFunc that's implemented in terms of math.FloatLess.

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[earthboundkid]

What if instead, we provided a function in the math package like:

Should FloatCompare go in math or sort? I can see the case for either.

ISTM, if we have that we should have Compare[Int ~int|~uint|etc](a, b N) int in the same package too.

[dsnet]

My argument for it being in "math" is:

1. The other scalar kinds (int, uint) don't really have ambiguous definitions of ordering (i.e., the < operator does exactly what you want). It's only really float that is special.

2. The "math" package seems to already have special handling for IEEE-754. I proposed the names with a Float prefix to match the existing FloatXXbits and FloatXXfrombits functions that are IEEE-754 specific. There are other IEEE-754 specific functions like IsNaN and NaN.

3. I don't think a predicate for ordering is sufficient justification for it being "sort". For example, should we have moved

   • bytes.Compare to be sort.BytesCompare, or
   • netip.Addr.Compare to be sort.AddrCompare, or
   • time.Time.Compare to be sort.TimeCompare?

   Functionality for order should live with other functionality for the type (i.e.,
   "math" for floats,
   "bytes" for []byte,
   "strings" for strings,
   "netip" for netip.Addr,
   "time" for time.Time,
   etc.).

[earthboundkid]

That makes sense to me. My only other thought is that math.Compare(a, b float64) int would also make sense since all the functions in math take float64.

[smasher164]

What if instead, we provided a function in the math package like:

This total-ordering predicate would be pretty simple to define as well, since it's just:

func sign(a, b int64) int {
	if a < b {
		return -1
	}
	if a > b {
		return 1
	}
	return 0
}

func FloatCompare[F constraints.Float](a, b F) int {
	x := int64(Float64bits(float64(a)))
	y := int64(Float64bits(float64(b)))
	x ^= int64(uint64(x>>63) >> 1)
	y ^= int64(uint64(y>>63) >> 1)
	return sign(x, y)
}

The only thing I'd point out is this ordering of NaNs is different from the way sort.Float64s does it. The total ordering predicate sorts -NaN < everything else < +NaN, while sort.Float64s does (+-)NaN < everything.

[rsc]

The special case in sort seems like a clear decline since it can't be done generally.
Retitling to be about this math.FloatCompare that might be helpful for people writing their own.

[rsc]

I feel slightly better about this because it is defined by IEEE-754 and we are not making it up.
That said, it still seems very niche.
The definition is in https://irem.univ-reunion.fr/IMG/pdf/ieee-754-2008.pdf on page 40.

I don't think we should make this function the first generic one in math.
It should probably just be func Compare(x, y float64) int.

[dsnet]

My reason for proposing a generic version was because you can't roundtrip convert a float32->float64->float32 and preserve the exact bits for NaNs. A single bit is mangled in the float32->float64 conversion.

See this example: https://go.dev/play/p/sPn-yfpd-nK, where one of the bits gets mangled on my Ryzen 5900x. I don't know if this a Go-specific issue or a x86 issue.

This means that:

var x, y float32 = ...
Compare(float64(x), float64(y))

wouldn't be quite correct for NaNs. Arguably this case is esoteric, but Compare is already esoteric, so the people who use it probably care about correctness in the esoteric cases.

Options:

• Accept this oddity and just provide the float64-only API.
• Fix the float32->float64 conversion issue in the compiler (if possible?)
• Provide both Compare32 and Compare64 or something.

I don't have a strong preference.

[earthboundkid]

My feeling is to just provide the float64 API under the name math.Compare, and wait until math/v2 to provide a generic version along with generic everything else.

[randall77]

See this example: https://go.dev/play/p/sPn-yfpd-nK, where one of the bits gets mangled on my Ryzen 5900x. I don't know if this a Go-specific issue or a x86 issue.

This is squashing a signaling NaN to a quiet NaN. I believe all platforms do this on a float32->float64->float32 conversion. (Joe and I have been through this ugliness before, e.g., #27193 and #36400.)

I'd be ok with a Compare and Compare32. (Following the lead of Nextafter and Nextafter32.)

[smasher164]

Writing this function generically without converting to float64 first would require the ability to either call Float32bits or Float64bits depending on the type of the argument, which doesn't seem possible without converting to interface{} and type-asserting. I think either Compare32/Compare64 or Compare(x, y float64) is fine.

Edit: I forgot that you can use unsafe and get the float value's size.

func sign[I constraints.Signed](a, b I) int {
	if a < b {
		return -1
	}
	if a > b {
		return 1
	}
	return 0
}

func FloatCompare[F constraints.Float](a, b F) int {
	if unsafe.Sizeof(a) == 4 {
		x := int32(math.Float32bits(float32(a)))
		y := int32(math.Float32bits(float32(b)))
		x ^= int32(uint32(x>>31) >> 1)
		y ^= int32(uint32(y>>31) >> 1)
		return sign(x, y)
	} else {
		x := int64(math.Float64bits(float64(a)))
		y := int64(math.Float64bits(float64(b)))
		x ^= int64(uint64(x>>63) >> 1)
		y ^= int64(uint64(y>>63) >> 1)
		return sign(x, y)
	}
}

[xen0n]

@xen0n What do you think about setting the is_signaling bit when not on NAN2008? So on mips,

if IsNaN(a) && !NAN2008 {
    // set the is_signaling to 1
}
if IsNaN(b) && !NAN2008 {
    // set the is_signaling to 1
}
// do comparison as normal

The problem is there's currently no trivial/cheap way to derive the NAN2008 value in your sketched-up code. Either perform some non-trivial dance to grab it from the ELF header (which is not suitable for math; perhaps runtime would be better if we must probe at run-time) and cache the result; or better yet, figure out the target NaN flavor at compile-time and select appropriate code, but "MIPS NaN flavor" isn't something currently expressible via go:build constraints.

Plus the "fix" in your approach would probably more resemble this:

if !NAN2008 {
    if IsNaN(a) {
        flip signalling bit of a
    }
    if IsNaN(b) {
        flip signalling bit of b
    }
} 
compare as if on nan2008

[smasher164]

Right, as you posted that comment, I noticed that debug/elf doesn't expose the EF_ flags.
Ideally the runtime would check this on startup and store it in internal/cpu, so the math library can just check that field.
Edit: /cc @randall77 since he looked at this problem in #37455

[ianlancetaylor]

I suggest that we write special case code if runtime.GOARCH == "mips" for comparing Inf and NaN. The behavior of math.Compare should not vary based on ELF flags. (Maybe the behavior of math.NaN should vary, but not math.Compare).

[ianlancetaylor]

Reopening because the CL was rolled back.

[smasher164]

Maybe the behavior of math.NaN should vary, but not math.Compare

If we fix math.NaN() for MIPS, does that guarantee that NaNs that are the result of some FPU computation will remain the same?

Maybe Compare doesn't need to know about the ELF flag. If the inputs are NaNs and the platform is MIPS, then it can set the signaling bit no matter what.

[ianlancetaylor]

Looking a bit more I'm not even sure that there is any problem with Compare. I think the problem may only have been with the test. The test expected NaN to return a non-signalling NaN value. Maybe we just need to tweak the test.

[smasher164]

I was trying to replicate the issue by manually toggling the quiet bit, and I was still getting the correct answer.

(Sidenote: there are two quiet nan values from https://github.com/golang/go/blob/master/src/cmd/compile/internal/test/float_test.go 0x8fc00000 and 0x8fffffff that I thought were failing my test, but I think they're actually just invalid quiet NaN values)

The test expected NaN to return a non-signalling NaN value.

Doesn't NaN() just bitcast 0x7FF8000000000001 and return it up? How could it return a signaling value?

[ianlancetaylor]

Hmmm, you're right. Both the constants and the Compare function are all done using only bits. Now I really don't understand what is going wrong on MIPS.

The error messages in the test log are

    all_test.go:2296: Compare(NaN, -Inf) = 1, want -1
    all_test.go:2296: Compare(-Inf, NaN) = -1, want 1
    all_test.go:2302: Compare32(NaN, -Inf) = 1, want -1
    all_test.go:2302: Compare32(-Inf, NaN) = -1, want 1

That is interesting because the test actually never compares positive NaN with negative infinity. The outputs of Compare are correct for the values that are being printed. From looking at the test, it appears that -NaN() on MIPS returns a positive NaN, whereas on other systems it returns a negative NaN. Looking at the generated code, it seems that on both amd64 and mips64le the code works by loading the constant 0x7ff8000000000001 and then negating it. On amd64 the negation is done by doing an xor with 0x8000000000000000. On mips64le it's done using the NEGD instruction, which in the MIPS world is known as neg.d.

According Richard Sandiford at https://gcc.gnu.org/pipermail/gcc-patches/2006-September/199974.html the MIPS neg.d instruction does not actually change the sign bit of a NaN. Fortunately Godbolt lets us see what GCC generates when negating a float64 in C. It does not use neg.d, but instead does an xor with the sign bit.

So I think that this could be described as a bug in the MIPS support in the Go compiler.

[ianlancetaylor]

I filed #58466 for the compiler bug. If that gets resolved as I expect, then we can return to CL 459435.

[smasher164]

As a workaround, in case we decide not to change negate's behavior, I can update the test to take the bit-exact representation of -NaN.

[gopherbot]

Change https://go.dev/cl/467515 mentions this issue: math: add Compare and Compare32

[smasher164]

Sent a second CL with the same change, but updated the tests. @xen0n are you able to verify that these tests pass on MIPS?

[earthboundkid]

#58468

[gopherbot]

Change https://go.dev/cl/498776 mentions this issue: doc/go1.21: mention math.Compare and Compare32

[ianlancetaylor]

Issue #60519 suggests removing math.Compare and math.Compare32 in favor of cmp.Compare. This would effectively decline this proposal (though it could be reopened for a later release if that seems desirable).

[gopherbot]

Change https://go.dev/cl/499416 mentions this issue: Revert "math: add Compare and Compare32"