go 1.6 sort panic: runtime error: index out of range

[Steven Hartland]

After updating to go 1.6 a simple sort that was working fine in 1.5.3
now causes a panic: runtime error: index out of range.

I added some debugging to try can catch it in the act and it seems like
go 1.6's sort may be broken.

Output:
LEN: 189
LEN: 189 i: 95 j: 189
panic: runtime error: index out of range

I should never see that second LEN call as it means that sort called
Less with i or j >= Len().

Code snippet
func (ba Sorter) Len() int {
fmt.Println("LEN:", len(ba))
return len(ba)
}

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

func (ba Sorter) Swap(i, j int) {
ba[i], ba[j] = ba[j], ba[i]
}

Regards
Steve

[Caleb Spare]

Can you show a complete, runnable example please? I cannot reproduce.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Steven Hartland]

I can't I'm afraid its part of a much larger system and takes it a little bit to trigger, so I'm guessing the input data has something to do with it.

Bug raised here:
https://github.com/golang/go/issues/14377

I'm going to add more debug to show what swaps etc are being done.

[Dave Cheney]

Can you please build a version of your program with the -race detector enabled and run that until the program barfs to check that this issue is not caused by a data race.

[Steven Hartland]

The fields being sorted by do indeed have a data race, however the size of the slice is constant (there's an mtx protecting modification of the slice) so given sort knows the length, it shouldn't try to access beyond it surely?

I'm guessing the new sort changes aren't safe if the Less is indeterministic even though the max length is know?

[Caleb Spare]

If there are data races, you don't have any correctness guarantees.

[David Anderson]

On Wed, Feb 17, 2016 at 8:12 PM, Steven Hartland <steven....@multiplay.co.uk> wrote:

The fields being sorted by do indeed have a data race, however the size of the slice is constant (there's an mtx protecting modification of the slice) so given sort knows the length, it shouldn't try to access beyond it surely?

I'm guessing the new sort changes aren't safe if the Less is indeterministic even though the max length is know?

I believe Sort has always relied on the fact that the ordering of values doesn't change mid-sort. It was never safe, now it just happens to go wrong loudly instead of quietly :).

- Dave

[Steven Hartland]

On 18/02/2016 04:35, David Anderson wrote:

On Wed, Feb 17, 2016 at 8:12 PM, Steven Hartland <steven....@multiplay.co.uk> wrote:

The fields being sorted by do indeed have a data race, however the size of the slice is constant (there's an mtx protecting modification of the slice) so given sort knows the length, it shouldn't try to access beyond it surely?

I'm guessing the new sort changes aren't safe if the Less is indeterministic even though the max length is know?

I believe Sort has always relied on the fact that the ordering of values doesn't change mid-sort. It was never safe, now it just happens to go wrong loudly instead of quietly :).

I'm actually ok with slight inaccurate results if the data changes, but as it knows the array bounds it should never try to access beyond them.

Ignoring the race for a minute is seems likely we could see the same issue with non-strict ordered data too, which would be quite a change in spec would it not?

    Regards
    Steve

[Caleb Spare]

I'm actually ok with slight inaccurate results if the data changes, but as it knows the array bounds it should never try to access beyond them.

​Data races can result in any arbitrary behavior, including crashes, not just slightly inaccurate results.

​

 

Ignoring the race for a minute is seems likely we could see the same issue with non-strict ordered data too, which would be quite a change in spec would it not?

​I've tried reproducing this with a non-racy sort that reports a random value for Less but I can't reproduce it.​ But yes, if you can find a non-racy case that causes sort.Sort to panic, that is definitely a bug we'd want to fix.

That said, I'm not sure how you'd expect sort.Sort to meaningfully function if your data does not report a consistent Less ordering.

[Sokolov Yura]

Bug is in race: previous version did check `b<c` so were more permissive to concurrent value change. Current version checks `b!=c && data.Less(pivot, c-1)` and it is not immune to concurrent changes.

Changing equality check to comparison (as in old version) will fix an "issue", but i don't think it is issue: you shall not sort mutating data.

[Sokolov Yura]

Well, it fails also on random comparison (ie random Less), and while sort is not for mixing, some people use it that way. So I think proposed patch is ought to be applied.

[Dan Kortschak]

On Sun, 2016-02-21 at 13:37 -0800, Sokolov Yura wrote:
> Well, it fails also on random comparison (ie random Less),


> and while sort is not for mixing, some people use it that way.

They really shouldn't - this is a good wakeup call.

[Ian Lance Taylor]

On Sun, Feb 21, 2016 at 1:53 PM, Dan Kortschak
<dan.ko...@adelaide.edu.au> wrote:
> On Sun, 2016-02-21 at 13:37 -0800, Sokolov Yura wrote:
>> Well, it fails also on random comparison (ie random Less),
>
>
>> and while sort is not for mixing, some people use it that way.
>
> They really shouldn't - this is a good wakeup call.

It's a wakeup call of sorts, but I don't think it's a good one. It
certainly doesn't point to the problem.

Ian

[Dan Kortschak]

On Sun, 2016-02-21 at 15:01 -0800, Ian Lance Taylor wrote:
> >> and while sort is not for mixing, some people use it that way.
> >
> > They really shouldn't - this is a good wakeup call.
>
> It's a wakeup call of sorts, but I don't think it's a good one. It
> certainly doesn't point to the problem.
>

Maybe, but fixing sort so that people can do things that are wrong seems
like the wrong thing to do.

[Konstantin Shaposhnikov]

FYI, Java 8 Arrays.sort throws an IllegalArgumentException "Comparison method violates its general contract!" in such cases.

[Michael Jones]

Precisely. Less cannot be random! Any callback-sort from the original C-library qsort to now expects that compare(a,b) is a proper function for fixed a and b. If you violate that on purpose, or by race condition accident, you are not honoring the contract that makes the whole notion work.

—
Michael Jones, CEO • mic...@wearality.com • +1 650 656-6989
Wearality Corporation • 289 S. San Antonio Road • Los Altos, CA 94022

> On Feb 21, 2016, at 7:27 PM, Konstantin Shaposhnikov <k.shapo...@gmail.com> wrote:
>
> FYI, Java 8 Arrays.sort throws an IllegalArgumentException "Comparison method violates its general contract!" in such cases.
>

[Damian Gryski]

On Monday, February 22, 2016 at 5:20:00 AM UTC+1, Michael Jones wrote:

Precisely. Less cannot be random! Any callback-sort from the original C-library qsort to now expects that compare(a,b) is a proper function for fixed a and b. If you violate that on purpose, or by race condition accident, you are not honoring the contract that makes the whole notion work.

Exactly. A Less() which lies is just as bad as a Len() which lies: both will lead to crashes.

Damian

[Sokolov Yura]

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?

[Ian Davis]

The important point is that two calls to Less with the same arguments
should always give the same result. That should be stated as part of the
function's conditions of use.

Ian

[Steven Hartland]

I would agree with this statement however you can't get away from the
fact that no matter how bad it is to use it with an implementation which
doesn't abide by this, this was not part of the original go1 spec, so
changing it now would break the go1 compatibility guarantee IMO.

Regards
Steve

[Val]

Ian, unless I'm very mistaken this is not enough.
A consistent Less implementation, which would always return :

• Less(a,b) == true
• Less(b,c) == true
• Less(c,a) == true

should be regarded as just as broken as non-consistent successive calls.
Val

[Konstantin Shaposhnikov]

That is only assuming that "teenagers" know what they are doing ;)

[Steven Hartland]

The definition for Less doesn't deal with the case when two items are equal so both return false.

For strict sort ordering Less(i, j) must always equal !Less(j, i) which is not stated as requirement.

On 22/02/2016 11:37, gaurav wrote:

Isn't definition of Less() quite unambiguous? where is the room in the spec to return random or inconsistent answer. the way I read it, Less has to be consistent as well as transitive as well.

type Interface interface {
        // Len is the number of elements in the collection.
        Len() int
        // Less reports whether the element with
        // index i should sort before the element with index j.
        Less(i, j int) bool
        // Swap swaps the elements with indexes i and j.
        Swap(i, j int)
}

[Michael Jones]

Less in Sort is “less than”, aka “<“ from mathematics:

Less(i,j) ==> array[i] < array[j]

The truth table is simple:

Less(i,j) returns...

array[i] < array[j] ==> true

array[i] = array[j] ==> false

array[i] > array[j] ==> false

Less(i,j) != !Less(j,i) in the case that array[i] == array[j]

The code in Sort knows how to compare Less(i,j) and Less(j,i) to understand the lay of the land:

if Less(i,j) {

    // array[i] < array[j] 

} else if Less(j,i) {

    // array[i] > array[j]

} else {

    // array[i] == array[j] // …at least in terms of sort keys

}

When we say the code “knows” we mean “unless the author of Less() is playing games."

— 

Michael Jones, CEO  •  mic...@wearality.com  •  +1 650 656-6989 

Wearality Corporation  •  289 S. San Antonio Road  •  Los Altos, CA 94022

[gaurav]

Isn't definition of Less() quite unambiguous? where is the room in the spec to return random or inconsistent answer. the way I read it, Less has to be consistent as well as transitive as well.

type Interface interface {
        // Len is the number of elements in the collection.
        Len() int
        // Less reports whether the element with
        // index i should sort before the element with index j.
        Less(i, j int) bool
        // Swap swaps the elements with indexes i and j.
        Swap(i, j int)
}

On Monday, February 22, 2016 at 3:45:09 PM UTC+5:30, Steven Hartland wrote:

[gaurav]

Less() only requires you to tell if item at index i should be placed before item at index j. It does not talk about equality etc.

As implementer of that interface, you must know specify a consistent answer to that.

[Axel Wagner]

I do think that there is a case to be made here for improving the documentation of Less.

I think that it is a given, that it should be consistent, yes. But is the order required to be total or is a partial order okay too? If so, will the result be topologically sorted? As the documentation currently states, I would claim that the answer *might* be "yes" to both. And I think it would be great if that's the case. On the other hand I have no idea if the underlying implementation relies on a total ordering or not (most of the posts in this thread so far certainly assume a total ordering).

Allowing partial orderings would allow, for example, to use the sort package for ordering dependent tasks. I think that would be great (but not worth it to make the algorithm more expensive if it's not currently the case).

[Aaron Cannon]

> On Feb 22, 2016, at 03:37, Sokolov Yura <funny....@gmail.com> wrote:
>
> Is Go only for good teams, or for "teenagers" also?

Good teams! Teenagers will thank us later, when they attempt to join a good team.
--
This message was sent from a mobile device

[Devon H. O'Dell]

2016-02-17 20:17 GMT-08:00 Caleb Spare <ces...@gmail.com>:
> If there are data races, you don't have any correctness guarantees.

This is not a true statement. It is also not true that for any given
protocol, a lack of data races implies correct behavior.

--dho

[Caleb Spare]

> If there are data races, you don't have any correctness guarantees.

This is not a true statement.

​​I'm talking about Go, as specified today. If you still disagree, please explain.​

 

It is also not true that for any given
protocol, a lack of data races implies correct behavior.

​I did not state that. (It is the inverse of my claim.)

[Devon H. O'Dell]

2016-02-22 18:38 GMT-08:00 Caleb Spare <ces...@gmail.com>:
>> > If there are data races, you don't have any correctness guarantees.
>>
>> This is not a true statement.
>
> I'm talking about Go, as specified today. If you still disagree, please
> explain.

Perhaps you were stating this as applied to usage of Sort, but it is
stated absolutely. It is not absolutely true, so I wanted to clarify
that point, regardless of what is possible with Go today.

That said, I do still disagree: one can implement lock-free data
structures on top of sync.atomic such that data races are present, but
such that operations linearize. Linearization provides a correctness
guarantee, and some (but by far not all) of these structures can be
implemented in Go, as specified today.

>> It is also not true that for any given
>> protocol, a lack of data races implies correct behavior.
>
> I did not state that. (It is the inverse of my claim.)

I point it out because one can also implement lock-free data
structures entirely using sync.atomic where no data races occur, but
which do not function correctly given some concurrent workloads.

From that perspective, data races are uninteresting because they
neither imply correctness nor the lack thereof. Correctness is only
provided by strict serialization (of which linearization is a special
case).

[Caleb Spare]

On Mon, Feb 22, 2016 at 6:51 PM, Devon H. O'Dell <devon...@gmail.com> wrote:

2016-02-22 18:38 GMT-08:00 Caleb Spare <ces...@gmail.com>:
>> > If there are data races, you don't have any correctness guarantees.
>>
>> This is not a true statement.
>
> I'm talking about Go, as specified today. If you still disagree, please
> explain.

Perhaps you were stating this as applied to usage of Sort, but it is
stated absolutely. It is not absolutely true, so I wanted to clarify
that point, regardless of what is possible with Go today.

That said, I do still disagree: one can implement lock-free data
structures on top of sync.atomic such that data races are present, but
such that operations linearize. Linearization provides a correctness
guarantee, and some (but by far not all) of these structures can be
implemented in Go, as specified today.

If the shared memory access is done through atomic operations, then I don't call that a data race. I also don't think that's the common usage in the Go ecosystem. (For example, the race detector does not flag atomic accesses; https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong refers to code using atomics as "race-free", etc)

[Devon H. O'Dell]

2016-02-22 19:11 GMT-08:00 Caleb Spare <ces...@gmail.com>:
>
>
> On Mon, Feb 22, 2016 at 6:51 PM, Devon H. O'Dell <devon...@gmail.com>
> wrote:
>>
>> 2016-02-22 18:38 GMT-08:00 Caleb Spare <ces...@gmail.com>:
>> >> > If there are data races, you don't have any correctness guarantees.
>> >>
>> >> This is not a true statement.
>> >
>> > I'm talking about Go, as specified today. If you still disagree, please
>> > explain.
>>
>> Perhaps you were stating this as applied to usage of Sort, but it is
>> stated absolutely. It is not absolutely true, so I wanted to clarify
>> that point, regardless of what is possible with Go today.
>>
>> That said, I do still disagree: one can implement lock-free data
>> structures on top of sync.atomic such that data races are present, but
>> such that operations linearize. Linearization provides a correctness
>> guarantee, and some (but by far not all) of these structures can be
>> implemented in Go, as specified today.
>
>
> If the shared memory access is done through atomic operations, then I don't
> call that a data race. I also don't think that's the common usage in the Go
> ecosystem. (For example, the race detector does not flag atomic accesses;
> https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong
> refers to code using atomics as "race-free", etc)

An atomic pointer load, followed by non-atomic reads of that memory
into local state, followed by a CAS of the original pointer are likely
to trip the race detector, and still seem to qualify as a "data race"
given your definition. (And the race detector will -- or at least used
to; I haven't tried recently -- flag the non-atomic reads. I'd be
surprised if it didn't anymore, because then it could prove
linearization, which seems out of its capability.) This is how many
non-blocking data structures work.

I do agree that it is uncommon, so this is probably a silly argument.
But data races do not automatically imply lack of correctness in Go or
in any other language that provides RMW primitives like CAS. And
that's my point: the existence or lack of a data race by itself says
nothing about the correctness of a program, and therefore labeling
something as a data race is almost entirely useless for formal
discussions of correctness.

[Caleb Spare]

An atomic pointer load, followed by non-atomic reads of that memory
into local state, followed by a CAS of the original pointer are likely
to trip the race detector, and still seem to qualify as a "data race"
given your definition. (And the race detector will -- or at least used
to; I haven't tried recently -- flag the non-atomic reads. I'd be
surprised if it didn't anymore, because then it could prove
linearization, which seems out of its capability.)

​Please give an example. I've used a load-modify-cas pattern before without tripping the race detector. I also tried coding up an example:

http://play.golang.org/p/ZPX20YRqCr

and the race detector doesn't seem to have a problem with it.

The race detector is not supposed to have any false positives. If you can find an example of the race detector flagging code that you believe is fine, please file a bug.

 

This is how many
non-blocking data structures work.

I do agree that it is uncommon, so this is probably a silly argument.
But data races do not automatically imply lack of correctness in Go or
in any other language that provides RMW primitives like CAS. And
that's my point: the existence or lack of a data race by itself says
nothing about the correctness of a program, and therefore labeling
something as a data race is almost entirely useless for formal
discussions of correctness.

​Again, I'm only talking about Go. In Go, a data race is inherently a bug wrt the programming model, even if the generated code today is okay. (This is the conclusion I've come to based on what the authors have written; it's not really documented properly though. That's what #5045 and #8897 are for.)

[Devon H. O'Dell]

2016-02-22 20:13 GMT-08:00 Caleb Spare <ces...@gmail.com>:
> Please give an example. I've used a load-modify-cas pattern before without
> tripping the race detector. I also tried coding up an example:
>
> http://play.golang.org/p/ZPX20YRqCr
>
> and the race detector doesn't seem to have a problem with it.
>
> The race detector is not supposed to have any false positives. If you can
> find an example of the race detector flagging code that you believe is fine,
> please file a bug.

The race detector has come a long way. I can't get it to complain, but
I can get it to not complain when obvious ABA problems are present.
(That said, it has false negatives, which is why the inverse argument
is important.) This isn't material to the argument.

> Again, I'm only talking about Go. In Go, a data race is inherently a bug wrt
> the programming model, even if the generated code today is okay. (This is
> the conclusion I've come to based on what the authors have written; it's not
> really documented properly though. That's what #5045 and #8897 are for.)

A data race still isn't a bug. An accessible, easy example of this is
a simple lossy counter.

So as far as I can understand, you're defining "bug" to mean something
other than "behavior other than what the programmer intended". It is
possible you define bug to mean "not providing correctness
guarantees", but this is subtly not the same thing. A lossy counter
inherently does not have a strictly correct value, but that does not
inherently make the program behave in an unintended fashion.

More importantly, the definition of "data race" is an event which
"...occurs when two concurrent threads access a shared variable and
when: at least one access is a write and the threads use no explicit
mechanism to prevent the accesses from being simultaneous"[1], which
does not agree with your definition. For example, in lock-free data
structures, reads and writes commonly appear simultaneously, and
linearization points occur only between writes; therefore it is
possible to write correct software that contains data races. It then
follows that data races imply no correctness guarantees is false,
regardless of your language, its memory model, or its runtime
environment -- they aren't even part of the equation. You can write
incorrect software that contains data races. You can write correct
software that contains data races. We're back to the fact that data
races say nothing about correctness, and I really don't need to write
code to show this.

Regarding whatever people want to document in #5045 and #8897, it
would be disingenuous to document the term "data race" to mean
anything but the definition in [1], as that is the definition used by
nearly every paper on the subject.

Since we don't agree on the definitions of "bug" or "data race", I
don't think it is worthwhile to continue arguing. I am sure you can
find definitions of both that would make me agree with you.

--dho

[1]: https://cseweb.ucsd.edu/~savage/papers/Tocs97.pdf "Eraser: A
Dynamic Data Race Detector for Multithreaded Programs"