aboutsummaryrefslogtreecommitdiff
path: root/src/sort/sort.go
AgeCommit message (Collapse)Author
2026-01-15sort: improve comment readability for Stable functionPrateik Lohani
Change-Id: I3bc9f906f85e2b5f3d4ba6484e3c125065e36b57 GitHub-Last-Rev: 5d637c132533691d5a56fd00845bdb1d349642a3 GitHub-Pull-Request: golang/go#77190 Reviewed-on: https://go-review.googlesource.com/c/go/+/736501 Reviewed-by: Robert Griesemer <gri@google.com> Auto-Submit: Keith Randall <khr@golang.org> Auto-Submit: Robert Griesemer <gri@google.com> Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org>
2025-07-07sort: clarify Less docJohn Giorshev
clarifies the requirements for Less Fixes https://github.com/golang/go/issues/73420 Change-Id: I7d49b10fad78c618d946b3bb161ce19680ede47a GitHub-Last-Rev: 7a49ad81923048bfc99b265dd89f012eefcf5699 GitHub-Pull-Request: golang/go#74333 Reviewed-on: https://go-review.googlesource.com/c/go/+/683275 Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Keith Randall <khr@google.com> Reviewed-by: Carlos Amedee <carlos@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-11-02slice, sort: correct triple of xorshift RNGMeng Zhuo
The original triple is `[13,17,5]` which don't existed in the Xorshift RNG paper. This CL use the right triple `[13,7,17]` for 64 bits RNG. Fixes #70144 Change-Id: I3e3d475835980d9f28451ab73e3ce61eb2f1685e Reviewed-on: https://go-review.googlesource.com/c/go/+/624295 Reviewed-by: Eli Bendersky <eliben@google.com> Reviewed-by: Carlos Amedee <carlos@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: yunhao zhang <zhangyunhao116@gmail.com>
2024-08-21sort: drop implementation for Go <1.21Tobias Klauser
Now that Go 1.22.6 is the minimum bootstrap toolchain (cf. CL 606156), the fallback implementation for Go versions <1.21 can be dropped. For #61180 For #64751 Change-Id: Idfeca0a6e9f490e1ab0f308ead372612402923ea Reviewed-on: https://go-review.googlesource.com/c/go/+/607315 Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Commit-Queue: Tobias Klauser <tobias.klauser@gmail.com> Reviewed-by: Dmitri Shuralyov <dmitshur@golang.org> Auto-Submit: Tobias Klauser <tobias.klauser@gmail.com>
2023-11-28sort: add available godoc linkcui fliter
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>
2023-07-21sort: forward fixed-type slice sorting to slices packageEli Bendersky
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>
2023-06-13sort: comments directing new code to use the slices package when applicableEli Bendersky
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>
2022-04-13sort: use pdqsortzhangyunhao
- 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>
2022-04-01all: remove trailing blank doc comment linesRuss Cox
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>
2022-03-03sort: use a different codegen strategyEli Bendersky
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>
2021-11-16sort: improve sort documentationjiahua wang
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>
2020-10-17sort: fix grammar in updated Less commentzikaeroh
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>
2020-10-16sort: update commentsRuss Cox
- 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>
2020-10-14sort: document requirements of Less relationalandonovan
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>
2019-01-27sort: change let to let'sGiantsLoveDeathMetal
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>
2018-04-22sort: fix typo in commentTakayoshi Nishida
Change-Id: Ia2c87473d63175db6cb36a21be0769ae9fcb4f8b Reviewed-on: https://go-review.googlesource.com/108695 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
2017-10-27sort: split post-Go1.4 code into its own fileRuss Cox
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>
2017-06-01sort: clarify comment about not-a-number valuesIan Lance Taylor
Updates #20540 Change-Id: I864008fadd77b0aeb10fe7e7f1ec696516a5add5 Reviewed-on: https://go-review.googlesource.com/44492 Reviewed-by: Robert Griesemer <gri@golang.org>
2017-05-31sort: document NaN behavior for Float64Slice and friendsIan Lance Taylor
Fixes #20540 Change-Id: I440eee02d37b6921613f9ae77875d91eeec48b1e Reviewed-on: https://go-review.googlesource.com/44490 Reviewed-by: Robert Griesemer <gri@golang.org>
2017-02-10sort: optimize average calculation in symMerge and doPivot.David R. Jenni
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>
2016-10-03sort: add Slice, SliceStable, and SliceIsSortedBrad Fitzpatrick
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>
2016-03-25all: delete dead non-test codeDominik Honnef
This change removes a lot of dead code. Some of the code has never been used, not even when it was first commited. The rest shouldn't have survived refactors. This change doesn't remove unused routines helpful for debugging, nor does it remove code that's used in commented out blocks of code that are only unused temporarily. Furthermore, unused constants weren't removed when they were part of a set of constants from specifications. One noteworthy omission from this CL are about 1000 lines of unused code in cmd/fix, 700 lines of which are the typechecker, which hasn't been used ever since the pre-Go 1 fixes have been removed. I wasn't sure if this code should stick around for future uses of cmd/fix or be culled as well. Change-Id: Ib714bc7e487edc11ad23ba1c3222d1fd02e4a549 Reviewed-on: https://go-review.googlesource.com/20926 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-03-02all: single space after period.Brad Fitzpatrick
The tree's pretty inconsistent about single space vs double space after a period in documentation. Make it consistently a single space, per earlier decisions. This means contributors won't be confused by misleading precedence. This CL doesn't use go/doc to parse. It only addresses // comments. It was generated with: $ perl -i -npe 's,^(\s*// .+[a-z]\.) +([A-Z]),$1 $2,' $(git grep -l -E '^\s*//(.+\.) +([A-Z])') $ go test go/doc -update Change-Id: Iccdb99c37c797ef1f804a94b22ba5ee4b500c4f7 Reviewed-on: https://go-review.googlesource.com/20022 Reviewed-by: Rob Pike <r@golang.org> Reviewed-by: Dave Day <djd@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-02-24sort: fix for nondeterministic less function in quicksort pivotJure Ham
Fixes #14377 Change-Id: I130a6e1b8bc827db44efd0a74e759b894ecc4977 Reviewed-on: https://go-review.googlesource.com/19823 Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-02-18sort: Fix typo in stable sort commentMatt Bostock
Fix `reverences`, which I believe should read as `references`. Change-Id: I450efcbeee0f8861a84b209f2e6636764034232a Reviewed-on: https://go-review.googlesource.com/19469 Reviewed-by: Russ Cox <rsc@golang.org>
2015-12-04sort: improve average quicksort performanceRuss Cox
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>
2015-12-04Revert "sort: improve average quicksort performance"Russ Cox
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>
2015-12-04sort: improve average quicksort performanceSokolov Yura
- 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>
2015-08-17sort: Fix typo in Stable() commentMatt Bostock
Correct 'an' to 'on' in the comment above the Stable() function. Change-Id: I714e38b2d3a79dfd539d5368967d1c6b519cb948 Reviewed-on: https://go-review.googlesource.com/13662 Reviewed-by: Rob Pike <r@golang.org>
2015-02-08sort: fixed small typo in commentsFlorin Patan
There was a small typo in the comment before the Stable function. Change-Id: Ia6fa5272aa7869124a637d2eeda81c4f35ef46c8 Reviewed-on: https://go-review.googlesource.com/4201 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
2015-01-13sort: reduce number of comparisons needed by medianOfThreeMartin Möhrmann
For some cases we can ensure the correct order of elements in two instead of three comparisons. It is unnecessary to compare m0 and m1 again if m2 and m1 are not swapped. benchmark old ns/op new ns/op delta BenchmarkSortString1K 302721 299590 -1.03% BenchmarkSortInt1K 124055 123215 -0.68% BenchmarkSortInt64K 12291522 12203402 -0.72% BenchmarkSort1e2 58027 57111 -1.58% BenchmarkSort1e4 12426805 12341761 -0.68% BenchmarkSort1e6 1966250030 1960557883 -0.29% Change-Id: I2b17ff8dee310ec9ab92a6f569a95932538768a9 Reviewed-on: https://go-review.googlesource.com/2614 Reviewed-by: Robert Griesemer <gri@golang.org>
2015-01-06sort: optimize symMerge performance for blocks with one elementMartin Möhrmann
Use direct binary insertion instead of recursive calls to symMerge when one of the blocks has only one element. benchmark old ns/op new ns/op delta BenchmarkStableString1K 421999 397629 -5.77% BenchmarkStableInt1K 123422 120592 -2.29% BenchmarkStableInt64K 9629094 9620200 -0.09% BenchmarkStable1e2 123089 120209 -2.34% BenchmarkStable1e4 39505228 36870029 -6.67% BenchmarkStable1e6 8196612367 7630840157 -6.90% Change-Id: I49905a909e8595cfa05920ccf9aa00a8f3036110 Reviewed-on: https://go-review.googlesource.com/2219 Reviewed-by: Robert Griesemer <gri@golang.org>
2014-12-23sort: simplify rotate and reduce calls to itMartin Möhrmann
Move the checks for empty rotate changes from the beginning of rotate to the callers. Remove additional variable p used instead of existing m with same value. Remove special casing of equal ranges (i==j) to exit early as no work is saved vs checking (i!=j) and making a single swapRange call if this is false. benchmark old ns/op new ns/op delta BenchmarkStableString1K 417195 425218 +1.92% BenchmarkStableInt1K 126661 124498 -1.71% BenchmarkStableInt64K 10365014 10417438 +0.51% BenchmarkStable1e2 132151 130648 -1.14% BenchmarkStable1e4 42027428 40812649 -2.89% BenchmarkStable1e6 8524772364 8430192391 -1.11% Change-Id: Ia7642e9d31408496970c700f5843d53cc3ebe817 Reviewed-on: https://go-review.googlesource.com/2100 Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Ian Lance Taylor <iant@golang.org>
2014-12-22sort: reduce leaf calls in StableJosh Bleecher Snyder
Move the symMerge recursion stopping condition from the beginning of symMerge to the callers. This halves the number of calls to symMerge while running 'go test sort'. benchmark old ns/op new ns/op delta BenchmarkStable1e6 8358117060 7954143849 -4.83% BenchmarkStable1e4 40116117 38583285 -3.82% BenchmarkStableInt1K 119150 115182 -3.33% BenchmarkStableInt64K 9799845 9515475 -2.90% BenchmarkStableString1K 388901 393516 +1.19% BenchmarkStable1e2 124917 123618 -1.04% Change-Id: I7ba2ca277f213b076fe6830e1139edb47ac53800 Reviewed-on: https://go-review.googlesource.com/1820 Reviewed-by: Robert Griesemer <gri@golang.org>
2014-12-19sort: deduplicate inner loop of StableJosh Bleecher Snyder
benchmark old ns/op new ns/op delta BenchmarkStableInt1K 117212 116287 -0.79% BenchmarkStableInt64K 9632002 9587872 -0.46% BenchmarkStable1e4 40044309 39865644 -0.45% BenchmarkStable1e2 126985 126456 -0.42% BenchmarkStableString1K 389774 391052 +0.33% BenchmarkStable1e6 8183202516 8157693442 -0.31% Change-Id: I14e518ad49ecce3d1fc2b056e1acd5e5a2de8144 Reviewed-on: https://go-review.googlesource.com/1821 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
2014-09-08build: move package sources from src/pkg to srcRuss Cox
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.
generated by cgit v1.3 (git 2.53.0) at 2026-04-16 06:02:02 +0000