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 · 14 comments
Open

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

dsnet opened this issue Aug 2, 2019 · 14 comments
Labels
NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Milestone

Comments

@dsnet
Copy link
Member

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

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

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

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

@randall77
Copy link
Contributor

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

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

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

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

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.

@katiehockman katiehockman added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label Aug 5, 2019
@smasher164
Copy link
Member

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.

@nsajko
Copy link
Contributor

nsajko commented Nov 14, 2020

@smasher164 What do you mean by "signed zero is not exposed at the language level"? I think that's false, considering that Go follows IEEE 754 and that Go behaves like this (it is easy to make and use a signed zero value): https://play.golang.org/p/h7LnQtFSDaL

Regarding the main topic of this issue (whether negative zero should be considered to be less than positive zero when sorting), I suspect the answer is yes, and futhermore that this is more important than NaN sort order. The reason is that signed zero matters when computing some mathematical functions, and as such could conceivably break someone's numeric work; while, on the other hand, a NaN only produces NaNs anyway, it's payload is usually unused, and when it is used it's probably used for debugging so the sort order wouldn't matter probably anyway.

@smasher164
Copy link
Member

smasher164 commented Nov 14, 2020

@smasher164 What do you mean by "signed zero is not exposed at the language level"? I think that's false, considering that Go follows IEEE 754 and that Go behaves like this (it is easy to make and use a signed zero value): https://play.golang.org/p/h7LnQtFSDaL

You're right. I forgot the case that a float variable containing 0.0 is negated.

Also, regarding my previous comment about introducing an import, I think that's obviated by the recent trend of using internal packages to break import dependency rules. In fact, I would argue that this would've been already if it weren't for the fact that internal packages didn't exist at the time of Go 1.1 when isNaN was duplicated in the sort package so that it wouldn't depend on math. We could probably add an internal/float package that defines float<->uint conversions. This would permit us to go in whatever direction we wanted.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Projects
None yet
Development

No branches or pull requests

8 participants