path{,/filepath}: speed up Match

This change adds benchmarks for Match and speeds it up by simplifying
scanChunk (to the point of making it inlineable) and eliminating some
branches in matchChunk.

Here are some benchmark results (no change to allocations):

goos: darwin
goarch: amd64
pkg: path
cpu: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
                                          │     old      │                 new2                 │
                                          │    sec/op    │    sec/op     vs base                │
Match/"abc"_"abc"-8                          24.64n ± 6%   21.30n ±  1%  -13.53% (p=0.000 n=10)
Match/"*"_"abc"-8                            9.117n ± 3%   8.345n ±  2%   -8.47% (p=0.000 n=10)
Match/"*c"_"abc"-8                           29.59n ± 3%   29.86n ±  3%        ~ (p=0.055 n=10)
Match/"a*"_"a"-8                             22.88n ± 2%   20.66n ±  1%   -9.68% (p=0.000 n=10)
Match/"a*"_"abc"-8                           23.57n ± 1%   21.59n ±  0%   -8.40% (p=0.000 n=10)
Match/"a*"_"ab/c"-8                          23.18n ± 1%   21.48n ±  1%   -7.35% (p=0.000 n=10)
Match/"a*/b"_"abc/b"-8                       54.96n ± 1%   52.06n ±  0%   -5.29% (p=0.000 n=10)
Match/"a*/b"_"a/c/b"-8                       34.50n ± 3%   31.42n ±  2%   -8.91% (p=0.000 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxe/f"-8         125.4n ± 1%   114.9n ±  1%   -8.45% (p=0.000 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxexxx/f"-8      151.1n ± 1%   149.4n ±  1%   -1.09% (p=0.001 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxe/xxx/f"-8     127.8n ± 4%   115.6n ±  3%   -9.51% (p=0.000 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxexxx/fff"-8    155.6n ± 1%   168.0n ± 11%        ~ (p=0.143 n=10)
Match/"a*b?c*x"_"abxbbxdbxebxczzx"-8         189.2n ± 1%   193.5n ±  6%        ~ (p=1.000 n=10)
Match/"a*b?c*x"_"abxbbxdbxebxczzy"-8         196.3n ± 1%   190.6n ±  2%   -2.93% (p=0.001 n=10)
Match/"ab[c]"_"abc"-8                        39.50n ± 1%   37.84n ±  1%   -4.20% (p=0.000 n=10)
Match/"ab[b-d]"_"abc"-8                      47.94n ± 1%   45.99n ±  1%   -4.06% (p=0.000 n=10)
Match/"ab[e-g]"_"abc"-8                      49.48n ± 1%   47.57n ±  1%   -3.85% (p=0.000 n=10)
Match/"ab[^c]"_"abc"-8                       41.55n ± 1%   38.01n ±  2%   -8.51% (p=0.000 n=10)
Match/"ab[^b-d]"_"abc"-8                     50.48n ± 1%   46.35n ±  0%   -8.17% (p=0.000 n=10)
Match/"ab[^e-g]"_"abc"-8                     50.12n ± 3%   47.37n ±  2%   -5.47% (p=0.000 n=10)
Match/"a\\*b"_"a*b"-8                        24.59n ± 0%   21.77n ±  1%  -11.47% (p=0.000 n=10)
Match/"a\\*b"_"ab"-8                         26.14n ± 1%   24.52n ±  3%   -6.18% (p=0.000 n=10)
Match/"a?b"_"a☺b"-8                          25.66n ± 2%   23.40n ±  1%   -8.81% (p=0.000 n=10)
Match/"a[^a]b"_"a☺b"-8                       41.14n ± 0%   38.97n ±  3%   -5.29% (p=0.001 n=10)
Match/"a???b"_"a☺b"-8                        39.66n ± 6%   36.63n ±  6%   -7.63% (p=0.003 n=10)
Match/"a[^a][^a][^a]b"_"a☺b"-8               85.07n ± 8%   84.97n ±  1%        ~ (p=0.971 n=10)
Match/"[a-ζ]*"_"α"-8                         49.45n ± 4%   48.34n ±  2%   -2.23% (p=0.001 n=10)
Match/"*[a-ζ]"_"A"-8                         67.67n ± 3%   70.53n ±  2%   +4.23% (p=0.000 n=10)
Match/"a?b"_"a/b"-8                          26.61n ± 5%   25.92n ±  1%   -2.59% (p=0.000 n=10)
Match/"a*b"_"a/b"-8                          29.38n ± 3%   26.61n ±  2%   -9.46% (p=0.000 n=10)
Match/"[\\]a]"_"]"-8                         40.75n ± 3%   39.31n ±  2%   -3.52% (p=0.000 n=10)
Match/"[\\-]"_"-"-8                          30.58n ± 1%   30.53n ±  2%        ~ (p=0.565 n=10)
Match/"[x\\-]"_"x"-8                         41.02n ± 2%   39.32n ±  1%   -4.13% (p=0.000 n=10)
Match/"[x\\-]"_"-"-8                         40.74n ± 2%   39.82n ±  1%   -2.25% (p=0.000 n=10)
Match/"[x\\-]"_"z"-8                         42.19n ± 1%   40.47n ±  1%   -4.08% (p=0.001 n=10)
Match/"[\\-x]"_"x"-8                         40.77n ± 1%   39.61n ±  3%   -2.86% (p=0.000 n=10)
Match/"[\\-x]"_"-"-8                         40.94n ± 2%   39.39n ±  0%   -3.79% (p=0.000 n=10)
Match/"[\\-x]"_"a"-8                         42.12n ± 2%   42.11n ±  1%        ~ (p=0.954 n=10)
Match/"[]a]"_"]"-8                           23.73n ± 2%   21.67n ±  2%   -8.72% (p=0.000 n=10)
Match/"[-]"_"-"-8                            21.28n ± 1%   19.96n ±  1%   -6.16% (p=0.000 n=10)
Match/"[x-]"_"x"-8                           28.96n ± 1%   27.98n ±  3%   -3.37% (p=0.000 n=10)
Match/"[x-]"_"-"-8                           29.46n ± 2%   29.27n ±  7%        ~ (p=0.796 n=10)
Match/"[x-]"_"z"-8                           29.14n ± 0%   30.78n ±  9%        ~ (p=0.468 n=10)
Match/"[-x]"_"x"-8                           23.62n ± 3%   22.08n ±  1%   -6.54% (p=0.000 n=10)
Match/"[-x]"_"-"-8                           23.70n ± 2%   22.11n ±  2%   -6.69% (p=0.000 n=10)
Match/"[-x]"_"a"-8                           23.71n ± 0%   22.09n ±  3%   -6.83% (p=0.000 n=10)
Match/"\\"_"a"-8                            11.845n ± 2%   9.496n ±  3%  -19.83% (p=0.000 n=10)
Match/"[a-b-c]"_"a"-8                        39.85n ± 1%   40.69n ±  1%   +2.10% (p=0.000 n=10)
Match/"["_"a"-8                              18.57n ± 3%   16.47n ±  3%  -11.33% (p=0.000 n=10)
Match/"[^"_"a"-8                             20.30n ± 3%   17.96n ±  1%  -11.53% (p=0.000 n=10)
Match/"[^bc"_"a"-8                           36.81n ± 7%   32.87n ±  2%  -10.72% (p=0.000 n=10)
Match/"a["_"a"-8                             20.11n ± 1%   19.41n ±  1%   -3.46% (p=0.000 n=10)
Match/"a["_"ab"-8                            23.19n ± 2%   21.80n ±  1%   -6.02% (p=0.000 n=10)
Match/"a["_"x"-8                             20.79n ± 1%   19.51n ±  1%   -6.13% (p=0.000 n=10)
Match/"a/b["_"x"-8                           29.80n ± 0%   28.36n ±  0%   -4.82% (p=0.000 n=10)
Match/"*x"_"xxx"-8                           30.77n ± 2%   28.55n ±  2%   -7.23% (p=0.000 n=10)
geomean                                      37.11n        35.15n         -5.29%

pkg: path/filepath
                                          │      old      │                new2                 │
                                          │    sec/op     │   sec/op     vs base                │
Match/"abc"_"abc"-8                          22.79n ±  3%   21.62n ± 1%   -5.11% (p=0.000 n=10)
Match/"*"_"abc"-8                           11.410n ±  3%   9.595n ± 1%  -15.91% (p=0.000 n=10)
Match/"*c"_"abc"-8                           29.69n ±  2%   29.09n ± 0%   -2.00% (p=0.001 n=10)
Match/"a*"_"a"-8                             23.69n ±  1%   21.12n ± 1%  -10.83% (p=0.000 n=10)
Match/"a*"_"abc"-8                           25.38n ±  4%   22.41n ± 5%  -11.70% (p=0.000 n=10)
Match/"a*"_"ab/c"-8                          24.73n ±  1%   21.85n ± 3%  -11.65% (p=0.000 n=10)
Match/"a*/b"_"abc/b"-8                       53.73n ±  2%   53.30n ± 2%   -0.82% (p=0.037 n=10)
Match/"a*/b"_"a/c/b"-8                       32.97n ±  2%   31.64n ± 0%   -4.02% (p=0.000 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxe/f"-8         120.7n ±  0%   124.0n ± 1%   +2.82% (p=0.000 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxexxx/f"-8      149.4n ±  2%   160.0n ± 6%   +7.13% (p=0.009 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxe/xxx/f"-8     121.8n ±  2%   122.8n ± 9%        ~ (p=0.898 n=10)
Match/"a*b*c*d*e*/f"_"axbxcxdxexxx/fff"-8    149.7n ±  1%   151.2n ± 2%   +1.04% (p=0.005 n=10)
Match/"a*b?c*x"_"abxbbxdbxebxczzx"-8         187.8n ±  1%   184.8n ± 1%   -1.57% (p=0.001 n=10)
Match/"a*b?c*x"_"abxbbxdbxebxczzy"-8         195.6n ±  1%   191.2n ± 2%   -2.22% (p=0.018 n=10)
Match/"ab[c]"_"abc"-8                        40.30n ±  4%   37.31n ± 3%   -7.41% (p=0.000 n=10)
Match/"ab[b-d]"_"abc"-8                      47.92n ±  4%   45.92n ± 4%   -4.17% (p=0.002 n=10)
Match/"ab[e-g]"_"abc"-8                      47.58n ±  4%   45.22n ± 0%   -4.98% (p=0.000 n=10)
Match/"ab[^c]"_"abc"-8                       40.33n ±  2%   36.95n ± 2%   -8.38% (p=0.000 n=10)
Match/"ab[^b-d]"_"abc"-8                     48.68n ±  2%   46.49n ± 3%   -4.50% (p=0.001 n=10)
Match/"ab[^e-g]"_"abc"-8                     49.11n ±  2%   48.42n ± 2%   -1.42% (p=0.014 n=10)
Match/"a\\*b"_"a*b"-8                        26.79n ±  9%   23.70n ± 1%  -11.53% (p=0.000 n=10)
Match/"a\\*b"_"ab"-8                         23.84n ± 11%   25.99n ± 1%   +9.02% (p=0.015 n=10)
Match/"a?b"_"a☺b"-8                          25.72n ±  2%   23.70n ± 1%   -7.87% (p=0.000 n=10)
Match/"a[^a]b"_"a☺b"-8                       41.72n ±  2%   39.24n ± 2%   -5.94% (p=0.000 n=10)
Match/"a???b"_"a☺b"-8                        35.94n ±  1%   35.30n ± 3%   -1.78% (p=0.009 n=10)
Match/"a[^a][^a][^a]b"_"a☺b"-8               82.17n ±  0%   84.56n ± 3%   +2.91% (p=0.000 n=10)
Match/"[a-ζ]*"_"α"-8                         52.01n ±  3%   49.78n ± 0%   -4.30% (p=0.000 n=10)
Match/"*[a-ζ]"_"A"-8                         65.62n ±  1%   66.91n ± 3%   +1.97% (p=0.000 n=10)
Match/"a?b"_"a/b"-8                          24.60n ±  2%   25.60n ± 1%   +4.07% (p=0.001 n=10)
Match/"a*b"_"a/b"-8                          28.00n ±  1%   26.50n ± 1%   -5.37% (p=0.000 n=10)
Match/"[\\]a]"_"]"-8                         40.72n ±  1%   39.55n ± 2%   -2.86% (p=0.002 n=10)
Match/"[\\-]"_"-"-8                          30.52n ±  2%   30.15n ± 1%   -1.18% (p=0.003 n=10)
Match/"[x\\-]"_"x"-8                         40.69n ±  1%   40.41n ± 2%        ~ (p=0.105 n=10)
Match/"[x\\-]"_"-"-8                         40.50n ±  2%   40.69n ± 2%        ~ (p=0.109 n=10)
Match/"[x\\-]"_"z"-8                         40.80n ±  3%   39.92n ± 2%   -2.17% (p=0.002 n=10)
Match/"[\\-x]"_"x"-8                         40.73n ±  2%   43.78n ± 5%   +7.49% (p=0.003 n=10)
Match/"[\\-x]"_"-"-8                         40.86n ±  2%   39.58n ± 9%        ~ (p=0.105 n=10)
Match/"[\\-x]"_"a"-8                         40.67n ±  0%   40.85n ± 3%        ~ (p=0.288 n=10)
Match/"[]a]"_"]"-8                           22.71n ±  1%   20.35n ± 2%  -10.37% (p=0.000 n=10)
Match/"[-]"_"-"-8                            20.98n ±  2%   19.71n ± 2%   -6.10% (p=0.000 n=10)
Match/"[x-]"_"x"-8                           30.78n ±  1%   26.29n ± 1%  -14.56% (p=0.000 n=10)
Match/"[x-]"_"-"-8                           30.79n ±  2%   26.38n ± 3%  -14.29% (p=0.000 n=10)
Match/"[x-]"_"z"-8                           30.77n ±  0%   26.47n ± 1%  -13.97% (p=0.000 n=10)
Match/"[-x]"_"x"-8                           23.73n ±  1%   21.08n ± 1%  -11.19% (p=0.000 n=10)
Match/"[-x]"_"-"-8                           23.68n ±  1%   21.11n ± 3%  -10.81% (p=0.000 n=10)
Match/"[-x]"_"a"-8                           23.74n ±  3%   21.04n ± 0%  -11.37% (p=0.000 n=10)
Match/"\\"_"a"-8                             11.57n ±  0%   10.35n ± 0%  -10.63% (p=0.000 n=10)
Match/"[a-b-c]"_"a"-8                        42.46n ±  1%   38.97n ± 3%   -8.23% (p=0.000 n=10)
Match/"["_"a"-8                              18.03n ±  7%   15.95n ± 1%  -11.51% (p=0.000 n=10)
Match/"[^"_"a"-8                             19.20n ± 11%   17.96n ± 3%   -6.41% (p=0.000 n=10)
Match/"[^bc"_"a"-8                           32.82n ±  3%   32.34n ± 0%   -1.45% (p=0.000 n=10)
Match/"a["_"a"-8                             19.48n ±  2%   19.48n ± 2%        ~ (p=0.670 n=10)
Match/"a["_"ab"-8                            22.19n ±  3%   22.09n ± 1%        ~ (p=0.148 n=10)
Match/"a["_"x"-8                             20.32n ±  3%   19.66n ± 1%   -3.27% (p=0.001 n=10)
Match/"a/b["_"x"-8                           28.68n ±  1%   28.52n ± 1%        ~ (p=0.315 n=10)
Match/"*x"_"xxx"-8                           29.95n ±  3%   29.27n ± 3%   -2.27% (p=0.006 n=10)
geomean                                      36.76n         35.10n        -4.51%

Change-Id: I02d07b7a066e5789587035180fa15ae07a9579a6
GitHub-Last-Rev: 8b314b430920f9636088d0291adf8d518fc56b0a
GitHub-Pull-Request: golang/go#75211
Reviewed-on: https://go-review.googlesource.com/c/go/+/700315
Reviewed-by: Emmanuel Odeke <emmanuel@orijtech.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Kirill Kolyshkin <kolyshkin@gmail.com>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

2 files changed, 28 insertions, 25 deletions

diff --git a/src/path/filepath/match.go b/src/path/filepath/match.go
index b93e89adb0..7ccf71ee0c 100644
--- a/src/path/filepath/match.go
+++ b/src/path/filepath/match.go
@@ -94,16 +94,12 @@ func scanChunk(pattern string) (star bool, chunk, rest string) {
 		star = true
 	}
 	inrange := false
-	var i int
-Scan:
-	for i = 0; i < len(pattern); i++ {
+	for i := 0; i < len(pattern); i++ {
 		switch pattern[i] {
 		case '\\':
-			if runtime.GOOS != "windows" {
-				// error check handled in matchChunk: bad pattern.
-				if i+1 < len(pattern) {
-					i++
-				}
+			// error check handled in matchChunk: bad pattern.
+			if runtime.GOOS != "windows" && i+1 < len(pattern) {
+				i++
 			}
 		case '[':
 			inrange = true
@@ -111,11 +107,11 @@ Scan:
 			inrange = false
 		case '*':
 			if !inrange {
-				break Scan
+				return star, pattern[:i], pattern[i:]
 			}
 		}
 	}
-	return star, pattern[0:i], pattern[i:]
+	return star, pattern, ""
 }
 
 // matchChunk checks whether chunk matches the beginning of s.
@@ -127,9 +123,7 @@ func matchChunk(chunk, s string) (rest string, ok bool, err error) {
 	// checking that the pattern is well-formed but no longer reading s.
 	failed := false
 	for len(chunk) > 0 {
-		if !failed && len(s) == 0 {
-			failed = true
-		}
+		failed = failed || len(s) == 0
 		switch chunk[0] {
 		case '[':
 			// character class
@@ -164,20 +158,14 @@ func matchChunk(chunk, s string) (rest string, ok bool, err error) {
 						return "", false, err
 					}
 				}
-				if lo <= r && r <= hi {
-					match = true
-				}
+				match = match || lo <= r && r <= hi
 				nrange++
 			}
-			if match == negated {
-				failed = true
-			}
+			failed = failed || match == negated
 
 		case '?':
 			if !failed {
-				if s[0] == Separator {
-					failed = true
-				}
+				failed = s[0] == Separator
 				_, n := utf8.DecodeRuneInString(s)
 				s = s[n:]
 			}
@@ -194,9 +182,7 @@ func matchChunk(chunk, s string) (rest string, ok bool, err error) {
 
 		default:
 			if !failed {
-				if chunk[0] != s[0] {
-					failed = true
-				}
+				failed = chunk[0] != s[0]
 				s = s[1:]
 			}
 			chunk = chunk[1:]
diff --git a/src/path/filepath/match_test.go b/src/path/filepath/match_test.go
index 2ae79980c7..51ccaecaa9 100644
--- a/src/path/filepath/match_test.go
+++ b/src/path/filepath/match_test.go
@@ -106,6 +106,23 @@ func TestMatch(t *testing.T) {
 	}
 }
 
+func BenchmarkMatch(b *testing.B) {
+	for _, tt := range matchTests {
+		name := fmt.Sprintf("%q %q", tt.pattern, tt.s)
+		b.Run(name, func(b *testing.B) {
+			b.ReportAllocs()
+			for range b.N {
+				bSink, errSink = Match(tt.pattern, tt.s)
+			}
+		})
+	}
+}
+
+var (
+	bSink   bool
+	errSink error
+)
+
 var globTests = []struct {
 	pattern, result string
 }{