code review 4805051: sort: fixed bug in (Float64Slice) Less; NaN less than a...

sort: fixed bug in (Float64Slice) Less; NaN less than anything else

Previously comparisons with NaN led to contradictory results if it was
compared to anything not NaN, since Less always returned false, thus
breaking monotonicity of ordering.
This fix makes NaN less than anything else and adds NaN and (+-)Inf to
testcases.

Fixes issue 2092.

[Florian Uekermann, 2011-07-22 21:43:19]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[Florian Uekermann, 2011-07-22 22:34:51]

For some reason gotest now fails to start the tests for the sort package with
the error below. I have no idea what I did wrong since everything compiles
nicely and the my testprograms work fine. Reverting the changes in the files I
edited also doesn't fix things. I sent the CL anyway since I am stuck here, I
don't know how to debug this, I am not even sure if something wrong with the CL
or if I broke something else... ...I am bit confused.

florian@FlorianLaptop:~/goupstream/go/src/pkg/sort$ gotest
rm -f _test/sort.a
rm -f _test/sort.a
gopack grc _test/sort.a _gotest_.6 
throw: recursive call during initialization - linker skew

runtime.throw+0x40 /home/florian/goupstream/go/src/pkg/runtime/runtime.c:102
	runtime.throw(0x508ab5, 0x7f7e00000010)
runtime.throwinit+0x25 /home/florian/goupstream/go/src/pkg/runtime/runtime.c:93
	runtime.throwinit()
testing.init+0x36 /home/florian/goupstream/go/src/pkg/testing/testing.go:298
	testing.init()
sort.init+0x52 /home/florian/goupstream/go/src/pkg/sort/search_test.go:15
	sort.init()
path/filepath.init+0x57
/home/florian/goupstream/go/src/pkg/path/filepath/path_unix.go:23
	path/filepath.init()
io/ioutil.init+0x48 /home/florian/goupstream/go/src/pkg/io/ioutil/tempfile.go:91
	io/ioutil.init()
time.init+0x43 /home/florian/goupstream/go/src/pkg/time/zoneinfo_unix.go:213
	time.init()
testing.init+0x52 /home/florian/goupstream/go/src/pkg/testing/testing.go:298
	testing.init()
main.init+0x4d /home/florian/goupstream/go/src/pkg/sort/_testmain.go:21
	main.init()
runtime.mainstart+0x5 /home/florian/goupstream/go/src/pkg/runtime/amd64/asm.s:76
	runtime.mainstart()
runtime.goexit /home/florian/goupstream/go/src/pkg/runtime/proc.c:244
	runtime.goexit()
----- goroutine created by -----
_rt0_amd64+0xc9 /home/florian/goupstream/go/src/pkg/runtime/amd64/asm.s:65
gotest: "./6.out" failed: exit status 2

[r2, 2011-07-22 22:42:23]

you've added a dependency, which means the problem is likely that you've created
a dependency cycle, probably in the test binary. notice the path

testing
time
io
path
sort
testing

in the trace.

however, i tried adding a math dependency to my test_sort without problems. try
a clean.bash and then all.bash. if you still see this, you have a cycle; if not,
it's "linker skew".

-rob

On 23/07/2011, at 8:34 AM, f1@uekermann-online.de wrote:

> For some reason gotest now fails to start the tests for the sort package
> with the error below. I have no idea what I did wrong since everything
> compiles nicely and the my testprograms work fine. Reverting the changes
> in the files I edited also doesn't fix things. I sent the CL anyway
> since I am stuck here, I don't know how to debug this, I am not even
> sure if something wrong with the CL or if I broke something else... ...I
> am bit confused.
> 
> florian@FlorianLaptop:~/goupstream/go/src/pkg/sort$ gotest
> rm -f _test/sort.a
> rm -f _test/sort.a
> gopack grc _test/sort.a _gotest_.6
> throw: recursive call during initialization - linker skew
> 
> runtime.throw+0x40
> /home/florian/goupstream/go/src/pkg/runtime/runtime.c:102
> 	runtime.throw(0x508ab5, 0x7f7e00000010)
> runtime.throwinit+0x25
> /home/florian/goupstream/go/src/pkg/runtime/runtime.c:93
> 	runtime.throwinit()
> testing.init+0x36
> /home/florian/goupstream/go/src/pkg/testing/testing.go:298
> 	testing.init()
> sort.init+0x52
> /home/florian/goupstream/go/src/pkg/sort/search_test.go:15
> 	sort.init()
> path/filepath.init+0x57
> /home/florian/goupstream/go/src/pkg/path/filepath/path_unix.go:23
> 	path/filepath.init()
> io/ioutil.init+0x48
> /home/florian/goupstream/go/src/pkg/io/ioutil/tempfile.go:91
> 	io/ioutil.init()
> time.init+0x43
> /home/florian/goupstream/go/src/pkg/time/zoneinfo_unix.go:213
> 	time.init()
> testing.init+0x52
> /home/florian/goupstream/go/src/pkg/testing/testing.go:298
> 	testing.init()
> main.init+0x4d /home/florian/goupstream/go/src/pkg/sort/_testmain.go:21
> 	main.init()
> runtime.mainstart+0x5
> /home/florian/goupstream/go/src/pkg/runtime/amd64/asm.s:76
> 	runtime.mainstart()
> runtime.goexit /home/florian/goupstream/go/src/pkg/runtime/proc.c:244
> 	runtime.goexit()
> ----- goroutine created by -----
> _rt0_amd64+0xc9
> /home/florian/goupstream/go/src/pkg/runtime/amd64/asm.s:65
> gotest: "./6.out" failed: exit status 2
> 
> 
> http://codereview.appspot.com/4805051/

