Skip to content

Commit

Permalink
sort: use pdqsort
Browse files Browse the repository at this point in the history 
- Across all benchmarks, pdqsort is never significantly slower than the previous algorithm.
- In common patterns, pdqsort is often faster (i.e. 10x faster in sorted slices).

The pdqsort is described at https://arxiv.org/pdf/2106.05123.pdf

This CL is inspired by both C++ implementation and Rust implementation.
- C++ implementation: https://github.com/orlp/pdqsort
- Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/

For #50154

name                   old time/op  new time/op  delta
SearchWrappers-16      72.8ns ± 3%  75.1ns ± 2%   +3.25%  (p=0.000 n=20+10)
SortString1K-16        85.2µs ± 3%  86.2µs ± 5%     ~     (p=0.247 n=19+10)
SortString1K_Slice-16  84.6µs ± 4%  86.1µs ± 4%     ~     (p=0.120 n=20+10)
StableString1K-16       112µs ± 5%   112µs ± 5%     ~     (p=0.604 n=19+10)
SortInt1K-16           44.8µs ± 3%  43.2µs ± 2%   -3.68%  (p=0.000 n=20+10)
SortInt1K_Sorted-16    28.2µs ± 3%   3.3µs ± 3%  -88.16%  (p=0.000 n=19+10)
SortInt1K_Reversed-16  29.4µs ± 3%   4.8µs ± 2%  -83.59%  (p=0.000 n=20+10)
SortInt1K_Mod8-16      25.1µs ± 2%  20.0µs ± 2%  -20.35%  (p=0.000 n=18+10)
StableInt1K-16         51.3µs ± 3%  50.9µs ± 2%     ~     (p=0.562 n=20+9)
StableInt1K_Slice-16   49.5µs ± 2%  50.7µs ± 4%   +2.55%  (p=0.009 n=19+10)
SortInt64K-16          4.73ms ± 3%  4.49ms ± 4%   -5.08%  (p=0.000 n=20+10)
SortInt64K_Slice-16    4.51ms ± 3%  4.35ms ± 1%   -3.42%  (p=0.000 n=20+8)
StableInt64K-16        4.85ms ± 2%  4.82ms ± 2%     ~     (p=0.267 n=20+10)
Sort1e2-16             27.9µs ± 1%  28.1µs ± 2%     ~     (p=0.198 n=20+10)
Stable1e2-16           56.6µs ± 2%  55.0µs ± 2%   -2.88%  (p=0.000 n=20+10)
Sort1e4-16             5.51ms ± 1%  5.36ms ± 1%   -2.58%  (p=0.000 n=19+9)
Stable1e4-16           17.8ms ± 1%  17.3ms ± 1%   -2.40%  (p=0.000 n=20+10)
Sort1e6-16              833ms ± 1%   807ms ± 1%   -3.02%  (p=0.000 n=20+10)
Stable1e6-16            3.49s ± 2%   3.44s ± 1%   -1.41%  (p=0.001 n=20+10)

Change-Id: Iecded047d237b9330b5a4101001a5fdc2f50646a
Reviewed-on: https://go-review.googlesource.com/c/go/+/371574
Reviewed-by: Emmanuel Odeke <emmanuel@orijtech.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Eli Bendersky <eliben@google.com>
  • Loading branch information
@zhangyunhao116 @gopherbot
zhangyunhao116 authored and gopherbot committed Apr 13, 2022
1 parent 9298f60 commit 72e77a7
Show file tree
Hide file tree
Showing 8 changed files with 885 additions and 366 deletions.
2 changes: 1 addition & 1 deletion src/sort/example_multi_test.go
View file
Expand Up @@ -126,7 +126,7 @@ func Example_sortMultiKeys() {
// By user: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
// By user,<lines: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
// By user,>lines: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken Go 200} {ken C 150} {r C 150} {r Go 100} {rsc Go 200}]
// By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {r Go 100} {gri Go 100} {ken Go 200} {glenda Go 200} {rsc Go 200} {gri Smalltalk 80}]
// By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}]
// By language,<lines,user: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}]

}
4 changes: 4 additions & 0 deletions src/sort/export_test.go
View file
Expand Up @@ -7,3 +7,7 @@ package sort
func Heapsort(data Interface) {
heapSort(data, 0, data.Len())
}

func ReverseRange(data Interface, a, b int) {
reverseRange(data, a, b)
}

6 comments on commit 72e77a7

@csbo98
Copy link

@csbo98 csbo98 commented on 72e77a7 Apr 21, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this is so cool!

@xerosanyam
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

power of open source! one person finds a performance improvement, the gain is trickled into all the systems across.. making whole humanity efficient.

@jxsl13
Copy link

@jxsl13 jxsl13 commented on 72e77a7 Apr 22, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

https://github.com/scandum/crumsort
claiming better performance than pdqsort.

@dskloet
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Go's previous implementation of quickSort used ShellSort on short ranges, but pdqsort only uses plain insertion sort.
Isn't ShellSort better?

https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/sort/sort.go;l=215

@yinchyu
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

all Benchmark is StopTimer() in the begin why not ResetTimer()

@ianlancetaylor
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We don't use GitHub for code review. Very few people will see comments made on this pull request. If you want to make comments on this change, please comment on https://go.dev/cl/371574. Thanks.

Please sign in to comment.