Merge pull request #15 from eaburns/re1

Benchmark and optimize

There's a lot of work left to be done.
Though I'm not sure that I'm going to actually do it; this is probably fine for a while.

Here's a benchcmp comparing to Go's regexp package:
benchmark old ns/op new ns/op delta
BenchmarkRegexpMatchEasy0x32 129 1203 +832.56%
BenchmarkRegexpMatchEasy0x1K 332 32900 +9809.64%
BenchmarkRegexpMatchEasy1x32 109 1198 +999.08%
BenchmarkRegexpMatchEasy1x1K 1034 33711 +3160.25%
BenchmarkRegexpMatchMediumx32 201 241 +19.90%
BenchmarkRegexpMatchMediumx1K 72060 42668 -40.79%
BenchmarkRegexpMatchHardx32 3893 117365 +2914.77%
BenchmarkRegexpMatchHardx1K 114819 5673346 +4841.12%

benchmark old MB/s new MB/s speedup
BenchmarkRegexpMatchEasy0x32 246.50 26.60 0.11x
BenchmarkRegexpMatchEasy0x1K 3083.54 31.12 0.01x
BenchmarkRegexpMatchEasy1x32 292.74 26.70 0.09x
BenchmarkRegexpMatchEasy1x1K 989.54 30.38 0.03x
BenchmarkRegexpMatchMediumx32 4.97 4.13 0.83x
BenchmarkRegexpMatchMediumx1K 14.21 24.00 1.69x
BenchmarkRegexpMatchHardx32 8.22 0.27 0.03x
BenchmarkRegexpMatchHardx1K 8.92 0.18 0.02x

Obviously everything's a lot slower.
Go's regexp package has an optimization: if the regular expression has a literal prefix, it scans forward for that prefix before trying to evaluate the automata. (One of the added optimizations, "Quickly fail on obvious mis-matches," is a cheap form of this that works on a 1-rune literal prefix, which is what Sam and Acme seem to use.) Here's a comparison of re1 to a version of regexp with this optimization disabled:

benchmark old ns/op new ns/op delta
BenchmarkRegexpMatchEasy0x32 2006 1203 -40.03%
BenchmarkRegexpMatchEasy0x1K 68804 32900 -52.18%
BenchmarkRegexpMatchEasy1x32 1960 1198 -38.88%
BenchmarkRegexpMatchEasy1x1K 67572 33711 -50.11%
BenchmarkRegexpMatchMediumx32 220 241 +9.55%
BenchmarkRegexpMatchMediumx1K 76851 42668 -44.48%
BenchmarkRegexpMatchHardx32 3846 117365 +2951.61%
BenchmarkRegexpMatchHardx1K 124950 5673346 +4440.49%

benchmark old MB/s new MB/s speedup
BenchmarkRegexpMatchEasy0x32 15.95 26.60 1.67x
BenchmarkRegexpMatchEasy0x1K 14.88 31.12 2.09x
BenchmarkRegexpMatchEasy1x32 16.32 26.70 1.64x
BenchmarkRegexpMatchEasy1x1K 15.15 30.38 2.01x
BenchmarkRegexpMatchMediumx32 4.54 4.13 0.91x
BenchmarkRegexpMatchMediumx1K 13.32 24.00 1.80x
BenchmarkRegexpMatchHardx32 8.32 0.27 0.03x
BenchmarkRegexpMatchHardx1K 8.20 0.18 0.02x

re1 is actually faster for the easy cases, but still way slower for the hard cases. There is probably some other very important optimization that regexp is doing for the Kleene star (which, as far as I can see, is what makes the hard case hard).
Add tests for Kleene star.

Two things: test ** and test empty matches at the start of strings.

This surprised me, but perhaps it shouldn't have.
The expression a* matches the empty string at the beginning of "xyzaaa."
I expected it to match the a's.
However, that's not how Acme behaves.
In retrospect, it's better that it matches the empty,
otherwise the behavior is inconsistent
(why doesn't * return its earliest match?)
and it would be difficult to describe.
Omit needless nodes. Omit needless nodes. Omit needless nodes.

But not as good as I was hoping:
benchmark                         old ns/op     new ns/op     delta
BenchmarkRegexpMatchEasy0x32      1203          1214          +0.91%
BenchmarkRegexpMatchEasy0x1K      32900         32534         -1.11%
BenchmarkRegexpMatchEasy1x32      1198          1203          +0.42%
BenchmarkRegexpMatchEasy1x1K      33711         32699         -3.00%
BenchmarkRegexpMatchMediumx32     241           244           +1.24%
BenchmarkRegexpMatchMediumx1K     42668         40159         -5.88%
BenchmarkRegexpMatchHardx32       117365        102727        -12.47%
BenchmarkRegexpMatchHardx1K       5673346       4766294       -15.99%

benchmark                         old MB/s     new MB/s     speedup
BenchmarkRegexpMatchEasy0x32      26.60        26.35        0.99x
BenchmarkRegexpMatchEasy0x1K      31.12        31.47        1.01x
BenchmarkRegexpMatchEasy1x32      26.70        26.59        1.00x
BenchmarkRegexpMatchEasy1x1K      30.38        31.32        1.03x
BenchmarkRegexpMatchMediumx32     4.13         4.09         0.99x
BenchmarkRegexpMatchMediumx1K     24.00        25.50        1.06x
BenchmarkRegexpMatchHardx32       0.27         0.31         1.15x
BenchmarkRegexpMatchHardx1K       0.18         0.21         1.17x