From 8f699a3fb9e5a947e66a5fc962ca5b70631e871c Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Wed, 28 Sep 2011 12:00:31 -0400 Subject: [PATCH] regexp: speedups MatchEasy0_1K 500000 4207 ns/op 243.35 MB/s MatchEasy0_1K_Old 500000 4625 ns/op 221.40 MB/s MatchEasy0_1M 500 3948932 ns/op 265.53 MB/s MatchEasy0_1M_Old 500 3943926 ns/op 265.87 MB/s MatchEasy0_32K 10000 122974 ns/op 266.46 MB/s MatchEasy0_32K_Old 10000 123270 ns/op 265.82 MB/s MatchEasy0_32M 10 127265400 ns/op 263.66 MB/s MatchEasy0_32M_Old 10 127123500 ns/op 263.95 MB/s MatchEasy1_1K 500000 5637 ns/op 181.63 MB/s MatchEasy1_1K_Old 10000 100690 ns/op 10.17 MB/s MatchEasy1_1M 200 7683150 ns/op 136.48 MB/s MatchEasy1_1M_Old 10 145774000 ns/op 7.19 MB/s MatchEasy1_32K 10000 239887 ns/op 136.60 MB/s MatchEasy1_32K_Old 500 4508182 ns/op 7.27 MB/s MatchEasy1_32M 10 247103500 ns/op 135.79 MB/s MatchEasy1_32M_Old 1 4660191000 ns/op 7.20 MB/s MatchMedium_1K 10000 160567 ns/op 6.38 MB/s MatchMedium_1K_Old 10000 158367 ns/op 6.47 MB/s MatchMedium_1M 10 162928000 ns/op 6.44 MB/s MatchMedium_1M_Old 10 159699200 ns/op 6.57 MB/s MatchMedium_32K 500 5090758 ns/op 6.44 MB/s MatchMedium_32K_Old 500 5005800 ns/op 6.55 MB/s MatchMedium_32M 1 5233973000 ns/op 6.41 MB/s MatchMedium_32M_Old 1 5109676000 ns/op 6.57 MB/s MatchHard_1K 10000 249087 ns/op 4.11 MB/s MatchHard_1K_Old 5000 364569 ns/op 2.81 MB/s MatchHard_1M 5 256050000 ns/op 4.10 MB/s MatchHard_1M_Old 5 372446400 ns/op 2.82 MB/s MatchHard_32K 200 7944525 ns/op 4.12 MB/s MatchHard_32K_Old 100 11609380 ns/op 2.82 MB/s MatchHard_32M 1 8144503000 ns/op 4.12 MB/s MatchHard_32M_Old 1 11885434000 ns/op 2.82 MB/s R=r, bradfitz CC=golang-dev https://golang.org/cl/5134049 --- src/pkg/regexp/exec.go | 72 +++++++++++++++++-------- src/pkg/regexp/exec_test.go | 85 ++++++++++++++++++++++++++++++ src/pkg/regexp/regexp.go | 12 ++++- src/pkg/regexp/syntax/compile.go | 11 ++++ src/pkg/regexp/syntax/prog.go | 23 +++++++- src/pkg/regexp/syntax/prog_test.go | 30 +++++------ 6 files changed, 191 insertions(+), 42 deletions(-) diff --git a/src/pkg/regexp/exec.go b/src/pkg/regexp/exec.go index 3395231c3a..3b0e388852 100644 --- a/src/pkg/regexp/exec.go +++ b/src/pkg/regexp/exec.go @@ -50,6 +50,13 @@ func progMachine(p *syntax.Prog) *machine { return m } +func (m *machine) init(ncap int) { + for _, t := range m.pool { + t.cap = t.cap[:ncap] + } + m.matchcap = m.matchcap[:ncap] +} + // alloc allocates a new thread with the given instruction. // It uses the free pool if possible. func (m *machine) alloc(i *syntax.Inst) *thread { @@ -59,9 +66,8 @@ func (m *machine) alloc(i *syntax.Inst) *thread { m.pool = m.pool[:n-1] } else { t = new(thread) - t.cap = make([]int, cap(m.matchcap)) + t.cap = make([]int, len(m.matchcap), cap(m.matchcap)) } - t.cap = t.cap[:len(m.matchcap)] t.inst = i return t } @@ -121,7 +127,7 @@ func (m *machine) match(i input, pos int) bool { if len(m.matchcap) > 0 { m.matchcap[0] = pos } - m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag) + m.add(runq, uint32(m.p.Start), pos, m.matchcap, flag, nil) } flag = syntax.EmptyOpContext(rune, rune1) m.step(runq, nextq, pos, pos+width, rune, flag) @@ -148,7 +154,8 @@ func (m *machine) match(i input, pos int) bool { func (m *machine) clear(q *queue) { for _, d := range q.dense { if d.t != nil { - m.free(d.t) + // m.free(d.t) + m.pool = append(m.pool, d.t) } } q.dense = q.dense[:0] @@ -168,10 +175,12 @@ func (m *machine) step(runq, nextq *queue, pos, nextPos, c int, nextCond syntax. continue } if longest && m.matched && len(t.cap) > 0 && m.matchcap[0] < t.cap[0] { - m.free(t) + // m.free(t) + m.pool = append(m.pool, t) continue } i := t.inst + add := false switch i.Op { default: panic("bad inst") @@ -185,7 +194,8 @@ func (m *machine) step(runq, nextq *queue, pos, nextPos, c int, nextCond syntax. // First-match mode: cut off all lower-priority threads. for _, d := range runq.dense[j+1:] { if d.t != nil { - m.free(d.t) + // m.free(d.t) + m.pool = append(m.pool, d.t) } } runq.dense = runq.dense[:0] @@ -193,11 +203,21 @@ func (m *machine) step(runq, nextq *queue, pos, nextPos, c int, nextCond syntax. m.matched = true case syntax.InstRune: - if i.MatchRune(c) { - m.add(nextq, i.Out, nextPos, t.cap, nextCond) - } + add = i.MatchRune(c) + case syntax.InstRune1: + add = c == i.Rune[0] + case syntax.InstRuneAny: + add = true + case syntax.InstRuneAnyNotNL: + add = c != '\n' + } + if add { + t = m.add(nextq, i.Out, nextPos, t.cap, nextCond, t) + } + if t != nil { + // m.free(t) + m.pool = append(m.pool, t) } - m.free(t) } runq.dense = runq.dense[:0] } @@ -206,12 +226,12 @@ func (m *machine) step(runq, nextq *queue, pos, nextPos, c int, nextCond syntax. // It also recursively adds an entry for all instructions reachable from pc by following // empty-width conditions satisfied by cond. pos gives the current position // in the input. -func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp) { +func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.EmptyOp, t *thread) *thread { if pc == 0 { - return + return t } if j := q.sparse[pc]; j < uint32(len(q.dense)) && q.dense[j].pc == pc { - return + return t } j := len(q.dense) @@ -228,30 +248,36 @@ func (m *machine) add(q *queue, pc uint32, pos int, cap []int, cond syntax.Empty case syntax.InstFail: // nothing case syntax.InstAlt, syntax.InstAltMatch: - m.add(q, i.Out, pos, cap, cond) - m.add(q, i.Arg, pos, cap, cond) + t = m.add(q, i.Out, pos, cap, cond, t) + t = m.add(q, i.Arg, pos, cap, cond, t) case syntax.InstEmptyWidth: if syntax.EmptyOp(i.Arg)&^cond == 0 { - m.add(q, i.Out, pos, cap, cond) + t = m.add(q, i.Out, pos, cap, cond, t) } case syntax.InstNop: - m.add(q, i.Out, pos, cap, cond) + t = m.add(q, i.Out, pos, cap, cond, t) case syntax.InstCapture: if int(i.Arg) < len(cap) { opos := cap[i.Arg] cap[i.Arg] = pos - m.add(q, i.Out, pos, cap, cond) + m.add(q, i.Out, pos, cap, cond, nil) cap[i.Arg] = opos } else { - m.add(q, i.Out, pos, cap, cond) + t = m.add(q, i.Out, pos, cap, cond, t) + } + case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL: + if t == nil { + t = m.alloc(i) + } else { + t.inst = i } - case syntax.InstMatch, syntax.InstRune: - t := m.alloc(i) - if len(t.cap) > 0 { + if len(cap) > 0 && &t.cap[0] != &cap[0] { copy(t.cap, cap) } d.t = t + t = nil } + return t } // empty is a non-nil 0-element slice, @@ -263,7 +289,7 @@ var empty = make([]int, 0) // the position of its subexpressions. func (re *Regexp) doExecute(i input, pos int, ncap int) []int { m := re.get() - m.matchcap = m.matchcap[:ncap] + m.init(ncap) if !m.match(i, pos) { re.put(m) return nil diff --git a/src/pkg/regexp/exec_test.go b/src/pkg/regexp/exec_test.go index d6af76645d..905fd4ef12 100644 --- a/src/pkg/regexp/exec_test.go +++ b/src/pkg/regexp/exec_test.go @@ -9,8 +9,10 @@ import ( "compress/bzip2" "fmt" "io" + old "old/regexp" "os" "path/filepath" + "rand" "regexp/syntax" "strconv" "strings" @@ -647,3 +649,86 @@ func parseFowlerResult(s string) (ok, compiled, matched bool, pos []int) { pos = x return } + +var text []byte + +func makeText(n int) []byte { + if len(text) >= n { + return text[:n] + } + text = make([]byte, n) + for i := range text { + if rand.Intn(30) == 0 { + text[i] = '\n' + } else { + text[i] = byte(rand.Intn(0x7E+1-0x20) + 0x20) + } + } + return text +} + +func benchmark(b *testing.B, re string, n int) { + r := MustCompile(re) + t := makeText(n) + b.ResetTimer() + b.SetBytes(int64(n)) + for i := 0; i < b.N; i++ { + if r.Match(t) { + panic("match!") + } + } +} + +func benchold(b *testing.B, re string, n int) { + r := old.MustCompile(re) + t := makeText(n) + b.ResetTimer() + b.SetBytes(int64(n)) + for i := 0; i < b.N; i++ { + if r.Match(t) { + panic("match!") + } + } +} + +const ( + easy0 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ$" + easy1 = "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$" + medium = "[XYZ]ABCDEFGHIJKLMNOPQRSTUVWXYZ$" + hard = "[ -~]*ABCDEFGHIJKLMNOPQRSTUVWXYZ$" + parens = "([ -~])*(A)(B)(C)(D)(E)(F)(G)(H)(I)(J)(K)(L)(M)" + + "(N)(O)(P)(Q)(R)(S)(T)(U)(V)(W)(X)(Y)(Z)$" +) + +func BenchmarkMatchEasy0_1K(b *testing.B) { benchmark(b, easy0, 1<<10) } +func BenchmarkMatchEasy0_1K_Old(b *testing.B) { benchold(b, easy0, 1<<10) } +func BenchmarkMatchEasy0_1M(b *testing.B) { benchmark(b, easy0, 1<<20) } +func BenchmarkMatchEasy0_1M_Old(b *testing.B) { benchold(b, easy0, 1<<20) } +func BenchmarkMatchEasy0_32K(b *testing.B) { benchmark(b, easy0, 32<<10) } +func BenchmarkMatchEasy0_32K_Old(b *testing.B) { benchold(b, easy0, 32<<10) } +func BenchmarkMatchEasy0_32M(b *testing.B) { benchmark(b, easy0, 32<<20) } +func BenchmarkMatchEasy0_32M_Old(b *testing.B) { benchold(b, easy0, 32<<20) } +func BenchmarkMatchEasy1_1K(b *testing.B) { benchmark(b, easy1, 1<<10) } +func BenchmarkMatchEasy1_1K_Old(b *testing.B) { benchold(b, easy1, 1<<10) } +func BenchmarkMatchEasy1_1M(b *testing.B) { benchmark(b, easy1, 1<<20) } +func BenchmarkMatchEasy1_1M_Old(b *testing.B) { benchold(b, easy1, 1<<20) } +func BenchmarkMatchEasy1_32K(b *testing.B) { benchmark(b, easy1, 32<<10) } +func BenchmarkMatchEasy1_32K_Old(b *testing.B) { benchold(b, easy1, 32<<10) } +func BenchmarkMatchEasy1_32M(b *testing.B) { benchmark(b, easy1, 32<<20) } +func BenchmarkMatchEasy1_32M_Old(b *testing.B) { benchold(b, easy1, 32<<20) } +func BenchmarkMatchMedium_1K(b *testing.B) { benchmark(b, medium, 1<<10) } +func BenchmarkMatchMedium_1K_Old(b *testing.B) { benchold(b, medium, 1<<10) } +func BenchmarkMatchMedium_1M(b *testing.B) { benchmark(b, medium, 1<<20) } +func BenchmarkMatchMedium_1M_Old(b *testing.B) { benchold(b, medium, 1<<20) } +func BenchmarkMatchMedium_32K(b *testing.B) { benchmark(b, medium, 32<<10) } +func BenchmarkMatchMedium_32K_Old(b *testing.B) { benchold(b, medium, 32<<10) } +func BenchmarkMatchMedium_32M(b *testing.B) { benchmark(b, medium, 32<<20) } +func BenchmarkMatchMedium_32M_Old(b *testing.B) { benchold(b, medium, 32<<20) } +func BenchmarkMatchHard_1K(b *testing.B) { benchmark(b, hard, 1<<10) } +func BenchmarkMatchHard_1K_Old(b *testing.B) { benchold(b, hard, 1<<10) } +func BenchmarkMatchHard_1M(b *testing.B) { benchmark(b, hard, 1<<20) } +func BenchmarkMatchHard_1M_Old(b *testing.B) { benchold(b, hard, 1<<20) } +func BenchmarkMatchHard_32K(b *testing.B) { benchmark(b, hard, 32<<10) } +func BenchmarkMatchHard_32K_Old(b *testing.B) { benchold(b, hard, 32<<10) } +func BenchmarkMatchHard_32M(b *testing.B) { benchmark(b, hard, 32<<20) } +func BenchmarkMatchHard_32M_Old(b *testing.B) { benchold(b, hard, 32<<20) } diff --git a/src/pkg/regexp/regexp.go b/src/pkg/regexp/regexp.go index 8632c10688..2325f6204b 100644 --- a/src/pkg/regexp/regexp.go +++ b/src/pkg/regexp/regexp.go @@ -247,7 +247,11 @@ func newInputString(str string) *inputString { func (i *inputString) step(pos int) (int, int) { if pos < len(i.str) { - return utf8.DecodeRuneInString(i.str[pos:len(i.str)]) + c := i.str[pos] + if c < utf8.RuneSelf { + return int(c), 1 + } + return utf8.DecodeRuneInString(i.str[pos:]) } return endOfText, 0 } @@ -286,7 +290,11 @@ func newInputBytes(str []byte) *inputBytes { func (i *inputBytes) step(pos int) (int, int) { if pos < len(i.str) { - return utf8.DecodeRune(i.str[pos:len(i.str)]) + c := i.str[pos] + if c < utf8.RuneSelf { + return int(c), 1 + } + return utf8.DecodeRune(i.str[pos:]) } return endOfText, 0 } diff --git a/src/pkg/regexp/syntax/compile.go b/src/pkg/regexp/syntax/compile.go index 6b6d062374..c415d39a57 100644 --- a/src/pkg/regexp/syntax/compile.go +++ b/src/pkg/regexp/syntax/compile.go @@ -273,5 +273,16 @@ func (c *compiler) rune(rune []int, flags Flags) frag { } i.Arg = uint32(flags) f.out = patchList(f.i << 1) + + // Special cases for exec machine. + switch { + case flags&FoldCase == 0 && (len(rune) == 1 || len(rune) == 2 && rune[0] == rune[1]): + i.Op = InstRune1 + case len(rune) == 2 && rune[0] == 0 && rune[1] == unicode.MaxRune: + i.Op = InstRuneAny + case len(rune) == 4 && rune[0] == 0 && rune[1] == '\n'-1 && rune[2] == '\n'+1 && rune[3] == unicode.MaxRune: + i.Op = InstRuneAnyNotNL + } + return f } diff --git a/src/pkg/regexp/syntax/prog.go b/src/pkg/regexp/syntax/prog.go index e92baaca0d..ced45da077 100644 --- a/src/pkg/regexp/syntax/prog.go +++ b/src/pkg/regexp/syntax/prog.go @@ -28,6 +28,9 @@ const ( InstFail InstNop InstRune + InstRune1 + InstRuneAny + InstRuneAnyNotNL ) // An EmptyOp specifies a kind or mixture of zero-width assertions. @@ -102,6 +105,16 @@ func (p *Prog) skipNop(pc uint32) *Inst { return i } +// op returns i.Op but merges all the Rune special cases into InstRune +func (i *Inst) op() InstOp { + op := i.Op + switch op { + case InstRune1, InstRuneAny, InstRuneAnyNotNL: + op = InstRune + } + return op +} + // Prefix returns a literal string that all matches for the // regexp must start with. Complete is true if the prefix // is the entire match. @@ -109,13 +122,13 @@ func (p *Prog) Prefix() (prefix string, complete bool) { i := p.skipNop(uint32(p.Start)) // Avoid allocation of buffer if prefix is empty. - if i.Op != InstRune || len(i.Rune) != 1 { + if i.op() != InstRune || len(i.Rune) != 1 { return "", i.Op == InstMatch } // Have prefix; gather characters. var buf bytes.Buffer - for i.Op == InstRune && len(i.Rune) == 1 && Flags(i.Arg)&FoldCase == 0 { + for i.op() == InstRune && len(i.Rune) == 1 && Flags(i.Arg)&FoldCase == 0 { buf.WriteRune(i.Rune[0]) i = p.skipNop(i.Out) } @@ -283,5 +296,11 @@ func dumpInst(b *bytes.Buffer, i *Inst) { bw(b, "/i") } bw(b, " -> ", u32(i.Out)) + case InstRune1: + bw(b, "rune1 ", strconv.QuoteToASCII(string(i.Rune)), " -> ", u32(i.Out)) + case InstRuneAny: + bw(b, "any -> ", u32(i.Out)) + case InstRuneAnyNotNL: + bw(b, "anynotnl -> ", u32(i.Out)) } } diff --git a/src/pkg/regexp/syntax/prog_test.go b/src/pkg/regexp/syntax/prog_test.go index 3fe0c5870a..e3e3f4d142 100644 --- a/src/pkg/regexp/syntax/prog_test.go +++ b/src/pkg/regexp/syntax/prog_test.go @@ -9,7 +9,7 @@ var compileTests = []struct { Prog string }{ {"a", ` 0 fail - 1* rune "a" -> 2 + 1* rune1 "a" -> 2 2 match `}, {"[A-M][n-z]", ` 0 fail @@ -22,69 +22,69 @@ var compileTests = []struct { 2 match `}, {"a?", ` 0 fail - 1 rune "a" -> 3 + 1 rune1 "a" -> 3 2* alt -> 1, 3 3 match `}, {"a??", ` 0 fail - 1 rune "a" -> 3 + 1 rune1 "a" -> 3 2* alt -> 3, 1 3 match `}, {"a+", ` 0 fail - 1* rune "a" -> 2 + 1* rune1 "a" -> 2 2 alt -> 1, 3 3 match `}, {"a+?", ` 0 fail - 1* rune "a" -> 2 + 1* rune1 "a" -> 2 2 alt -> 3, 1 3 match `}, {"a*", ` 0 fail - 1 rune "a" -> 2 + 1 rune1 "a" -> 2 2* alt -> 1, 3 3 match `}, {"a*?", ` 0 fail - 1 rune "a" -> 2 + 1 rune1 "a" -> 2 2* alt -> 3, 1 3 match `}, {"a+b+", ` 0 fail - 1* rune "a" -> 2 + 1* rune1 "a" -> 2 2 alt -> 1, 3 - 3 rune "b" -> 4 + 3 rune1 "b" -> 4 4 alt -> 3, 5 5 match `}, {"(a+)(b+)", ` 0 fail 1* cap 2 -> 2 - 2 rune "a" -> 3 + 2 rune1 "a" -> 3 3 alt -> 2, 4 4 cap 3 -> 5 5 cap 4 -> 6 - 6 rune "b" -> 7 + 6 rune1 "b" -> 7 7 alt -> 6, 8 8 cap 5 -> 9 9 match `}, {"a+|b+", ` 0 fail - 1 rune "a" -> 2 + 1 rune1 "a" -> 2 2 alt -> 1, 6 - 3 rune "b" -> 4 + 3 rune1 "b" -> 4 4 alt -> 3, 6 5* alt -> 1, 3 6 match `}, {"A[Aa]", ` 0 fail - 1* rune "A" -> 2 + 1* rune1 "A" -> 2 2 rune "A"/i -> 3 3 match `}, {"(?:(?:^).)", ` 0 fail 1* empty 4 -> 2 - 2 rune "\x00\t\v\U0010ffff" -> 3 + 2 anynotnl -> 3 3 match `}, } -- 2.50.0