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
diff --git a/src/pkg/regexp/exec.go b/src/pkg/regexp/exec.go
index 3395231..3b0e388 100644
--- a/src/pkg/regexp/exec.go
+++ b/src/pkg/regexp/exec.go
@@ -50,6 +50,13 @@
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 @@
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 @@
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) 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 @@
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 @@
// 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 @@
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'
}
- m.free(t)
+ 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)
+ }
}
runq.dense = runq.dense[:0]
}
@@ -206,12 +226,12 @@
// 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 @@
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:
- t := m.alloc(i)
- if len(t.cap) > 0 {
+ case syntax.InstMatch, syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
+ if t == nil {
+ t = m.alloc(i)
+ } else {
+ t.inst = i
+ }
+ 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 @@
// 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 d6af766..905fd4e 100644
--- a/src/pkg/regexp/exec_test.go
+++ b/src/pkg/regexp/exec_test.go
@@ -9,8 +9,10 @@
"compress/bzip2"
"fmt"
"io"
+ old "old/regexp"
"os"
"path/filepath"
+ "rand"
"regexp/syntax"
"strconv"
"strings"
@@ -647,3 +649,86 @@
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 8632c10..2325f62 100644
--- a/src/pkg/regexp/regexp.go
+++ b/src/pkg/regexp/regexp.go
@@ -247,7 +247,11 @@
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 (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 6b6d062..c415d39 100644
--- a/src/pkg/regexp/syntax/compile.go
+++ b/src/pkg/regexp/syntax/compile.go
@@ -273,5 +273,16 @@
}
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 e92baac..ced45da 100644
--- a/src/pkg/regexp/syntax/prog.go
+++ b/src/pkg/regexp/syntax/prog.go
@@ -28,6 +28,9 @@
InstFail
InstNop
InstRune
+ InstRune1
+ InstRuneAny
+ InstRuneAnyNotNL
)
// An EmptyOp specifies a kind or mixture of zero-width assertions.
@@ -102,6 +105,16 @@
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 @@
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 @@
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 3fe0c58..e3e3f4d 100644
--- a/src/pkg/regexp/syntax/prog_test.go
+++ b/src/pkg/regexp/syntax/prog_test.go
@@ -9,7 +9,7 @@
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 @@
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
`},
}
