proposal: sort/heapsort: Use bottom up heapsort

[ValarDragon]

Currently the golang heapsort implementation uses the standard "siftdown" method, of taking a node, and checking if it is greater than either of its two child nodes. It is faster to use "bottom-up heapsort", as described here https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort, which basically just entails an update to the siftdown method. This will have no outward API changes, since this would just be improving the performance of heapsort, not changing its functionality.

I can implement this, if the proposal is accepted.

[agnivade]

Related #25137.

Your case might be easier to consider if you have a working prototype with benchmarks showing performance improvements.

[ValarDragon]

Finished the code, its at the point where it passes all of the tests! I'll clean it up and then put it on gerrit.
The performance improvements are hard to see under the normal benchmarks, since introsort rarely goes to heapsort. (Basically only in the adversarial cases where quicksort would normally degenerate to O(n^2) performance)

If I switch sort to just be heapsort, here is what the interface operation counts used to be:

--- PASS: TestCountSortOps (0.75s)
    sort_test.go:635: Sort        100 elements:         554 Swap,       1005 Less
    sort_test.go:635: Sort        300 elements:        2197 Swap,       4012 Less
    sort_test.go:635: Sort       1000 elements:        9038 Swap,      16829 Less
    sort_test.go:635: Sort       3000 elements:       32089 Swap,      60232 Less
    sort_test.go:635: Sort      10000 elements:      124139 Swap,     235333 Less
    sort_test.go:635: Sort      30000 elements:      419770 Swap,     800625 Less
    sort_test.go:635: Sort     100000 elements:     1575082 Swap,    3019629 Less
    sort_test.go:635: Sort     300000 elements:     5196029 Swap,   10001230 Less
    sort_test.go:635: Sort    1000000 elements:    19046823 Swap,   36793561 Less

And now they are:

--- PASS: TestCountSortOps (0.62s)
    sort_test.go:635: Sort        100 elements:         597 Swap,        691 Less
    sort_test.go:635: Sort        300 elements:        2226 Swap,       2573 Less
    sort_test.go:635: Sort       1000 elements:        9076 Swap,      10331 Less
    sort_test.go:635: Sort       3000 elements:       32130 Swap,      35772 Less
    sort_test.go:635: Sort      10000 elements:      124174 Swap,     136649 Less
    sort_test.go:635: Sort      30000 elements:      419819 Swap,     457355 Less
    sort_test.go:635: Sort     100000 elements:     1575131 Swap,    1699305 Less
    sort_test.go:635: Sort     300000 elements:     5196107 Swap,    5569848 Less
    sort_test.go:635: Sort    1000000 elements:    19046885 Swap,   20296423 Less

This implies that when Introsort switches to heapsort, this significantly reduces the number of "Less" operations. Though it has a small increase to the number of swaps. This shouldn't be a huge issue for performance though, since when switching to heapsort, it has to have a minimum of 12 elements left, and this should help in the adversarial cases with large numbers of elements. Also I think swaps should be more efficient than less's in many instances -- I can benchmark the time for how the heap sort implementations compare at low numbers of elements if desired.

Benchmarking the performance with the standard introsort benchmarks didn't yield any difference, since the standard benchmarks aren't on adversarially chosen data, which is the only time Introsort switches over to using the heap sort implementation. Should I create a new benchmark for how it performs on adversarially chosen data?

[gopherbot]

Change https://golang.org/cl/120699 mentions this issue: sort: improve unstable sort on adversarial input

[rsc]

This doesn't need to go through the proposal process if it has no user-visible effect. Brad asked on the CL about the effect on elements that compare equal according to Less but are nonetheless distinguishable in the final output. If the CL really has no effect on that case, then it's just a performance improvement, which is fine. But if it does have a visible effect, then it's probably not worth it, since this is in fallback code that is very rarely used, so its performance doesn't matter much. The fact that the number of Swap calls change suggests that this does have a user-visible effect though.

Will close this - review on the CL is fine - but please do NOT change the user-visible ordering for a very rare performance win.

[ValarDragon]

Sounds good. I will work on debugging why the number of swaps differs, and producing test cases to ensure the ordering doesn't change between this implementation and the current one.