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

sort: Float64Slice.Less does not treat -0 as less than +0 #33440

Open
dsnet opened this issue Aug 2, 2019 · 12 comments
Open

sort: Float64Slice.Less does not treat -0 as less than +0 #33440

dsnet opened this issue Aug 2, 2019 · 12 comments
Labels

Comments

@dsnet
Copy link
Member

@dsnet dsnet commented Aug 2, 2019

Using Go1.12

Consider this snippet:

fs := []float64{math.Copysign(0, +1), math.Copysign(0, -1)}
sort.Stable(sort.Float64Slice(fs))
fmt.Println(fs)

This currently prints:

[0 -0]

I expected this to print:

[-0 0]

Either this case be documented or we fix the Float64Slice.Less method.

@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 2, 2019

but -0 < 0 is false is Go. Even if you make a -0 correctly like this: 1/math.Inf(-1) < 0.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Aug 2, 2019

It's entirely reasonable to keep the current behavior, but I should note that the current implementation treats NaN as less than all other numbers even though math.NaN() < 0 is false in Go.

It seems odd to me that the current implementation special cases one edge case of floating points and not another.

@cespare
Copy link
Contributor

@cespare cespare commented Aug 2, 2019

the current implementation treats NaN as less than all other numbers even though math.NaN() < 0 is false in Go.

But that is documented in the sort package.

You have to decide how to handle NaNs one way or the other for sorting, whereas for -0 (and -Inf and +Inf) there is a natural ordering that is part of IEEE floating point and implemented by <.

@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 2, 2019

If we really wanted to make Float64Slice.Sort fully specified we'd need to define the ordering of -0/+0 as well as the ordering among NaNs.

Do we want that? Keep in mind you can always use sort.Stable to get output that does not depend on the implementation.

(Aside: Sort and Stable probably still produce implementation-defined results when the comparison function isn't transitive. That's not what is happening for floats, although it is certainly in weird territory near there.)

@smasher164
Copy link
Member

@smasher164 smasher164 commented Aug 2, 2019

Note that IEEE-754 defines a total-ordering predicate (5.10), but I do not know of any sorting library or hardware that implements it. Although it can be severely optimized, here it is for reference:

// TotalOrder(p[i], p[j])
func (p Float64Slice) Less(i, j int) bool {
	switch x, y := p[i], p[j]; {
	case x < y:
		return true
	case x == y:
		return signbit(x) || !signbit(y)
	case signbit(x) && isNaN(x) || !signbit(y) && isNaN(y):
		return true
	case isNaN(x) && isNaN(y):
		bx, by := float64bits(x), float64bits(y)
		switch {
		case signbit(x) != signbit(y):
			return signbit(x)
		case signbit(x):
			if bx != by {
				return bx == qnan && y != qnan
			}
			return bx > by
		default:
			if bx != by {
				return bx != qnan && y == qnan
			}
			return bx < by
		}
	}
	return false
}

A playground link: https://play.golang.org/p/NsdlMHGI2A5

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Aug 2, 2019

Thanks. I can definitely see an argument for using that ordering for sort.Float64Slice.

@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 2, 2019

Using something standard would be nice.
Unfortunately, it sorts all -NaN first and all +NaN last, which is different from how Float64Slice is currently spec'd. That makes it hard to adopt without breaking backwards compatibility.

The spec also says (5.10.d.3.iii) ...otherwise, the order of NaNs is implementation-defined.. So even the spec order isn't totally defined (for NaNs which are both signaling or both quiet).

@smasher164
Copy link
Member

@smasher164 smasher164 commented Aug 2, 2019

The spec also says (5.10.d.3.iii) ...otherwise, the order of NaNs is implementation-defined.. So even the spec order isn't totally defined (for NaNs which are both signaling or both quiet).

I think the final revision of the spec (https://ieeexplore.ieee.org/document/4610935) says in 5.10.d.3.iii: lesser payload, when regarded as an integer, orders below greater payload for +NaN, reverse for −NaN..

I wonder how big the breakage would be if the NaN ordering was changed. How often do people sort NaNs?

@smasher164
Copy link
Member

@smasher164 smasher164 commented Aug 2, 2019

Also it seems that IEEE defined total order this way for easy implementation, as explained here: rust-lang/rust#53938. This lets one implement this operation as a comparison of two's complement integers: https://play.golang.org/p/TsOGodZlBd-.

func (p Float64Slice) Less(i, j int) bool {
	x := int64(math.Float64bits(p[i]))
	y := int64(math.Float64bits(p[j]))
	x ^= int64(uint64(x>>63) >> 1)
	y ^= int64(uint64(y>>63) >> 1)
	return x < y
}
@randall77
Copy link
Contributor

@randall77 randall77 commented Aug 3, 2019

I wonder how big the breakage would be if the NaN ordering was changed. How often do people sort NaNs?

Probably not very often. But that cuts both ways - why would it be worth a backwards-incompatible change for a feature that is seldom used?

@smasher164
Copy link
Member

@smasher164 smasher164 commented Aug 3, 2019

why would it be worth a backwards-incompatible change for a feature that is seldom used?

It's probably not worth it, considering that this behavior was introduced just before the 1.0 release( https://golang.org/cl/4805051). Although, maybe it's worth adding a func TotalOrder(float64, float64) bool to the math package for people who want strict ordering.

We also have the option of adopting only part of the standard's total-ordering predicate, while remaining backwards-compatible. For instance, if we only wanted to specify the -0/+0 behavior, we could just adopt 5.10.c, i.e. (p[i] == p[j] && (signbit(p[i]) || !signbit(p[j]))). If we also cared about specifying the internal ordering of NaNs, affected by their specific bit patterns (signalling and quiet), we could extend the current behavior to be

  1. NaN < any other value
  2. 5.10.d.3 a.k.a if isNaN(p[i]) && isNaN(p[j])
    i) negative sign orders below positive sign
    ii) signaling orders below quiet for +NaN, reverse for −NaN
    iii) lesser payload, when regarded as an integer, orders below greater payload for +NaN, reverse for −NaN.

However, I think that the NaN ordering should not change, since Go's floating-point operations don't produce signalling NaNs in the first place, and sNaNs will only come from external sources.

@smasher164
Copy link
Member

@smasher164 smasher164 commented Oct 24, 2019

Making any change here will require introducing an import to the sort package, either math or unsafe. This is because the uint64 representation of a float64 is needed, at the minimum to retrieve the sign bit.

That being said, because signed zero is not exposed at the language level, I think it is best to document that Float64Slice does not sort -0 before +0. Zeroes are grouped together, similar to how NaNs are.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
You can’t perform that action at this time.