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>