[rsc, 2011-07-23 00:43:54]

This is a real, preexisting cycle.
You're just hitting now because the runtime
doesn't catch cycles involving packages
with no init.

I sent out a CL fixing sort and
another CL making the linker find these.
sort is the only one in the tree.

Russ

[Florian Uekermann, 2011-07-23 01:35:37]

Ah I see... ...wrong packagename + no init/missing check.

After pulling the changes everything works fine.

I forgot to check the alphabetical ordering of imports (somehow I feel like I
read somewhere that gofmt learned to do that on its own). Should I just send
another CL that fixes the import ordering or are there comments on this?

On 2011/07/23 00:43:54, rsc wrote:
> This is a real, preexisting cycle.
> You're just hitting now because the runtime
> doesn't catch cycles involving packages
> with no init.
> 
> I sent out a CL fixing sort and
> another CL making the linker find these.
> sort is the only one in the tree.
> 
> Russ

[r, 2011-07-23 01:41:42]

http://codereview.appspot.com/4805051/diff/3001/src/pkg/sort/sort.go
File src/pkg/sort/sort.go (right):

http://codereview.appspot.com/4805051/diff/3001/src/pkg/sort/sort.go#newcode9
src/pkg/sort/sort.go:9: import "math"
dependency cycles aside, it's kind of a shame to add an import to a package that
was once a leaf. is there a clean yet efficient way to avoid that?

i think you can do something like

if a < b return true
if b < a return false

then do the a < a check for NaN

i hate NaNs with a deep-seated passion.

[rsc, 2011-07-23 01:49:52]

> dependency cycles aside, it's kind of a shame to add an import to a
> package that was once a leaf. is there a clean yet efficient way to
> avoid that?
>
> i think you can do something like
>
> if a < b return true
> if b < a return false
>
> then do the a < a check for NaN
>
> i hate NaNs with a deep-seated passion.

I'd prefer to see IsNaN in the code to make it clearer.
math is a leaf too, and once inlining works you won't
even see a reference to math in the generated code.
So the import is not a problem.

[r2, 2011-07-23 01:57:43]

i give up. leaving for rsc.

-rob

[Florian Uekermann, 2011-07-23 02:22:34]

http://codereview.appspot.com/4805051/diff/3001/src/pkg/sort/sort.go
File src/pkg/sort/sort.go (right):

http://codereview.appspot.com/4805051/diff/3001/src/pkg/sort/sort.go#newcode9
src/pkg/sort/sort.go:9: import "math"
the current logic is better :
1 comparison for normal true without NaN
2 comparisons for normal false
2 comparisons for false with NaN as second value
3 comparisons for anything with NaN as first value

(imho) your suggestion would result in:
1 comparison for normal true without NaN
2 comparisons for normal false without NaN (<= instead of <)
3 comparisons for true with NaN as first value
4 comparisons for NaN as second (true) or NaN for both (false)

Probably made a mistake or two in the listing above, but I think the idea is
clear, the current code is easier and faster.

But getting rid of the math dependency is easy anyway, I could manually inline
IsNan (a!=a), but I guess the compiler will learn that as well at some point.

I don't like it, because the code is easier to read with IsNaN and math doesn't
add dependencies anyway (it only depends on unsafe), so there is no real
benefit.
But I don't care much, I made my point, now you choose what you would like to
have :).

