| Age | Commit message (Collapse) | Author |
|---|
|
Change-Id: I07e7c8eaa5bd4bac0d576b2f2f4cd3f81b0b77a4
Reviewed-on: https://go-review.googlesource.com/c/go/+/630055
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Commit-Queue: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Russ Cox <rsc@golang.org>
Auto-Submit: Ian Lance Taylor <iant@google.com>
|
|
- 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>
|
|
If Less(a, b) returns true when a is less than b, the correct way to
check if a is greater than b is to use Less(b, a). It is wrong to use
!Less(a, b) because that checks if a is greater than *or equal to* b.
1. The decreasingDistance function in Example_sortKeys makes this
mistake. Fix it.
2. The documentation of multiSorter.Less says it loops along the less
functions until it finds a comparison "that is either Less or
!Less". This is nonsense, because (Less(a, b) or !Less(a, b)) is
always true. Fix the documentation to say that it finds a
comparison "that discriminates between the two items (one is less
than the other)". The implementation already does this correctly.
Change-Id: If52b79f68e4fdb0d1095edf29bdecdf154a61b8d
Reviewed-on: https://go-review.googlesource.com/57752
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Revert "Revert "sort: improve average quicksort performance""
This reverts commit 30b87bb9aa0c6658830f3d111920e2f366476644.
See https://golang.org/cl/15688 for the CL being replayed.
Change-Id: I2ba36334003f4971f95a10536adfdd86be9a50de
Reviewed-on: https://go-review.googlesource.com/17389
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
Broke the build: http://build.golang.org/log/8159de7e0d6f3832da394c310975ddd4c4c74627
(cmd/gofmt TestRewrite)
This reverts commit 6f6b2f04b5c342edf70944e60c9c9a30eef5a9eb.
Change-Id: Ifd46b0b76c30b0a568521eaaf5ef8968a9549bf5
Reviewed-on: https://go-review.googlesource.com/17383
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
- change way of protection from O(N^2) on duplicate values.
Previous algorithm does additional comparisons and swaps
on every split pass.
Changed algorithm does one ordinal quicksort split pass,
and if distribution is skewed, then additional pass to
separate pivot's duplicates.
Changed algorithm could be slower on very ununique slice,
but it is still protected from O(N^2).
- increase small slice size and do simple shell sort pass
to amortize worst case on small slices.
Small slice has higher probability to have skewed
distribution, so lets sort it with simpler algorithm.
benchmark old ns/op new ns/op delta
BenchmarkSortString1K 458374 388641 -15.21%
BenchmarkSortInt1K 217851 181796 -16.55%
BenchmarkSortInt64K 20539264 16730340 -18.54%
BenchmarkSort1e2 98668 95554 -3.16%
BenchmarkSort1e4 20278500 18316829 -9.67%
BenchmarkSort1e6 3215724392 2795999911 -13.05%
number of operations:
Size: Total: Swap: Less:
% % %
Sort 100 Avg -5.98% -18.43% -1.90%
Sort 100 Max -14.43% -16.02% -4.51%
Sort 300 Avg -7.50% -12.76% -5.96%
Sort 300 Max -11.29% -9.60% -4.30%
Sort 1000 Avg -12.13% -11.65% -12.25%
Sort 1000 Max -13.81% -11.77% -11.89%
Sort 3000 Avg -14.61% -9.30% -15.86%
Sort 3000 Max -15.81% -8.66% -15.19%
Sort 10000 Avg -16.10% -8.47% -17.80%
Sort 10000 Max -17.13% -7.63% -16.97%
Sort 30000 Avg -17.46% -7.56% -19.57%
Sort 30000 Max -18.24% -7.62% -17.68%
Sort 100000 Avg -18.83% -6.64% -21.33%
Sort 100000 Max -19.72% -6.70% -20.96%
Sort 300000 Avg -19.61% -6.16% -22.30%
Sort 300000 Max -20.69% -6.15% -21.81%
Sort 1000000 Avg -20.42% -5.58% -23.31%
Sort 1000000 Max -21.54% -5.56% -23.61%
Change-Id: I23868e8b52b5841b358cd5403967c9a97871e4d5
Reviewed-on: https://go-review.googlesource.com/15688
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
Preparation was in CL 134570043.
This CL contains only the effect of 'hg mv src/pkg/* src'.
For more about the move, see golang.org/s/go14nopkg.
|
