| Age | Commit message (Collapse) | Author |
|---|
|
Change-Id: Ibc1344b678d5f7c730b924c697717305c90c26e9
Reviewed-on: https://go-review.googlesource.com/c/go/+/569537
Commit-Queue: Ian Lance Taylor <iant@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
|
|
This allows to drop the use of deprecated rand.Seed in benchmarks.
Fixes #61142
Change-Id: I628848c0d4a500dc9a361930c393e47c3361a95c
Reviewed-on: https://go-review.googlesource.com/c/go/+/551155
Reviewed-by: Eli Bendersky <eliben@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Run-TryBot: Tobias Klauser <tobias.klauser@gmail.com>
Auto-Submit: Tobias Klauser <tobias.klauser@gmail.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
|
|
Change-Id: I64645fef0ffd1cea7c7710ec974520f85e0f7496
Reviewed-on: https://go-review.googlesource.com/c/go/+/539579
Run-TryBot: shuang cui <imcusg@gmail.com>
Reviewed-by: Bryan Mills <bcmills@google.com>
Reviewed-by: qiulaidongfeng <2645477756@qq.com>
Auto-Submit: Dmitri Shuralyov <dmitshur@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
|
|
Running 'go fix' on the cmd+std packages handled much of this change.
Also update code generators to use only the new go:build lines,
not the old +build ones.
For #41184.
For #60268.
Change-Id: If35532abe3012e7357b02c79d5992ff5ac37ca23
Cq-Include-Trybots: luci.golang.try:gotip-linux-386-longtest,gotip-linux-amd64-longtest,gotip-windows-amd64-longtest
Reviewed-on: https://go-review.googlesource.com/c/go/+/536237
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Auto-Submit: Dmitri Shuralyov <dmitshur@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
|
|
Change-Id: I9603de9abff8d5c8fb9efdf688ff1a5f8c7d19b2
GitHub-Last-Rev: c6fe3acc41a3a9c7d07e3c291985867a704013b1
GitHub-Pull-Request: golang/go#61808
Reviewed-on: https://go-review.googlesource.com/c/go/+/516635
Auto-Submit: Keith Randall <khr@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
|
|
Also add a go:generate command to the standard library slices package.
For #61374
Change-Id: I7aae8e451b7c6c4390e0344257478d1a96a14189
Reviewed-on: https://go-review.googlesource.com/c/go/+/511660
Run-TryBot: Ian Lance Taylor <iant@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Eli Bendersky <eliben@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
|
|
Forwards the following functions to the slices package:
sort.Ints
sort.Strings
sort.Float64s
sort.IntsAreSorted
sort.StringsAreSorted
sort.Float64sAreSorted
benchstat results on the sort package's benchmarks:
goos: linux
goarch: amd64
pkg: sort
cpu: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
SearchWrappers-8 58.10n ± 0% 58.43n ± 1% +0.57% (p=0.004 n=10)
SortString1K-8 76.53µ ± 1% 66.04µ ± 2% -13.71% (p=0.000 n=10)
SortString1K_Slice-8 71.99µ ± 1% 72.32µ ± 2% ~ (p=0.481 n=10)
StableString1K-8 92.66µ ± 1% 92.10µ ± 2% -0.61% (p=0.019 n=10)
SortInt1K-8 34.31µ ± 0% 11.49µ ± 2% -66.50% (p=0.000 n=10)
SortInt1K_Sorted-8 2699.5n ± 1% 959.0n ± 3% -64.47% (p=0.000 n=10)
SortInt1K_Reversed-8 3.990µ ± 1% 1.429µ ± 4% -64.19% (p=0.000 n=10)
SortInt1K_Mod8-8 13.695µ ± 1% 5.129µ ± 2% -62.55% (p=0.000 n=10)
StableInt1K-8 46.22µ ± 1% 46.80µ ± 1% ~ (p=0.109 n=10)
StableInt1K_Slice-8 44.12µ ± 1% 44.32µ ± 2% ~ (p=0.315 n=10)
SortInt64K-8 3.848m ± 0% 1.857m ± 2% -51.76% (p=0.000 n=10)
SortInt64K_Slice-8 3.690m ± 0% 3.740m ± 0% +1.36% (p=0.002 n=10)
StableInt64K-8 3.901m ± 0% 3.917m ± 0% +0.42% (p=0.003 n=10)
Sort1e2-8 32.22µ ± 2% 32.40µ ± 2% ~ (p=0.529 n=10)
Stable1e2-8 54.11µ ± 1% 54.11µ ± 1% ~ (p=0.796 n=10)
Sort1e4-8 5.998m ± 1% 5.993m ± 1% ~ (p=0.579 n=10)
Stable1e4-8 15.23m ± 0% 15.32m ± 0% +0.59% (p=0.000 n=10)
Sort1e6-8 902.8m ± 0% 904.3m ± 0% ~ (p=0.075 n=10)
Stable1e6-8 3.089 ± 0% 3.089 ± 0% ~ (p=0.971 n=10)
geomean 259.8µ 200.0µ -22.99%
Most of the benchmarks are unaffected. The ones with significant reductions
are precisely for the functions that were forwarded.
This CL has to move some things around to avoid a circular dependency
between sort and slices. Since sort depends on slices now, nothing in
slices can depend on sort - not even in tests.
Fixes #61180
Change-Id: Ic0e5f519863d96a139fada08aefb1bcdf4c7a9a3
Reviewed-on: https://go-review.googlesource.com/c/go/+/508135
Run-TryBot: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
|
|
Change-Id: I0d4e902736fb3a75d128a088901055bece6c1a71
Reviewed-on: https://go-review.googlesource.com/c/go/+/502555
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: Eli Bendersky <eliben@google.com>
Auto-Submit: Eli Bendersky <eliben@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
|
|
Now that the `cmp` package exists, sorting and comparison functions from
`x/exp/slices` can be ported to the standard library, using the
`cmp.Ordered` type and the `cmp.Less` and `cmp.Compare` functions.
This move also includes adjustments to the discussions in #60091 w.r.t.
NaN handling and cmp vs. less functions, and adds Min/Max functions.
The final API is taken from
https://github.com/golang/go/issues/60091#issuecomment-1553850782
Updates #60091
Change-Id: Id7e6c88035b60d4ddd0c48dd82add8e8bc4e22d3
Reviewed-on: https://go-review.googlesource.com/c/go/+/496078
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Eli Bendersky <eliben@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
|
|
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>
|
|
Excluding vendor and testdata.
CL 384268 already reformatted most, but these slipped past.
The struct in the doc comment in debug/dwarf/type.go
was fixed up by hand to indent the first and last lines as well.
For #51082.
Change-Id: Iad020f83aafd671ff58238fe491907e85923d0c7
Reviewed-on: https://go-review.googlesource.com/c/go/+/407137
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
|
|
In CL 371574 PatchSet 18, we replaced all !{{Less}} with {{GreaterOrEqual}} to fix a problem(handle NaNs when sorting float64 slice) in exp/slices.
We don't actually need this change, because we don't guarantee that the slice will be sorted eventually if there are NaNs(we could have a[i] < a[j] for some i,j with i>j).
This CL reverts all the replacements in exp/slices and does not affect any codes in the sort package.
Change-Id: Idc225d480de3e2efef2add35c709ed880d1306cb
Reviewed-on: https://go-review.googlesource.com/c/go/+/400534
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
Auto-Submit: Keith Randall <khr@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Eli Bendersky <eliben@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Keith Randall <khr@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>
|
|
For golang/go#50340
Change-Id: I3b4d278affc8e7ec706db8c9777f7a8c8ce7441d
Reviewed-on: https://go-review.googlesource.com/c/go/+/396514
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Trust: Cherry Mui <cherryyz@google.com>
Run-TryBot: Russ Cox <rsc@golang.org>
Auto-Submit: Russ Cox <rsc@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
|
|
A future change to gofmt will rewrite
// Doc comment.
//
func f()
to
// Doc comment.
func f()
Apply that change preemptively to all doc comments.
For #51082.
Change-Id: I4023e16cfb0729b64a8590f071cd92f17343081d
Reviewed-on: https://go-review.googlesource.com/c/go/+/384259
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
|
|
For #51698
Change-Id: Ifc5bef2cc41b163644ac80ace7c1470c8a130467
Reviewed-on: https://go-review.googlesource.com/c/go/+/393700
Trust: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Eli Bendersky <eliben@golang.org>
|
|
The existing codegen strategy in sort.go relied on parsing the sort.go source
with go/ast and a combination of an AST rewrite + code text rewrite with regexes
to generate zfuncversion -- the same sort functionality with a different variant
of data.
In preparation for implementing #47619, we need a more robust codegen
strategy. To generate variants required for the generic sort functions
in the slices package, we'd need significanly more complicated AST
rewrites, which would make genzfunc.go much heavier.
Instead, redo the codegen strategy to use text/template instead of AST rewrites.
gen_sort_variants.go now contains the code for the underlying sort functions,
and generates multiple versions of them based on Variant configuration structs.
With this approach, adding new variants to generate generic sort functions for
the slices package becomes trivial.
See the discussion in #47619 for more details on the design decisions.
Change-Id: I8af784c41b1dc8ef92aaf6321359e8faa5fe106c
Reviewed-on: https://go-review.googlesource.com/c/go/+/353069
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Trust: Than McIntosh <thanm@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>
|
|
Fixes #48527
Change-Id: Ib5df0819cbcd5c2e4f03bda841871d237af96b19
Reviewed-on: https://go-review.googlesource.com/c/go/+/351336
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
Change-Id: I5fa4773467e3f515250deead72fdce3e4bd0973b
Reviewed-on: https://go-review.googlesource.com/c/go/+/275457
Reviewed-by: Emmanuel Odeke <emmanuel@orijtech.com>
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Emmanuel Odeke <emmanuel@orijtech.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Robert Griesemer <gri@golang.org>
|
|
Make all our package sources use Go 1.17 gofmt format
(adding //go:build lines).
Part of //go:build change (#41184).
See https://golang.org/design/draft-gobuild
Change-Id: Ia0534360e4957e58cd9a18429c39d0e32a6addb4
Reviewed-on: https://go-review.googlesource.com/c/go/+/294430
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Jason A. Donenfeld <Jason@zx2c4.com>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
As part of #42026, these helpers from io/ioutil were moved to os.
(ioutil.TempFile and TempDir became os.CreateTemp and MkdirTemp.)
Update the Go tree to use the preferred names.
As usual, code compiled with the Go 1.4 bootstrap toolchain
and code vendored from other sources is excluded.
ReadDir changes are in a separate CL, because they are not a
simple search and replace.
For #42026.
Change-Id: If318df0216d57e95ea0c4093b89f65e5b0ababb3
Reviewed-on: https://go-review.googlesource.com/c/go/+/266365
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
The rewritten comment didn't sound right to my ears. Tweak it to be
grammatically correct.
Change-Id: Iae7d9f8810fff78cfd964bb3117099bce4479c14
Reviewed-on: https://go-review.googlesource.com/c/go/+/263180
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Trust: Robert Griesemer <gri@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>
|
|
Fixes #34915
Change-Id: Ia62ff3b6f198ddcd79e8afc7b4f5514a44f2442c
Reviewed-on: https://go-review.googlesource.com/c/go/+/261959
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Akhil Indurti <aindurti@gmail.com>
Trust: Alberto Donizetti <alb.donizetti@gmail.com>
|
|
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>
|
|
Change-Id: I4f8d0178e780b86d1f551b367e2ddac3789be5aa
Reviewed-on: https://go-review.googlesource.com/c/go/+/168880
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
Trivial typo
Change-Id: I3804f365519453bfa19997f55ead34742ac1a9db
GitHub-Last-Rev: 0e04e928d05121099b78a2cefc1cb7531f6a7650
GitHub-Pull-Request: golang/go#29930
Reviewed-on: https://go-review.googlesource.com/c/159479
Reviewed-by: Emmanuel Odeke <emm.odeke@gmail.com>
|
|
Each URL was manually verified to ensure it did not serve up incorrect
content.
Change-Id: I4dc846227af95a73ee9a3074d0c379ff0fa955df
Reviewed-on: https://go-review.googlesource.com/115798
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
|
|
Change-Id: Ia2c87473d63175db6cb36a21be0769ae9fcb4f8b
Reviewed-on: https://go-review.googlesource.com/108695
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
Change-Id: If9ad8ae663f007efe43cc35631713565fa754e93
Reviewed-on: https://go-review.googlesource.com/93237
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
I found files to change with this command:
git grep 'DO NOT EDIT' | grep -v 'Code generated .* DO NOT'
There are more files that match that grep, but I do not intend on fixing
them.
Change-Id: I4b474f1c29ca3135560d414785b0dbe0d1a4e52c
GitHub-Last-Rev: 65804b02634abd85bf113788b38354d48801241f
GitHub-Pull-Request: golang/go#24334
Reviewed-on: https://go-review.googlesource.com/99955
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@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>
|
|
This is to let sort.Slice get more prominence since
it's the most common use case.
Fixes #21989
Change-Id: I0b180cc20256f5f09065b722e191c508c872f4f7
Reviewed-on: https://go-review.googlesource.com/65710
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Change-Id: Ib4883470bd2271e546daea3156d4a48dd873aaa3
Reviewed-on: https://go-review.googlesource.com/57670
Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
Run-TryBot: Joe Tsai <thebrokentoaster@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
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>
|
|
There are some major problems with TestAdversary (based on "A Killer
Adversary for Quicksort"[1] by M. D. McIlroy). See #21581 for details.
Rewrite the test to closely match the version in the paper so it can
be verified as correct by virtue of similarity.
The only major difference between this new version and the version in
the paper is that this version swaps the values directly instead of
permuting an array of indices because we don't need to recover the
original permutation.
This new version also counts the number of calls to Less() and fails
the test if there are too many.
Fixes #21581.
[1]: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
Change-Id: Ia94b5b6d288b8fa3805a5fa27661cebbc5bad9a7
Reviewed-on: https://go-review.googlesource.com/58330
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
Change-Id: I33f0e2362e85287b493d9279d43b760733e2abcb
Reviewed-on: https://go-review.googlesource.com/48831
Run-TryBot: Bryan Mills <bcmills@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Bryan Mills <bcmills@google.com>
|
|
Done with grep & interactive search & replace, to double-check
replacements. Not many remained after CL 20022.
Fixes #18572
Change-Id: Idbe90ba3b584f9b9661d2bbd141607daaadfa41a
Reviewed-on: https://go-review.googlesource.com/45270
Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
|
|
Updates #20540
Change-Id: I864008fadd77b0aeb10fe7e7f1ec696516a5add5
Reviewed-on: https://go-review.googlesource.com/44492
Reviewed-by: Robert Griesemer <gri@golang.org>
|
|
Fixes #20540
Change-Id: I440eee02d37b6921613f9ae77875d91eeec48b1e
Reviewed-on: https://go-review.googlesource.com/44490
Reviewed-by: Robert Griesemer <gri@golang.org>
|
|
ExampleSliceStable echoes the sort.Slice example, to demonstrate sorting
on two fields together preserving order between sorts.
Change-Id: I8afc20c0203991bfd57260431eda73913c165355
Reviewed-on: https://go-review.googlesource.com/37196
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Change code of the form `i + (j-i)/2` to `int(uint(i+j) >> 1)`.
The optimized average calculation uses fewer instructions to calculate
the average without overflowing at the addition.
Analogous to https://golang.org/cl/36332.
name old time/op new time/op delta
StableString1K-4 49.6µs ± 3% 49.1µs ± 8% ~ (p=0.659 n=16+19)
StableInt1K-4 160µs ±10% 148µs ± 5% -7.29% (p=0.000 n=20+16)
StableInt1K_Slice-4 139µs ± 4% 136µs ± 3% -2.52% (p=0.000 n=20+16)
StableInt64K-4 8.84ms ± 6% 8.57ms ± 5% -3.07% (p=0.001 n=20+19)
Stable1e2-4 162µs ±19% 147µs ±16% -8.79% (p=0.002 n=20+20)
Stable1e4-4 31.0ms ± 5% 30.6ms ± 5% ~ (p=0.221 n=20+20)
Stable1e6-4 6.37s ± 3% 6.27s ± 2% -1.67% (p=0.000 n=19+20)
Change-Id: I1cea0bcb9ace8ef7e48b8fab772e41b4b2170da9
Reviewed-on: https://go-review.googlesource.com/36570
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
Use fewer instructions to calculate the average of i and j without
overflowing at the addition.
Even if both i and j are math.MaxInt{32,64}, the sum fits into a
uint{32,64}. Because the sum of i and j is always ≥ 0, the right
shift by one does the same as a division by two. The result of the
shift operation is at most math.MaxInt{32,64} and fits again into
an int{32,64}.
name old time/op new time/op delta
SearchWrappers-4 153ns ± 3% 143ns ± 6% -6.33% (p=0.000 n=90+100)
This calculation is documented in:
https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
Change-Id: I2be7922afc03b3617fce32e59364606c37a83678
Reviewed-on: https://go-review.googlesource.com/36332
Reviewed-by: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Change-Id: I34ba4eaf1d232b639998ad3bbb0d075dd097722b
Reviewed-on: https://go-review.googlesource.com/33763
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Dominik Honnef <dominik@honnef.co>
|
|
Change-Id: I9783d8023d453a72c4605a308064bef98168bcb8
Reviewed-on: https://go-review.googlesource.com/30360
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Add helpers for sorting slices.
Slice sorts slices:
sort.Slice(s, func(i, j int) bool {
if s[i].Foo != s[j].Foo {
return s[i].Foo < s[j].Foo
}
return s[i].Bar < s[j].Bar
})
SliceStable is the same, but does a stable sort.
SliceIsSorted reports whether a slice is already sorted.
Fixes #16721
Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7
Reviewed-on: https://go-review.googlesource.com/27321
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
Change-Id: I27b82d8c63a06ddf7e148b15853aba24a22a6282
Reviewed-on: https://go-review.googlesource.com/29336
Reviewed-by: Joe Tsai <thebrokentoaster@gmail.com>
Run-TryBot: Joe Tsai <thebrokentoaster@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
This adds examples showing the different ways of using sort.Search.
Change-Id: Iaa08b4501691f37908317fdcf2e618fbe9f99ade
Reviewed-on: https://go-review.googlesource.com/29131
Reviewed-by: Andrew Gerrand <adg@golang.org>
Run-TryBot: Andrew Gerrand <adg@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
