proposal: slices, sort: randomize sort order of equal elements in tests

[znkr]

Proposal Details

Go's (non-stable) sort functions don't guarantee a particular ordering for equal elements. However, since the order of equal elements is always the same for a number of releases, tests tend to accumulate dependencies on the ordering of equal elements by accident.

In Google codebase we noticed that a large number of tests depended on the order of equal elements when the sorting algorithm was changed to pdqsort in April 2022 (http://go.dev/cl/371574). We needed to fix all of these to be able to release pdqsort internally. Recently http://go.dev/cl/624295 changed how equal elements are ordered. In the 2½ years since pdqsort was introduced a few tests have already started to depend on the order of equal elements again.

This is a classic example of Hyrum's Law

With a sufficient number of users of an API,
it does not matter what you promise in the contract:
all observable behaviors of your system
will be depended on by somebody.

Fixing tests when the order of equal elements changes is a lot of work and makes upgrading to a new Go version harder. It's also surprisingly hard to understand if the order of equal elements actually matters (i.e. if stable sort should have been used) or if the order of equal elements was depended upon accidentally. Both problems can be mitigated sufficiently by randomizing the order of equal elements on each test run. That way, tests that depend on the order of equal elements provide a very early signal of problem.

Google already did this for C++ some time ago and it's working very well:

• https://libcxx.llvm.org/DesignDocs/UnspecifiedBehaviorRandomization.html
• https://reviews.llvm.org/D96946
• https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/

[gabyhelp]

Related Issues and Documentation

• proposal: sort: return equal values in non-deterministic order #13884 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[mateusz834]

I assume that this would be implemented with the use of testing.Testing(), which means that it might also slow down benchmarks performance, right? is this fine to do?

[znkr]

@mateusz834, I left out any implementation details, but I would be very surprised if this can't be implemented in a way that doesn't impact performance in production. If no such mechanism is available, the slowdown should be a trivially predictable branch.

[znkr]

What changed since the last proposal (#13884):

• A stronger emphasis in the documentation did not help, we're still seeing tests depending on the order of equal elements
• One of the reasons for pushing back was that it's sending the wrong message: "We will deliberately surprise you with our algorithms because of something that doesn't really matter to you." (@robpike). One argument that I didn't see in the discussion is that it's very hard to understand if someone intended the order of equal elements to be stable or not once the algorithm changes.
• We now had multiple changes in the order of equal elements. I think it's fair to expect more in the future.

[mateusz834]

I left out any implementation details, but I would be very surprised if this can't be implemented in a way that doesn't impact performance in production. If no such mechanism is available, the slowdown should be a trivially predictable branch.

I don't mean production environments, but benchmarks in the _test.go files, (i guess) that they might slow down a bit because of this change. I don't strongly feel this as an huge issue, but something to consider.

[znkr]

Sorry for the misunderstanding. You are correct of course. I am sure there are cases where it matters. The pervious proposal suggested an opt-out mechanism for tests that should also work for benchmarks.