proposal: sort: return equal values in non-deterministic order

[rsc]

Crazy idea, but what if sort.Sort randomly permuted its input a bit before starting?

Go 1.6 has a different sort.Sort than Go 1.5 and I've seen at least a dozen test failures at Google that were implicitly depending on the old algorithm. The usual scenario is that you sort a slice of structs by one field in the struct. If there are entries with that field equal but others unequal and you expect a specific order for the structs at the end, you are depending on sort.Sort's algorithm. A later sort.Sort might make a different choice and produce a different order. This makes programs not portable from one version of Go to another, much like map hash differences used to make programs not portable from one architecture to another. We solved maps by randomizing the iteration order a bit. In the map case it's not a full permutation, but just enough variation to make tests obviously flaky.

I wonder if we should do the same for sort.Sort. It would only take N swaps to shuffle things quite well, and we already use N*log(N) swaps, so N*(log(N)+1) is not likely to be noticed. That would also protect a bit against malicious inputs.

It would surprise people, especially people who think sort.Sort == sort.Stable. But the rationale is that it's better to surprise them the first time they run the code instead of however many Go releases later.

/cc @robpike, @griesemer, @ianlancetaylor, @aclements, @dr2chase

[bradfitz]

Interesting. Perhaps we only do it for "small" inputs (most likely: tests), where it would especially unnoticed.

[rsc]

Given my experience fixing Google tests, I would do it on large inputs too. The larger the inputs the more the time required fades into the noise.

[ALTree]

There's one thing to consider.

The work the runtime does to randomize map iteration order is 100% justified because every time you iterate over a map you get a different order, so you are seeing the effects of the randomization 100% of the times.

That wouldn't be true for sort.Sort randomization. You write

It would only take N swaps to shuffle things quite well

but you don't really care about "shuffling the array well". What you really care about is the chance that N swaps change the order of the sorted array. Suppose you do the math and find out that that chance is really small, unless the array has a lot of repeated entries.

That would mean that you are always paying a price for a benefit that has zero chances to affect the user for arrays with no repeated entries, a very small chance to be seen if the array has a moderated number of repeated entries, and a decent chance to be a real benefit only for arrays with a decent number of repeated entries.

The bottom line is that one thing is to pay a (maybe) small price for something that has a visible effect 100% of the times, and another thing is to pay a (maybe) small price for something that has a (maybe) very small chance to actually do something useful. If the final result of the sorting is unchanged, the work spent shuffling is 100% wasted.

Just a random thought. I didn't do any math, nor run any benchmark.

[griesemer]

I like it. If people want stable sort they should use stable sort.

[rsc]

@ALTree The math works out OK. If you have two equal elements and sort.Sort puts them in one order, then if you swap them sort.Sort will necessarily put them in the other order, since it can't tell them apart. For any pair of places they might be, as long as the chance of one being before the other is 50/50 it works out.

Another possibility is a final run over the sorted list looking for equal entries and swap them randomly. That's N comparisons instead of N swaps though, and swaps are usually cheaper.

The price here is being paid on behalf of future compatibility. It's always 100% wasted if you ignore that. It would only make sense if the price were low enough to make sense to pay all the time. (And the larger the data being sorted the lower the price.)

[ianlancetaylor]

We could simply randomly flip the order of the insertion sort we use in the final step. If the comparison function is not fully specified, we should get different results. That would be essentially free.

[rsc]

What does "randomly flip the order of the insertion sort" mean? If X is before Y at the start of the insertion sort, it will stay X before Y throughout, no? I guess the insertion sort could go out of its way to drag equal elements past each other.

[robpike]

This gives me a bad taste. You're (mildly) punishing all users to make it easier for you (you in particular) to find bugs in others' code triggered by changes in the code base. I understand the argument for maps, but there the cost is minute and the frequency of dependence high. Here you need multiple sort operations even to create the possibility of the issue.

Much as I understand your frustration in dealing with the problem, it bothers me that that your solution is to take it out on everyone.

[ianlancetaylor]

The insertion sort code is

func insertionSort(data Interface, a, b int) {
    for i := a + 1; i < b; i++ {
        for j := i; j > a && data.Less(j, j-1); j-- {
            data.Swap(j, j-1)
        }
    }
}

We randomly flip between that version and

func insertionSort(data Interface, a, b int) {
    for i := b - 2; i >= a; i-- {
        for j := i; j < b-1 && !data.Less(j, j+1); j++ {
            data.Swap(j, j+1)
        }
    }
}

I probably have an off-by-one error in there, but that's the basic idea.

[cespare]

I like this idea. WRT the performance hit: people who need really fast sorting aren't using sort.Sort anyway.

[robpike]

It's not the performance hit that bothers me, it's the message: We will deliberately surprise you with our algorithms because of something that doesn't really matter to you.

I'm not totally opposed, I just find it distasteful.

[davecheney]

I'm with Rob. The understand the sentiment of this and the precedent of the
map change but on balance I would prefer not to see this change land.

To give some background, juju is close to 200k lines and many of our tests
were faulty and needed to be fixed as I'm trying to drag canonical off Go
1.2. This is a good thing.

However I've also spent an equal amount of time internally defending the
map change from people who persist that Go changed something by randomising
map ordering, when of course there was never a promise of ordering in the
first place. My coworkers are unable to see this as their own carelessness,
and blame Go for deliberately breaking their code to this day.

This sort change may help people project themselves from themselves, but
they aren't going to thank us, no matter how well intentioned our
motivations.

Thanks

Dave

On Sat, 9 Jan 2016, 15:35 Rob Pike notifications@github.com wrote:

It's not the performance hit that bothers me, it's the message: We will
deliberately surprise you with our algorithms because of something that
doesn't really matter to you.

I'm not totally opposed, I just find it distasteful.

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

[griesemer]

@davecheney I understand the sentiment in this case. But a future perhaps more efficient implementation may lead to a similar unanticipated change of order, with the same effect on code that makes implicit order assumptions. It seems to me it would be better to eliminate those errors earlier than later (or possibly even multiple times).

It would be interesting to make the experiment. GO16SORTEXPERIMENT=1 could enable it. (disabled by default). That way teams willing to take the plunge can try it out and see if it exposes any real errors. It would be fine to remove again for 1.7 if there's no real benefit.

[minux]

I think if we're going to make it an experiment, it should be default on, and people can opt-out if necessary.