[r2, 2011-07-23 02:22:48]

maybe not.

isn't it worth doing the other comparison (b < a after a < b) before calling out
to a function, inlined or not?

-rob

[rsc, 2011-07-23 02:28:00]

what about

a < b || !(b >= a)

with a good comment?
that's worst case 2 all the time
and might even work.

[Florian Uekermann, 2011-07-23 02:28:07]

its not much of a function its just a!=a, thats it, just one comparison

[r2, 2011-07-23 02:30:19]

On 23/07/2011, at 12:27 PM, Russ Cox wrote:

> what about
> 
> a < b || !(b >= a)
> 
> with a good comment?
> that's worst case 2 all the time
> and might even work.

that's what i'm trying to say, unsuccessfully.

-rob

[Florian Uekermann, 2011-07-23 02:36:39]

isn't that true for two NaNs?

On 2011/07/23 02:30:19, r2 wrote:
> On 23/07/2011, at 12:27 PM, Russ Cox wrote:
> 
> > what about
> > 
> > a < b || !(b >= a)
> > 
> > with a good comment?
> > that's worst case 2 all the time
> > and might even work.
> 
> that's what i'm trying to say, unsuccessfully.
> 
> -rob
>

[r2, 2011-07-23 02:44:55]

On 23/07/2011, at 12:36 PM, f1@uekermann-online.de wrote:

> isn't that true for two NaNs?

sigh, yes.

package main

import "fmt"
import "math"

func main() {
	a := math.NaN()
	b := math.NaN()
	fmt.Println(a < b, !(b >= a), a < b || !(b >= a))
}

false true true

[Florian Uekermann, 2011-07-23 02:50:27]

So we agree that its wrong for Less?

On 2011/07/23 02:44:55, r2 wrote:
> On 23/07/2011, at 12:36 PM, mailto:f1@uekermann-online.de wrote:
> 
> > isn't that true for two NaNs?
> 
> sigh, yes.
> 
> package main
> 
> import "fmt"
> import "math"
> 
> func main() {
> 	a := math.NaN()
> 	b := math.NaN()
> 	fmt.Println(a < b, !(b >= a), a < b || !(b >= a))
> }
> 
> false true true
>

[rsc, 2011-07-23 02:57:18]

On Fri, Jul 22, 2011 at 22:50,  <f1@uekermann-online.de> wrote:
> So we agree that its wrong for Less?

it's wrong but i don't think it's wrong enough to break sort.

[Florian Uekermann, 2011-07-23 03:05:18]

On 2011/07/23 02:57:18, rsc wrote:
> On Fri, Jul 22, 2011 at 22:50,  <mailto:f1@uekermann-online.de> wrote:
> > So we agree that its wrong for Less?
> 
> it's wrong but i don't think it's wrong enough to break sort.

If you only consider the current implementation inside the package yes, but its
a public function for a public interface... ...i thought of something similar
before I sent the CL, but I feared to get crucified for this. Thats a bad thing
to do, in other implementations it could easily lead to infinite loops.

[rsc, 2011-07-23 03:06:34]

okay, then i guess the simplest possible is

return a < b || math.IsNaN(a) && !math.IsNaN(b)

[Florian Uekermann, 2011-07-23 03:12:27]

On 2011/07/23 03:06:34, rsc wrote:
> okay, then i guess the simplest possible is
> 
> return a < b || math.IsNaN(a) && !math.IsNaN(b)

yes I guess it is, putting it in one line is probably nicer, will do that.

not that it matters anymore, but I looked through the code a bit, and I think
the working but wrong solution breaks IsSorted anyway, so there was no choice

[Florian Uekermann, 2011-07-23 03:24:35]

Hello golang-dev@googlegroups.com, r@google.com, rsc@golang.org, r@golang.org
(cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-07-23 19:44:42]

LGTM

[rsc, 2011-07-23 19:47:09]

*** Submitted as http://code.google.com/p/go/source/detail?r=ca14957bb4f3 ***

sort: fixed bug in (Float64Slice) Less; NaN less than anything else

Previously comparisons with NaN led to contradictory results if it was
compared to anything not NaN, since Less always returned false, thus
breaking monotonicity of ordering.
This fix makes NaN less than anything else and adds NaN and (+-)Inf to
testcases.

Fixes issue 2092.

R=golang-dev, r, rsc, r
CC=golang-dev
http://codereview.appspot.com/4805051

Committer: Russ Cox <rsc@golang.org>