| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
In Perl mode, (|a)* should match an empty string at the start of the
input. Instead it matches as many a's as possible.
Because (|a)+ is handled correctly, matching only an empty string,
this leads to the paradox that e* can match more text than e+
(for e = (|a)) and that e+ is sometimes different from ee*.
This is a very old bug that ultimately derives from the picture I drew
for e* in https://swtch.com/~rsc/regexp/regexp1.html. The picture is
correct for longest-match (POSIX) regexps but subtly wrong for
preferred-match (Perl) regexps in the case where e has a preferred
empty match. Pointed out by Andrew Gallant in private mail.
The current code treats e* and e+ as the same structure, with
different entry points. In the case of e* the preference list ends up
not quite in the right order, in part because the “before e” and
“after e” states are the same state. Splitting them apart fixes the
preference list, and that can be done by compiling e* as if it were
(e+)?.
Like with any bug fix, there is a very low chance of breaking a
program that accidentally depends on the buggy behavior.
RE2, Go, and Rust all have this bug, and we've all agreed to fix it,
to keep the implementations in sync.
Fixes #46123.
Change-Id: I70e742e71e0a23b626593b16ddef3c1e73b413b0
Reviewed-on: https://go-review.googlesource.com/c/go/+/318750
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This allows the one-pass executions to have their
own pool of (much smaller) allocated structures.
A step toward eliminating the per-Regexp machine cache.
Not much effect on benchmarks, since there are no
optimizations here, and pools are a tiny bit slower than a
locked data structure for single-threaded code.
name old time/op new time/op delta
Find-12 254ns ± 0% 252ns ± 0% -0.94% (p=0.000 n=9+10)
FindAllNoMatches-12 135ns ± 0% 134ns ± 1% -0.49% (p=0.002 n=9+9)
FindString-12 247ns ± 0% 246ns ± 0% -0.24% (p=0.003 n=8+10)
FindSubmatch-12 334ns ± 0% 333ns ± 2% ~ (p=0.283 n=10+10)
FindStringSubmatch-12 321ns ± 0% 320ns ± 0% -0.51% (p=0.000 n=9+10)
Literal-12 92.2ns ± 0% 91.1ns ± 0% -1.25% (p=0.000 n=9+10)
NotLiteral-12 1.47µs ± 0% 1.45µs ± 0% -0.99% (p=0.000 n=9+10)
MatchClass-12 2.17µs ± 0% 2.19µs ± 0% +0.84% (p=0.000 n=7+9)
MatchClass_InRange-12 2.13µs ± 0% 2.09µs ± 0% -1.70% (p=0.000 n=10+10)
ReplaceAll-12 1.39µs ± 0% 1.39µs ± 0% +0.51% (p=0.000 n=10+10)
AnchoredLiteralShortNonMatch-12 83.2ns ± 0% 82.4ns ± 0% -0.96% (p=0.000 n=8+8)
AnchoredLiteralLongNonMatch-12 105ns ± 0% 106ns ± 1% ~ (p=0.087 n=10+10)
AnchoredShortMatch-12 131ns ± 0% 130ns ± 0% -0.76% (p=0.000 n=10+9)
AnchoredLongMatch-12 267ns ± 0% 272ns ± 0% +2.01% (p=0.000 n=10+8)
OnePassShortA-12 611ns ± 0% 615ns ± 0% +0.61% (p=0.000 n=9+10)
NotOnePassShortA-12 552ns ± 0% 549ns ± 0% -0.46% (p=0.000 n=8+9)
OnePassShortB-12 491ns ± 0% 494ns ± 0% +0.61% (p=0.000 n=8+8)
NotOnePassShortB-12 412ns ± 0% 412ns ± 1% ~ (p=0.151 n=9+10)
OnePassLongPrefix-12 112ns ± 0% 108ns ± 0% -3.57% (p=0.000 n=10+10)
OnePassLongNotPrefix-12 410ns ± 0% 402ns ± 0% -1.95% (p=0.000 n=9+8)
MatchParallelShared-12 38.8ns ± 1% 38.6ns ± 2% ~ (p=0.536 n=10+9)
MatchParallelCopied-12 39.2ns ± 3% 39.4ns ± 7% ~ (p=0.986 n=10+10)
QuoteMetaAll-12 94.6ns ± 0% 94.9ns ± 0% +0.29% (p=0.001 n=8+9)
QuoteMetaNone-12 52.7ns ± 0% 52.7ns ± 0% ~ (all equal)
Match/Easy0/32-12 72.9ns ± 0% 72.1ns ± 0% -1.07% (p=0.000 n=9+9)
Match/Easy0/1K-12 298ns ± 0% 298ns ± 0% ~ (p=0.140 n=6+8)
Match/Easy0/32K-12 4.60µs ± 2% 4.64µs ± 1% ~ (p=0.171 n=10+10)
Match/Easy0/1M-12 235µs ± 0% 234µs ± 0% -0.14% (p=0.004 n=10+10)
Match/Easy0/32M-12 7.96ms ± 0% 7.95ms ± 0% -0.12% (p=0.043 n=10+9)
Match/Easy0i/32-12 1.09µs ± 0% 1.10µs ± 0% +0.15% (p=0.000 n=8+9)
Match/Easy0i/1K-12 31.7µs ± 0% 31.8µs ± 1% ~ (p=0.905 n=9+10)
Match/Easy0i/32K-12 1.61ms ± 0% 1.62ms ± 1% +1.12% (p=0.000 n=9+10)
Match/Easy0i/1M-12 51.4ms ± 0% 51.8ms ± 0% +0.85% (p=0.000 n=8+8)
Match/Easy0i/32M-12 1.65s ± 1% 1.65s ± 0% ~ (p=0.113 n=9+9)
Match/Easy1/32-12 67.9ns ± 0% 67.7ns ± 1% ~ (p=0.232 n=8+10)
Match/Easy1/1K-12 884ns ± 0% 873ns ± 0% -1.29% (p=0.000 n=9+10)
Match/Easy1/32K-12 39.2µs ± 0% 39.4µs ± 0% +0.50% (p=0.000 n=9+10)
Match/Easy1/1M-12 1.39ms ± 0% 1.39ms ± 0% +0.29% (p=0.000 n=9+10)
Match/Easy1/32M-12 44.2ms ± 1% 44.3ms ± 0% +0.21% (p=0.029 n=10+10)
Match/Medium/32-12 1.05µs ± 0% 1.04µs ± 0% -0.27% (p=0.001 n=8+9)
Match/Medium/1K-12 31.3µs ± 0% 31.4µs ± 0% +0.39% (p=0.000 n=9+8)
Match/Medium/32K-12 1.45ms ± 0% 1.45ms ± 0% +0.33% (p=0.000 n=8+9)
Match/Medium/1M-12 46.2ms ± 0% 46.4ms ± 0% +0.35% (p=0.000 n=9+8)
Match/Medium/32M-12 1.48s ± 0% 1.49s ± 1% +0.70% (p=0.000 n=8+10)
Match/Hard/32-12 1.49µs ± 0% 1.48µs ± 0% -0.43% (p=0.000 n=10+9)
Match/Hard/1K-12 45.1µs ± 1% 45.0µs ± 1% ~ (p=0.393 n=10+10)
Match/Hard/32K-12 2.18ms ± 1% 2.24ms ± 0% +2.71% (p=0.000 n=9+8)
Match/Hard/1M-12 69.7ms ± 1% 71.6ms ± 0% +2.76% (p=0.000 n=9+7)
Match/Hard/32M-12 2.23s ± 1% 2.29s ± 0% +2.65% (p=0.000 n=9+9)
Match/Hard1/32-12 7.89µs ± 0% 7.89µs ± 0% ~ (p=0.286 n=9+9)
Match/Hard1/1K-12 244µs ± 0% 244µs ± 0% ~ (p=0.905 n=9+10)
Match/Hard1/32K-12 10.3ms ± 0% 10.3ms ± 0% ~ (p=0.796 n=10+10)
Match/Hard1/1M-12 331ms ± 0% 331ms ± 0% ~ (p=0.167 n=8+9)
Match/Hard1/32M-12 10.6s ± 0% 10.6s ± 0% ~ (p=0.315 n=8+10)
Match_onepass_regex/32-12 812ns ± 0% 830ns ± 0% +2.19% (p=0.000 n=10+9)
Match_onepass_regex/1K-12 28.5µs ± 0% 28.7µs ± 1% +0.97% (p=0.000 n=10+9)
Match_onepass_regex/32K-12 936µs ± 0% 949µs ± 0% +1.43% (p=0.000 n=10+8)
Match_onepass_regex/1M-12 30.2ms ± 0% 30.4ms ± 0% +0.62% (p=0.000 n=10+8)
Match_onepass_regex/32M-12 970ms ± 0% 973ms ± 0% +0.35% (p=0.000 n=10+9)
CompileOnepass-12 4.63µs ± 1% 4.64µs ± 0% ~ (p=0.060 n=10+10)
[Geo mean] 23.3µs 23.3µs +0.12%
https://perf.golang.org/search?q=upload:20181004.2
Change-Id: Iff9e9f9d4a4698162126a2f300e8ed1b1a39361e
Reviewed-on: https://go-review.googlesource.com/c/139780
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
| |
|
|
|
|
|
|
|
|
|
| |
One benchmark is fine.
Having one per test case is overkill.
Change-Id: Id4ce789484dab1e79026bdd23cbcd63b2eaceb3f
Reviewed-on: https://go-review.googlesource.com/c/139777
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
It reduces needless allocations on compiling onepass regex.
name old time/op new time/op delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4 6.31µs ± 3% 6.11µs ± 3% ~ (p=0.056 n=5+5)
CompileOnepass/^abcd$-4 5.69µs ±12% 4.93µs ± 4% -13.42% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4 7.10µs ±12% 5.82µs ± 5% -17.95% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4 5.99µs ±10% 6.07µs ±11% ~ (p=1.000 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4 7.36µs ± 4% 7.81µs ±19% ~ (p=0.310 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4 4.71µs ± 3% 4.71µs ± 5% ~ (p=1.000 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4 6.06µs ± 2% 6.23µs ± 9% ~ (p=0.310 n=5+5)
CompileOnepass/^[a-c]+$-4 4.74µs ± 4% 4.64µs ± 6% ~ (p=0.421 n=5+5)
CompileOnepass/^[a-c]*$-4 5.17µs ± 2% 4.68µs ± 0% -9.57% (p=0.016 n=5+4)
CompileOnepass/^(?:a*)$-4 5.34µs ± 3% 5.08µs ±12% ~ (p=0.151 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4 7.24µs ± 5% 7.33µs ±12% ~ (p=0.841 n=5+5)
CompileOnepass/^...$-4 5.28µs ± 3% 4.99µs ± 9% ~ (p=0.095 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4 7.20µs ± 4% 7.24µs ±10% ~ (p=0.841 n=5+5)
CompileOnepass/^a((b))c$-4 7.99µs ± 3% 7.76µs ± 8% ~ (p=0.151 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4 8.30µs ± 5% 7.29µs ± 4% -12.08% (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4 7.34µs ± 4% 7.24µs ±19% ~ (p=0.690 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4 9.80µs ± 6% 9.49µs ±18% ~ (p=0.151 n=5+5)
CompileOnepass/^a(?:b|c)$-4 5.23µs ± 3% 4.80µs ±10% ~ (p=0.056 n=5+5)
CompileOnepass/^a(?:b?|c)$-4 8.26µs ± 3% 7.30µs ± 3% -11.62% (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4 9.18µs ± 2% 8.16µs ± 2% -11.06% (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4 6.16µs ± 3% 6.41µs ±13% ~ (p=0.548 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4 5.75µs ± 5% 5.50µs ±12% ~ (p=0.151 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4 7.65µs ± 5% 6.93µs ± 9% ~ (p=0.056 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4 13.0µs ± 1% 12.1µs ± 2% -6.91% (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4 9.20µs ± 4% 8.25µs ± 3% -10.38% (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4 254µs ± 2% 220µs ± 6% -13.47% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4 3.92kB ± 0% 3.41kB ± 0% -13.06% (p=0.008 n=5+5)
CompileOnepass/^abcd$-4 3.20kB ± 0% 2.75kB ± 0% -14.00% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4 3.85kB ± 0% 3.34kB ± 0% -13.31% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4 3.46kB ± 0% 2.95kB ± 0% -14.78% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4 4.20kB ± 0% 3.75kB ± 0% -10.67% (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4 3.10kB ± 0% 2.46kB ± 0% -20.62% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4 3.64kB ± 0% 3.13kB ± 0% -14.07% (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4 3.06kB ± 0% 2.48kB ± 0% -18.85% (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4 3.10kB ± 0% 2.52kB ± 0% -18.60% (p=0.008 n=5+5)
CompileOnepass/^(?:a*)$-4 3.21kB ± 0% 2.63kB ± 0% -17.96% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4 4.09kB ± 0% 3.64kB ± 0% -10.96% (p=0.008 n=5+5)
CompileOnepass/^...$-4 3.42kB ± 0% 2.91kB ± 0% -14.95% (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4 4.09kB ± 0% 3.64kB ± 0% -10.96% (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4 5.67kB ± 0% 4.39kB ± 0% -22.59% (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4 5.73kB ± 0% 4.32kB ± 0% -24.58% (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4 5.41kB ± 0% 4.06kB ± 0% -24.85% (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4 6.40kB ± 0% 5.31kB ± 0% -17.00% (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4 3.46kB ± 0% 2.88kB ± 0% -16.67% (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4 5.77kB ± 0% 4.36kB ± 0% -24.41% (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4 5.94kB ± 0% 4.59kB ± 0% -22.64% (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4 3.60kB ± 0% 3.15kB ± 0% -12.44% (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4 3.46kB ± 0% 2.94kB ± 0% -14.81% (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4 5.50kB ± 0% 4.09kB ± 0% -25.62% (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4 7.24kB ± 0% 6.15kB ± 0% -15.03% (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4 5.75kB ± 0% 4.47kB ± 0% -22.25% (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4 225kB ± 0% 135kB ± 0% -39.99% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4 52.0 ± 0% 49.0 ± 0% -5.77% (p=0.008 n=5+5)
CompileOnepass/^abcd$-4 44.0 ± 0% 41.0 ± 0% -6.82% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4 52.0 ± 0% 49.0 ± 0% -5.77% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4 47.0 ± 0% 44.0 ± 0% -6.38% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4 57.0 ± 0% 54.0 ± 0% -5.26% (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4 36.0 ± 0% 33.0 ± 0% -8.33% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4 49.0 ± 0% 46.0 ± 0% -6.12% (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4 39.0 ± 0% 36.0 ± 0% -7.69% (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4 44.0 ± 0% 41.0 ± 0% -6.82% (p=0.008 n=5+5)
CompileOnepass/^(?:a*)$-4 45.0 ± 0% 42.0 ± 0% -6.67% (p=0.008 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4 56.0 ± 0% 53.0 ± 0% -5.36% (p=0.008 n=5+5)
CompileOnepass/^...$-4 46.0 ± 0% 43.0 ± 0% -6.52% (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4 56.0 ± 0% 53.0 ± 0% -5.36% (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4 57.0 ± 0% 53.0 ± 0% -7.02% (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4 62.0 ± 0% 58.0 ± 0% -6.45% (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4 51.0 ± 0% 47.0 ± 0% -7.84% (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4 69.0 ± 0% 65.0 ± 0% -5.80% (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4 43.0 ± 0% 40.0 ± 0% -6.98% (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4 61.0 ± 0% 57.0 ± 0% -6.56% (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4 67.0 ± 0% 63.0 ± 0% -5.97% (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4 49.0 ± 0% 46.0 ± 0% -6.12% (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4 46.0 ± 0% 43.0 ± 0% -6.52% (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4 53.0 ± 0% 49.0 ± 0% -7.55% (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4 109 ± 0% 105 ± 0% -3.67% (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4 66.0 ± 0% 62.0 ± 0% -6.06% (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4 1.10k ± 0% 1.09k ± 0% -0.91% (p=0.008 n=5+5)
Fixes #19735
Change-Id: Ic68503aaa08e42fafcf7e11cf1f584d674f5ea7b
Reviewed-on: https://go-review.googlesource.com/38750
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
| |
|
|
|
|
|
|
|
|
| |
This deletes unused code and helpers from tests.
Change-Id: Ie31d46115f558ceb8da6efbf90c3c204e03b0d7e
Reviewed-on: https://go-review.googlesource.com/20927
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This is a subset of https://golang.org/cl/20022 with only the copyright
header lines, so the next CL will be smaller and more reviewable.
Go policy has been single space after periods in comments for some time.
The copyright header template at:
https://golang.org/doc/contribute.html#copyright
also uses a single space.
Make them all consistent.
Change-Id: Icc26c6b8495c3820da6b171ca96a74701b4a01b0
Reviewed-on: https://go-review.googlesource.com/20111
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
The one-pass transformation is structured as a search over the input
machine for conditions that violate the one-pass requisites. At each
iteration, we should fully explore all non-input paths that proceed from
the current instruction; this is implemented via recursive check calls.
But when we reach instructions that demand input (InstRune*), these
should be put onto the search queue.
Instead of searching this way, the routine previously (effectively)
proceeded through the machine one instruction at a time until finding an
Inst{Match,Fail,Rune*}, calling check on each instruction. This caused
bug #11905, where the transformation stopped before rewriting all
InstAlts as InstAltMatches.
Further, the check function unnecessarily recurred on InstRune*
instructions. (I believe this helps to mask the above bug.)
This change also deletes some unused functions and duplicate test cases.
Fixes #11905.
Change-Id: I5b0b26efea3d3bd01c7479a518b5ed1b886701cd
Reviewed-on: https://go-review.googlesource.com/17195
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
|
Preparation was in CL 134570043.
This CL contains only the effect of 'hg mv src/pkg/* src'.
For more about the move, see golang.org/s/go14nopkg.
|
