| Age | Commit message (Collapse) | Author |
|---|
|
The Go bootstrap toolchain requirement is now Go 1.17.
We can finally delete all these pre-Go 1.17 workarounds.
For #44505.
Change-Id: I59d4dff1cde23da022892b5b6a116eb3dbad9ce4
Reviewed-on: https://go-review.googlesource.com/c/go/+/420903
Auto-Submit: Dmitri Shuralyov <dmitshur@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
|
|
- 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>
|
|
And then revert the bootstrap cmd directories and certain testdata.
And adjust tests as needed.
Not reverting the changes in std that are bootstrapped,
because some of those changes would appear in API docs,
and we want to use any consistently.
Instead, rewrite 'any' to 'interface{}' in cmd/dist for those directories
when preparing the bootstrap copy.
A few files changed as a result of running gofmt -w
not because of interface{} -> any but because they
hadn't been updated for the new //go:build lines.
Fixes #49884.
Change-Id: Ie8045cba995f65bd79c694ec77a1b3d1fe01bb09
Reviewed-on: https://go-review.googlesource.com/c/go/+/368254
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
|
|
- Describe requirements on Less more precisely.
- Standardize on x for the variable name of the data being sorted
(was variously a, p, slice).
- Many other minor wording changes.
Fixes #41951.
Change-Id: Ic9e222a53ec035fcc3b5ddfc7f0eefbe1bb2890d
Reviewed-on: https://go-review.googlesource.com/c/go/+/262657
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
|
|
We compile package sort as part of the compiler bootstrap,
to make sure the compiler uses a consistent sort algorithm
no matter what version of Go it is compiled against.
(This matters for elements that compare "equal" but are distinguishable.)
Package sort was compiled in such a way as to disallow
sort.Slice entirely during bootstrap (at least with some compilers),
while cmd/internal/obj was compiled in such a way as to
make obj.SortSlice available to all compilers, precisely because
sort.Slice was not. This is all highly confusing.
Simplify by making sort.Slice available all the time.
Followup to CL 169137 and #30440
(and also CL 40114 and CL 73951).
Change-Id: I127f4e02d6c71392805d256c3a90ef7c51f9ba0c
Reviewed-on: https://go-review.googlesource.com/c/go/+/174525
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
Now the net package is back to no longer depending on unicode. And lock that in
with a test.
Fixes #30440
Change-Id: I18b89b02f7d96488783adc07308da990f505affd
Reviewed-on: https://go-review.googlesource.com/c/go/+/169137
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
This will let us build the latest sort when bootstrapping the compiler.
The compiler depends on the precise tie-breaks used by sort in
some cases, and it's easier to bring sort along than require checking
every sort call ever added to the compiler.
Change-Id: Idc622f89aedbb40d848708c76650fc28779d0c3c
Reviewed-on: https://go-review.googlesource.com/73951
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
|
