Go will use pdqsort in next release

use pdqsort · golang/go@72e77a7 · GitHub Permalink

Browse files

- 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]>