Can you show us a complete program that reproduces the problem?

Or at least the complete Less function.

(Does Go now require Less to be a strict weak ordering like the STL in C++?)

On golang-nuts @stevenh mentioned that the program has a data race.

@cespare, thanks. Indeed, from golang-nuts:

The fields being sorted by do indeed have a data race, however ...

No "howevers". Data race = no promises.

Here's the full version of Less.

func (ba Sorter) Less(i, j int) bool {
if len(ba) <= i || len(ba) <= j {
fmt.Println("LEN:", len(ba), "i:", i, "j:", j)
}
a, b := ba[i], ba[j]

     if a.VirtualType() < b.VirtualType() {
             return true
     } else if b.VirtualType() < a.VirtualType() {
             return false
     }

     aAlloc := a.Allocated()
     bAlloc := b.Allocated()
     if aAlloc > bAlloc {
             return true
     } else if bAlloc > aAlloc {
             return false
     }

     if a.LastUsed().After(b.LastUsed()) {
             return true
     } else if b.LastUsed().After(a.LastUsed()) {
             return false
     }

     return a.ID() < b.ID()

}

-race identified that LastUsed is racey, but it didn't race on the sort
run which paniced.

On 18/02/2016 04:21, Brad Fitzpatrick wrote:

Or at least the complete Less function.

(Does Go now require Less to be a strict weak ordering like the STL in
C++?)

—
Reply to this email directly or view it on GitHub
#14377 (comment).

Feel free to re-open this bug if you have a complete stand-alone race-free repro.

But if there's a bug, somebody else will hit it. Everybody uses sort. The fact that we haven't seen it already suggests it is due to your race.

We had a similar issue with one of our sorts where comparison was not deterministic (we used random as a tiebreaker). It makes sense that it should be, but it might be a good idea to either document it or produce a more explicit error message.

Example that "works" in go 1.5 but crashes in 1.6:

package main

import (
    "math/rand"
    "sort"
)

type Test struct{}

type TestSort []*Test

func (v TestSort) Len() int {
    return len(v)
}
func (v TestSort) Swap(i, j int) {
    v[i], v[j] = v[j], v[i]
}
func (v TestSort) Less(i, j int) bool {
    return rand.Float32() < 0.5
}

func main() {
    results := []*Test{}
    for i := 0; i < 100; i++ {
        results = append(results, &Test{})
    }
    sort.Sort(TestSort(results))
}

@hamaxx, thanks!

I can confirm:

bradfitz@laptop ~$ GOROOT=$HOME/go1.4 go run sort.go
bradfitz@laptop ~$ GOROOT=$HOME/go1.5 go run sort.go
bradfitz@laptop ~$ GOROOT=$HOME/go go run sort.go
panic: runtime error: index out of range

goroutine 1 [running]:
panic(0x66280, 0xc82000a080)
    /Users/bradfitz/go/src/runtime/panic.go:464 +0x3e6
main.(*TestSort).Swap(0xc82000e1c0, 0x62, 0xffffffffffffffff)
    <autogenerated>:2 +0x14b
sort.doPivot(0x13d088, 0xc82000e1c0, 0x0, 0x64, 0xc82000e1c0, 0x18)
    /Users/bradfitz/go/src/sort/sort.go:134 +0x5ea
sort.quickSort(0x13d088, 0xc82000e1c0, 0x0, 0x64, 0xd)
    /Users/bradfitz/go/src/sort/sort.go:195 +0xa3
sort.Sort(0x13d088, 0xc82000e1c0)
    /Users/bradfitz/go/src/sort/sort.go:229 +0x74
main.main()
    /Users/bradfitz/sort.go:27 +0x139
exit status 2

I didn't look too deeply into it, but I think it might be pretty easy to just fix the issue for the next release:

--- orig/sort.go    2016-02-18 18:22:08.837326357 +0100
+++ sort.go 2016-02-19 17:18:50.180761240 +0100
@@ -119,15 +119,15 @@
    pivot := lo
    a, c := lo+1, hi-1

-   for ; a != c && data.Less(a, pivot); a++ {
+   for ; a < c && data.Less(a, pivot); a++ {
    }
    b := a
    for {
-       for ; b != c && !data.Less(pivot, b); b++ { // data[b] <= pivot
+       for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
        }
-       for ; b != c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
+       for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
        }
-       if b == c {
+       if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] <= pivot
@@ -167,11 +167,11 @@
        //  data[a <= i < b] unexamined
        //  data[b <= i < c] = pivot
        for {
-           for ; a != b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
+           for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
            }
-           for ; a != b && data.Less(a, pivot); a++ { // data[a] < pivot
+           for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
            }
-           if a == b {
+           if a >= b {
                break
            }
            // data[a] == pivot; data[b-1] < pivot

I didn't thought about "random tie breaker" when i've changed comparison to inequality check.

While I think "random tie breaker" is not a good thing, it is sometimes useful. So patch should be applied.

Had someone sent already change for review?

@funny-falcon, no, there is no patch yet. It would be referenced here automatically if so. Want to send one?

@hamaxx wrote it already in his comments (both test case and fix), so if he wants to make a patch, i will not cross his way.

Aside: I would recommend against the "random tie breaker" method. While I do think the index out of bound panic should be fixed, I don't think sort.Sort makes any guarantees about the output ordering when Less is not a deterministic total ordering function. (And the random tie breaker method violates both determinism and total ordering.)

@mdempsky if you are team leader, you shall not allow "random tie breaker" to be merged into master. "rtb" is really a hack.

But if you makes personal project, then it is "quick and dirty" way to "sort by priority and get some random elements from min/max/mean priority".

Is Go only for good teams, or for "teenagers" also?

@funny-falcon, or @hamaxx, please send a CL. Code in comments isn't enough. Thanks.

Sure, I can send a CL.

@hamaxx, thanks!

@bradfitz I didn't tell comments are enough ;-) I've said I don't want to steal @hamaxx authorship

It's not clear to me that defending against inconsistent Less functions is required of sort.Sort. Therefore it's not clear to me that this needs to go into a point release.

Some one points to Go1x compatibility claim: program were working before Go1.6 and now it fails.

I believe it is my fault: when I changed condition I had an image of stable Less in my mind, and I forgot about "random tie breaker". "rtb" is really useful in some "quick&dirty" programs.

CL https://golang.org/cl/19823 mentions this issue.

CL https://golang.org/cl/22039 mentions this issue.