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).