| commit | d81a07b7e58487eed036bf115fa834653590d6cd | [log] [tgz] |
|---|---|---|
| author | Russ Cox <rsc@golang.org> | Thu May 09 23:11:12 2019 -0400 |
| committer | Russ Cox <rsc@golang.org> | Mon May 13 18:47:35 2019 +0000 |
| tree | cff0dcee79772e10aa19892c607fbb14e5e5432e | |
| parent | 8696927a2839210fb998cd751a78f8609855a381 [diff] |
go/analysis/passes/bools: eliminate quadratic runtime, output
If you have x == 1 || x == 2 || x == 3 || x == 4, the pass considered the set
{x==1, x==2, x==3, x==4}
and then also
{x==2, x==3, x==4}
{x==3, x==4}
Since the comparison is itself linear in the size of the set, this was overall
taking time quadratic in the length of the || or && sequence.
Worse, if it found duplicates, they'd be reported a quadratic number of times.
This CL cuts the time and output to linear by avoiding already-checked
subexpressions. This cuts the time spent analyzing cmd/compile/internal/ssa
(with all passes enabled, not just this one) by 20%.
Fixes golang/go#28086.
Change-Id: I812f64bd5a44fea995c9ab0c4fa2fbefb44037ce
Reviewed-on: https://go-review.googlesource.com/c/tools/+/176457
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Alan Donovan <adonovan@google.com>
This subrepository holds the source for various packages and tools that support the Go programming language.
Some of the tools, godoc and vet for example, are included in binary Go distributions.
Others, including the Go guru and the test coverage tool, can be fetched with go get.
Packages include a type-checker for Go and an implementation of the Static Single Assignment form (SSA) representation for Go programs.
The easiest way to install is to run go get -u golang.org/x/tools/.... You can also manually git clone the repository to $GOPATH/src/golang.org/x/tools.
This repository uses Gerrit for code changes. To learn how to submit changes to this repository, see https://golang.org/doc/contribute.html.
The main issue tracker for the tools repository is located at https://github.com/golang/go/issues. Prefix your issue with “x/tools/(your subdir):” in the subject line, so it is easy to find.