ianlancetaylor
commented
1 year ago CC @eliben
Open PeterRK opened 1 year ago
ianlancetaylor
commented
1 year ago CC @eliben
rsc
commented
1 year ago I think we already used this decade's "change to a new sort algorithm" coupon.
eliben
commented
1 year ago cc @zhangyunhao116
PeterRK
commented
1 year ago I think we already used this decade's "change to a new sort algorithm" coupon.
Dual-pivot quicksort is not a new sort algorithm. It can be found in Java standard library many years ago. New algorithm like pdqsort is not always best.
rsc
commented
1 year ago My point is we just put the ecosystem through the churn of a sort change in Go 1.19 (2022). I don't see a strong argument that slices.Sort is somehow fundamentally different from sort.Slice and merits a different algorithm, nor do I see a strong argument for invalidating our decision just last year to switch to pdqsort. We could spend lots of time flip-flopping between different sort algorithms in the standard library, or we could do other work. Having just changed the sort algorithm last year, I think we owe it to ourselves and our users not to change it again for at least five years (that is, Go 1.29 at the earliest) unless we have very good reasons.
We should definitely not make a change for Go 1.21 - it is too late in the cycle.
PeterRK
commented
1 year ago My point is we just put the ecosystem through the churn of a sort change in Go 1.19 (2022). I don't see a strong argument that slices.Sort is somehow fundamentally different from sort.Slice and merits a different algorithm, nor do I see a strong argument for invalidating our decision just last year to switch to pdqsort. We could spend lots of time flip-flopping between different sort algorithms in the standard library, or we could do other work. Having just changed the sort algorithm last year, I think we owe it to ourselves and our users not to change it again for at least five years (that is, Go 1.29 at the earliest) unless we have very good reasons.
We should definitely not make a change for Go 1.21 - it is too late in the cycle.
I agree that it’s not a good idea to make changes frequently. People now can use different sort algorithms with third-party libraries. Just let it fly.
eliben
commented
1 year ago To add to @rsc 's point, we're also putting the community through a "sorting change" right now, in the upcoming Go 1.21, where the slices package with its sorting functionality is entirely new. It provides better performance than the sort package in many cases, so we're going to recommend Go users to shift to it, if possible. This is a fairly major change.
pdqsort was a large performance improvement for some cases. The slices.Sort (vs. sort) is also a significant speedup. Compared to these, the quoted improvements with dual-pivot quicksort are relatively modest (except sorting a slice of ints). So I definitely agree that we should give the community time to settle with the recent changes, and if people require the absolutely fastest sort of an int slice, they can use a 3rd party package.
PeterRK
commented
1 year ago To add to @rsc 's point, we're also putting the community through a "sorting change" right now, in the upcoming Go 1.21, where the
slicespackage with its sorting functionality is entirely new. It provides better performance than thesortpackage in many cases, so we're going to recommend Go users to shift to it, if possible. This is a fairly major change.pdqsort was a large performance improvement for some cases. The
slices.Sort(vs.sort) is also a significant speedup. Compared to these, the quoted improvements with dual-pivot quicksort are relatively modest (except sorting a slice of ints). So I definitely agree that we should give the community time to settle with the recent changes, and if people require the absolutely fastest sort of an int slice, they can use a 3rd party package.
Patern-defeating techique just makes fastest cases faster. It helps little in real hybrid workload. New apis are needed to achieve significant speedup. But I don't think it's worthy to change standard library apis for speed now.
PeterRK
commented
1 year ago I didn't really care which sort algorithm is used in go standard library until someone claimed pdqsort is fastest algorithm in Go. That's not the truth, but got credit from go tream. @eliben @rsc
zhangyunhao116
commented
1 year ago @PeterRK
I'm the author of this article, and I don't think I claimed that "PDQSORT is the fastest sorting algorithm in Go".
We can see the summary of this article(translated from Chinese directly):
At present, most of the unstable sorting algorithms used in the industry have basically changed from a single sorting algorithm in textbooks to a hybrid sorting algorithm to deal with various sequences in practical scenarios.
Relying on its performance advantages in common scenarios compared with previous algorithms, pdqsort has gradually become the mainstream implementation of unstable sorting algorithms. Based on the generics brought by Go1.18, the implementation of sorting algorithms is greatly simplified, and it also gives us the possibility to implement new algorithms. But pdqsort is not a panacea. In some cases, other algorithms still maintain advantages (for example, timsort of the Python standard library is better than pdqsort in mixed ascending && descending scenarios). However, in most cases, pdqsort has become a better choice for unstable algorithms depending on its specific optimization for different situations.
The title of this article is "Building the fastest sorting algorithm"(it is ongoing), PDQSORT is just an important milestone on the road to building the fastest sorting algorithm. There are still many other languages or libraries that use this algorithm, and I still haven't found any algorithm that is faster than PDQSORT in all cases for now. PDQSORT is still one of the fastest hybrid sorting algorithms in some cases.
In addition, I am not the author of the PDQSORT algorithm itself. This implementation is first used internally at my work and then contributed to the community.
This article is more to let everyone understand the principles of the algorithm (in fact, this article is part of a course for college students within the company), and to attract more people to participate in community building, if you have a better idea for sorting algorithms, feel free.
PeterRK
commented
1 year ago Pattern-defeating technique can be found in timsort. Branch-eliminating technique comes from blockquicksort. Cache-exploiting technique comes from dual-pivot quicksort. Pdqsort trys to combine those techniques, but fail to handle the conflict between branch-eliminating technique and cache-exploiting technique. The author of pdqsort explains in paper why he choose branch-eliminating technique after trade-off. Cache-exploiting technique should be used in where branch-eliminating technique doesn’t work. Implement in go standard library distorts the idea of pdqsort and exaggerate its power.
Most worryingly, go team seems to support this mistake.
zhangyunhao116
commented
1 year ago In the process of implementation, we often need some engineering compromises, which means that the optimization of the paper wouldn't always work. For example, the implementation in the standard library is about 10%~ 20% slower than the original implementation I used. This is because it needs to support both interface-sorting and integer-sorting, and these algorithms need to be generated using the same file.
If the algorithm only needs to support integer sorting or doesn't need to be generated via the same file, many other optimizations can be used, but it doesn't mean these engineering compromises are a mistake.
Reinplement #52789 based on go 1.21rc2. Here is new benchmark result.
Xeon-8374C
EPYC-7K83
Dual-pivot quicksort usually has better performance than current pdqsort. It can be even faster with api change.
Xeon-8374C (X86-64)
Yitian-710 (ARM64)
By the way, this new implement is also shorter and simpler.