diff options
author | Sylvain Zimmer <sylvain@sylvainzimmer.com> | 2019-04-07 23:23:28 +0200 |
---|---|---|
committer | Russ Cox <rsc@golang.org> | 2019-05-15 15:28:22 +0000 |
commit | 8116599f01c38c491182d95a00f74706ed5f75c4 (patch) | |
tree | a90e4a27890f396c2dd14e0009356b4cd9d10e30 /src/regexp | |
parent | cefc0bbc9011baa62a8284d61452ba33245e8455 (diff) | |
download | go-8116599f01c38c491182d95a00f74706ed5f75c4.tar.gz go-8116599f01c38c491182d95a00f74706ed5f75c4.zip |
regexp: optimize for provably too short inputs
For many patterns we can compute the minimum input length at compile time.
If the input is shorter, we can return early and get a huge speedup.
As pointed out by Damian Gryski, Perl's regex engine contains a number of
these kinds of fail-fast optimizations:
https://perldoc.perl.org/perlreguts.html#Peep-hole-Optimisation-and-Analysis
Benchmarks: (including new ones for compile time)
name old time/op new time/op delta
Compile/Onepass-8 4.39µs ± 1% 4.40µs ± 0% +0.34% (p=0.029 n=9+8)
Compile/Medium-8 9.80µs ± 0% 9.91µs ± 0% +1.17% (p=0.000 n=10+10)
Compile/Hard-8 72.7µs ± 0% 73.5µs ± 0% +1.10% (p=0.000 n=9+10)
name old time/op new time/op delta
Match/Easy0/16-8 52.6ns ± 5% 4.9ns ± 0% -90.68% (p=0.000 n=10+9)
Match/Easy0/32-8 64.1ns ±10% 61.4ns ± 1% ~ (p=0.188 n=10+9)
Match/Easy0/1K-8 280ns ± 1% 277ns ± 2% -0.97% (p=0.004 n=10+10)
Match/Easy0/32K-8 4.61µs ± 1% 4.55µs ± 1% -1.49% (p=0.000 n=9+10)
Match/Easy0/1M-8 229µs ± 0% 226µs ± 1% -1.29% (p=0.000 n=8+10)
Match/Easy0/32M-8 7.50ms ± 1% 7.47ms ± 1% ~ (p=0.165 n=10+10)
Match/Easy0i/16-8 533ns ± 1% 5ns ± 2% -99.07% (p=0.000 n=10+10)
Match/Easy0i/32-8 950ns ± 0% 950ns ± 1% ~ (p=0.920 n=10+9)
Match/Easy0i/1K-8 27.5µs ± 1% 27.5µs ± 0% ~ (p=0.739 n=10+10)
Match/Easy0i/32K-8 1.13ms ± 0% 1.13ms ± 1% ~ (p=0.079 n=9+10)
Match/Easy0i/1M-8 36.7ms ± 2% 36.1ms ± 0% -1.64% (p=0.000 n=10+9)
Match/Easy0i/32M-8 1.17s ± 0% 1.16s ± 1% -0.80% (p=0.004 n=8+9)
Match/Easy1/16-8 55.5ns ± 6% 4.9ns ± 1% -91.19% (p=0.000 n=10+9)
Match/Easy1/32-8 58.3ns ± 8% 56.6ns ± 1% ~ (p=0.449 n=10+8)
Match/Easy1/1K-8 750ns ± 0% 748ns ± 1% ~ (p=0.072 n=8+10)
Match/Easy1/32K-8 31.8µs ± 0% 31.6µs ± 1% -0.50% (p=0.035 n=10+9)
Match/Easy1/1M-8 1.10ms ± 1% 1.09ms ± 0% -0.95% (p=0.000 n=10+9)
Match/Easy1/32M-8 35.5ms ± 0% 35.2ms ± 1% -1.05% (p=0.000 n=9+10)
Match/Medium/16-8 442ns ± 2% 5ns ± 1% -98.89% (p=0.000 n=10+10)
Match/Medium/32-8 875ns ± 0% 878ns ± 1% ~ (p=0.071 n=9+10)
Match/Medium/1K-8 26.1µs ± 0% 25.9µs ± 0% -0.64% (p=0.000 n=10+10)
Match/Medium/32K-8 1.09ms ± 1% 1.08ms ± 0% -0.84% (p=0.000 n=10+9)
Match/Medium/1M-8 34.9ms ± 0% 34.6ms ± 1% -0.98% (p=0.000 n=9+10)
Match/Medium/32M-8 1.12s ± 1% 1.11s ± 1% -0.98% (p=0.000 n=10+9)
Match/Hard/16-8 721ns ± 1% 5ns ± 0% -99.32% (p=0.000 n=10+9)
Match/Hard/32-8 1.32µs ± 1% 1.31µs ± 0% -0.71% (p=0.000 n=9+9)
Match/Hard/1K-8 39.8µs ± 1% 39.7µs ± 1% ~ (p=0.165 n=10+10)
Match/Hard/32K-8 1.57ms ± 0% 1.56ms ± 0% -0.70% (p=0.000 n=10+9)
Match/Hard/1M-8 50.4ms ± 1% 50.1ms ± 1% -0.57% (p=0.007 n=10+10)
Match/Hard/32M-8 1.62s ± 1% 1.60s ± 0% -0.98% (p=0.000 n=10+10)
Match/Hard1/16-8 3.88µs ± 1% 3.86µs ± 0% ~ (p=0.118 n=10+10)
Match/Hard1/32-8 7.44µs ± 1% 7.46µs ± 1% ~ (p=0.109 n=10+10)
Match/Hard1/1K-8 232µs ± 1% 229µs ± 1% -1.31% (p=0.000 n=10+9)
Match/Hard1/32K-8 7.41ms ± 2% 7.41ms ± 0% ~ (p=0.237 n=10+8)
Match/Hard1/1M-8 238ms ± 1% 238ms ± 0% ~ (p=0.481 n=10+10)
Match/Hard1/32M-8 7.69s ± 1% 7.61s ± 0% -1.00% (p=0.000 n=10+10)
Fixes #31329
Change-Id: I04640e8c59178ec8b3106e13ace9b109b6bdbc25
Reviewed-on: https://go-review.googlesource.com/c/go/+/171023
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
Run-TryBot: Rob Pike <r@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Diffstat (limited to 'src/regexp')
-rw-r--r-- | src/regexp/all_test.go | 47 | ||||
-rw-r--r-- | src/regexp/exec.go | 4 | ||||
-rw-r--r-- | src/regexp/exec_test.go | 1 | ||||
-rw-r--r-- | src/regexp/onepass_test.go | 10 | ||||
-rw-r--r-- | src/regexp/regexp.go | 38 |
5 files changed, 90 insertions, 10 deletions
diff --git a/src/regexp/all_test.go b/src/regexp/all_test.go index 623f82df72..626a69142f 100644 --- a/src/regexp/all_test.go +++ b/src/regexp/all_test.go @@ -860,6 +860,25 @@ func BenchmarkQuoteMetaNone(b *testing.B) { } } +var compileBenchData = []struct{ name, re string }{ + {"Onepass", `^a.[l-nA-Cg-j]?e$`}, + {"Medium", `^((a|b|[d-z0-9])*(日){4,5}.)+$`}, + {"Hard", strings.Repeat(`((abc)*|`, 50) + strings.Repeat(`)`, 50)}, +} + +func BenchmarkCompile(b *testing.B) { + for _, data := range compileBenchData { + b.Run(data.name, func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + if _, err := Compile(data.re); err != nil { + b.Fatal(err) + } + } + }) + } +} + func TestDeepEqual(t *testing.T) { re1 := MustCompile("a.*b.*c.*d") re2 := MustCompile("a.*b.*c.*d") @@ -882,3 +901,31 @@ func TestDeepEqual(t *testing.T) { t.Errorf("DeepEqual(re1, re2) = false, want true") } } + +var minInputLenTests = []struct { + Regexp string + min int +}{ + {``, 0}, + {`a`, 1}, + {`aa`, 2}, + {`(aa)a`, 3}, + {`(?:aa)a`, 3}, + {`a?a`, 1}, + {`(aaa)|(aa)`, 2}, + {`(aa)+a`, 3}, + {`(aa)*a`, 1}, + {`(aa){3,5}`, 6}, + {`[a-z]`, 1}, + {`日`, 3}, +} + +func TestMinInputLen(t *testing.T) { + for _, tt := range minInputLenTests { + re, _ := syntax.Parse(tt.Regexp, syntax.Perl) + m := minInputLen(re) + if m != tt.min { + t.Errorf("regexp %#q has minInputLen %d, should be %d", tt.Regexp, m, tt.min) + } + } +} diff --git a/src/regexp/exec.go b/src/regexp/exec.go index efe764e2dc..4411e4c3e6 100644 --- a/src/regexp/exec.go +++ b/src/regexp/exec.go @@ -524,6 +524,10 @@ func (re *Regexp) doExecute(r io.RuneReader, b []byte, s string, pos int, ncap i dstCap = arrayNoInts[:0:0] } + if r == nil && len(b)+len(s) < re.minInputLen { + return nil + } + if re.onepass != nil { return re.doOnePass(r, b, s, pos, ncap, dstCap) } diff --git a/src/regexp/exec_test.go b/src/regexp/exec_test.go index 1489219328..1e8795525d 100644 --- a/src/regexp/exec_test.go +++ b/src/regexp/exec_test.go @@ -717,6 +717,7 @@ var benchSizes = []struct { name string n int }{ + {"16", 16}, {"32", 32}, {"1K", 1 << 10}, {"32K", 32 << 10}, diff --git a/src/regexp/onepass_test.go b/src/regexp/onepass_test.go index a0f2e39048..32264d5f1e 100644 --- a/src/regexp/onepass_test.go +++ b/src/regexp/onepass_test.go @@ -223,13 +223,3 @@ func TestRunOnePass(t *testing.T) { } } } - -func BenchmarkCompileOnepass(b *testing.B) { - b.ReportAllocs() - const re = `^a.[l-nA-Cg-j]?e$` - for i := 0; i < b.N; i++ { - if _, err := Compile(re); err != nil { - b.Fatal(err) - } - } -} diff --git a/src/regexp/regexp.go b/src/regexp/regexp.go index 54cbd3777b..19ca6f2223 100644 --- a/src/regexp/regexp.go +++ b/src/regexp/regexp.go @@ -94,6 +94,7 @@ type Regexp struct { matchcap int // size of recorded match lengths prefixComplete bool // prefix is the entire regexp cond syntax.EmptyOp // empty-width conditions required at start of match + minInputLen int // minimum length of the input in bytes // This field can be modified by the Longest method, // but it is otherwise read-only. @@ -191,6 +192,7 @@ func compile(expr string, mode syntax.Flags, longest bool) (*Regexp, error) { cond: prog.StartCond(), longest: longest, matchcap: matchcap, + minInputLen: minInputLen(re), } if regexp.onepass == nil { regexp.prefix, regexp.prefixComplete = prog.Prefix() @@ -264,6 +266,42 @@ func (re *Regexp) put(m *machine) { matchPool[re.mpool].Put(m) } +// minInputLen walks the regexp to find the minimum length of any matchable input +func minInputLen(re *syntax.Regexp) int { + switch re.Op { + default: + return 0 + case syntax.OpAnyChar, syntax.OpAnyCharNotNL, syntax.OpCharClass: + return 1 + case syntax.OpLiteral: + l := 0 + for _, r := range re.Rune { + l += utf8.RuneLen(r) + } + return l + case syntax.OpCapture, syntax.OpPlus: + return minInputLen(re.Sub[0]) + case syntax.OpRepeat: + return re.Min * minInputLen(re.Sub[0]) + case syntax.OpConcat: + l := 0 + for _, sub := range re.Sub { + l += minInputLen(sub) + } + return l + case syntax.OpAlternate: + l := minInputLen(re.Sub[0]) + var lnext int + for _, sub := range re.Sub[1:] { + lnext = minInputLen(sub) + if lnext < l { + l = lnext + } + } + return l + } +} + // MustCompile is like Compile but panics if the expression cannot be parsed. // It simplifies safe initialization of global variables holding compiled regular // expressions. |