code review 5134049: regexp: speedups

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

[rsc, 2011-09-27 18:31:36]

Hello r (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[r, 2011-09-27 18:33:24]

LGTM but how about a couple of other cases for benchmarks.
- prefix that matches
- prefix that doesn't match
- maybe some parens?

[bradfitz, 2011-09-27 18:35:54]

Which is old?  The "was" number or the "Old" number?

On Tue, Sep 27, 2011 at 11:31 AM, <rsc@golang.org> wrote:

> Reviewers: r,
>
> Message:
> Hello r (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://go.googlecode.com/hg/
>
>
> Description:
> regexp: speedups
>
> regexp.BenchmarkMatch      162141 ns/op    6.17 MB/s (was 4.17 MB/s)
> regexp.BenchmarkOldMatch   186438 ns/op    5.36 MB/s
>
> Please review this at
http://codereview.appspot.com/**5134049/<http://codereview.appspot.com/5134049/>
>
> Affected files:
>  M src/pkg/regexp/exec.go
>  M src/pkg/regexp/exec_test.go
>  M src/pkg/regexp/regexp.go
>  M src/pkg/regexp/syntax/compile.**go
>  M src/pkg/regexp/syntax/prog.go
>  M src/pkg/regexp/syntax/prog_**test.go
>
>
>

[rsc, 2011-09-27 18:44:47]

The Old number is old/regexp.
The was number is regexp before this CL.

[rsc, 2011-09-28 15:44:32]

Hello r@golang.org, bradfitz@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-09-28 15:48:30]

There are new numbers in the CL description.

[r, 2011-09-28 15:49:31]

LGTM

[bradfitz, 2011-09-28 15:52:05]

http://codereview.appspot.com/5134049/diff/12001/src/pkg/regexp/exec_test.go
File src/pkg/regexp/exec_test.go (right):

http://codereview.appspot.com/5134049/diff/12001/src/pkg/regexp/exec_test.go#...
src/pkg/regexp/exec_test.go:661: if rand.Intn(30) == 0 {
your benchmarks depend on random input?

I know the random has a fixed seed, but still... seems sketch.  If you run
-test.Bench=That vs. -test.Bench=This|That, now That potentially changes speed?

Seems like your benchmark functions should fix the seed at least.

[rsc, 2011-09-28 15:59:57]

These benchmarks match the RE2 ones.
It doesn't matter what the input is.
A kilobyte or 32 MB of random data is
not distinguishable from another one
for these tests.

Russ

[rsc, 2011-09-28 16:00:33]

*** Submitted as http://code.google.com/p/go/source/detail?r=11940a304fb1 ***

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
http://codereview.appspot.com/5134049