Skip to content

Commit 72e77a7

Browse files
zhangyunhao116gopherbot
zhangyunhao116
authored and
gopherbot
committed
sort: use pdqsort
- 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 <[email protected]> Run-TryBot: Ian Lance Taylor <[email protected]> Reviewed-by: Keith Randall <[email protected]> Run-TryBot: Keith Randall <[email protected]> Auto-Submit: Keith Randall <[email protected]> Reviewed-by: Keith Randall <[email protected]> TryBot-Result: Gopher Robot <[email protected]> Reviewed-by: Eli Bendersky <[email protected]>
1 parent 9298f60 commit 72e77a7

8 files changed

Lines changed: 885 additions & 366 deletions

File tree

‎src/sort/example_multi_test.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -126,7 +126,7 @@ func Example_sortMultiKeys() {
126126
// 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}]
127127
// 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}]
128128
// 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}]
129-
// 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}]
129+
// 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}]
130130
// 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}]
131131

132132
}

‎src/sort/export_test.go‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,3 +7,7 @@ package sort
77
func Heapsort(data Interface) {
88
heapSort(data, 0, data.Len())
99
}
10+
11+
func ReverseRange(data Interface, a, b int) {
12+
reverseRange(data, a, b)
13+
}

0 commit comments

Comments
 (0)