From 8c27a808905b0611b0a7b7bbff08819206be3b86 Mon Sep 17 00:00:00 2001 From: Julien Cretel Date: Sun, 31 Aug 2025 19:34:07 +0000 Subject: [PATCH] path{,/filepath}: speed up Match MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 Reviewed-by: Keith Randall Reviewed-by: Kirill Kolyshkin Reviewed-by: Keith Randall Auto-Submit: Keith Randall Reviewed-by: Michael Pratt LUCI-TryBot-Result: Go LUCI --- src/cmd/compile/internal/test/inl_test.go | 6 ++++ src/path/filepath/match.go | 36 +++++++---------------- src/path/filepath/match_test.go | 17 +++++++++++ src/path/match.go | 28 +++++------------- src/path/match_test.go | 18 ++++++++++++ 5 files changed, 60 insertions(+), 45 deletions(-) diff --git a/src/cmd/compile/internal/test/inl_test.go b/src/cmd/compile/internal/test/inl_test.go index a49cd767db..4e51d7d9d1 100644 --- a/src/cmd/compile/internal/test/inl_test.go +++ b/src/cmd/compile/internal/test/inl_test.go @@ -233,6 +233,12 @@ func TestIntendedInlining(t *testing.T) { "testing": { "(*B).Loop", }, + "path": { + "scanChunk", + }, + "path/filepath": { + "scanChunk", + }, } if runtime.GOARCH != "386" && runtime.GOARCH != "loong64" && runtime.GOARCH != "mips64" && runtime.GOARCH != "mips64le" && runtime.GOARCH != "riscv64" { 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 }{ diff --git a/src/path/match.go b/src/path/match.go index d8b6809568..0678effd6e 100644 --- a/src/path/match.go +++ b/src/path/match.go @@ -95,9 +95,7 @@ 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 '\\': // error check handled in matchChunk: bad pattern. @@ -110,11 +108,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. @@ -126,9 +124,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 @@ -163,20 +159,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] == '/' { - failed = true - } + failed = s[0] == '/' _, n := utf8.DecodeRuneInString(s) s = s[n:] } @@ -191,9 +181,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/match_test.go b/src/path/match_test.go index 996bd691eb..90ca19a6f4 100644 --- a/src/path/match_test.go +++ b/src/path/match_test.go @@ -5,6 +5,7 @@ package path_test import ( + "fmt" . "path" "testing" ) @@ -82,3 +83,20 @@ 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 +) -- 2.52.0