delta/go-git.git/src/sort, branch dev.boringcrypto

slices: use !{{Less}} instead of {{GreaterOrEqual}}

2022-04-25T19:12:14+00:00

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 
Run-TryBot: Keith Randall 
Auto-Submit: Keith Randall 
TryBot-Result: Gopher Robot 
Reviewed-by: Eli Bendersky 
Reviewed-by: Keith Randall 
Auto-Submit: Keith Randall

sort: use pdqsort

2022-04-13T20:16:24+00:00

- 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 
Run-TryBot: Ian Lance Taylor 
Reviewed-by: Keith Randall 
Run-TryBot: Keith Randall 
Auto-Submit: Keith Randall 
Reviewed-by: Keith Randall 
TryBot-Result: Gopher Robot 
Reviewed-by: Eli Bendersky

sort: add Find function

2022-04-07T14:42:13+00:00

For golang/go#50340

Change-Id: I3b4d278affc8e7ec706db8c9777f7a8c8ce7441d
Reviewed-on: https://go-review.googlesource.com/c/go/+/396514
Reviewed-by: Ian Lance Taylor 
Trust: Cherry Mui 
Run-TryBot: Russ Cox 
Auto-Submit: Russ Cox 
TryBot-Result: Gopher Robot

all: remove trailing blank doc comment lines

2022-04-01T18:18:07+00:00

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 
Run-TryBot: Russ Cox 
Reviewed-by: Ian Lance Taylor 
TryBot-Result: Gopher Robot

sort: generate generic variants with E rather than Elem

2022-03-18T19:32:40+00:00

For #51698

Change-Id: Ifc5bef2cc41b163644ac80ace7c1470c8a130467
Reviewed-on: https://go-review.googlesource.com/c/go/+/393700
Trust: Ian Lance Taylor 
Run-TryBot: Ian Lance Taylor 
TryBot-Result: Gopher Robot 
Reviewed-by: Eli Bendersky‎

sort: use a different codegen strategy

2022-03-03T13:42:02+00:00

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 
Run-TryBot: Ian Lance Taylor 
TryBot-Result: Gopher Robot 
Trust: Than McIntosh

all: gofmt -w -r 'interface{} -> any' src

2021-12-13T18:45:54+00:00

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 
Run-TryBot: Russ Cox 
Reviewed-by: Robert Griesemer 
TryBot-Result: Gopher Robot

sort: improve sort documentation

2021-11-16T23:13:41+00:00

Fixes #48527

Change-Id: Ib5df0819cbcd5c2e4f03bda841871d237af96b19
Reviewed-on: https://go-review.googlesource.com/c/go/+/351336
Reviewed-by: Rob Pike 
Reviewed-by: Ian Lance Taylor

sort: add example tests for SearchFloat64s and SearchInts

2021-03-18T08:25:24+00:00

Change-Id: I5fa4773467e3f515250deead72fdce3e4bd0973b
Reviewed-on: https://go-review.googlesource.com/c/go/+/275457
Reviewed-by: Emmanuel Odeke 
Reviewed-by: Robert Griesemer 
Run-TryBot: Emmanuel Odeke 
TryBot-Result: Go Bot 
Trust: Robert Griesemer

all: go fmt std cmd (but revert vendor)

2021-02-20T03:54:50+00:00

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 
Run-TryBot: Russ Cox 
TryBot-Result: Go Bot 
Reviewed-by: Jason A. Donenfeld 
Reviewed-by: Ian Lance Taylor