Add benchmarks.

Here's a benchcmp comparison with go's standard regexp package:
benchmark                         old ns/op     new ns/op     delta
BenchmarkRegexpMatchEasy0x32      129           34426         +26586.82%
BenchmarkRegexpMatchEasy0x1K      332           1074961       +323683.43%
BenchmarkRegexpMatchEasy1x32      109           33746         +30859.63%
BenchmarkRegexpMatchEasy1x1K      1034          1039288       +100411.41%
BenchmarkRegexpMatchMediumx32     201           2288          +1038.31%
BenchmarkRegexpMatchMediumx1K     72060         1132776       +1471.99%
BenchmarkRegexpMatchHardx32       3893          944609        +24164.29%
BenchmarkRegexpMatchHardx1K       114819        45691695      +39694.54%

benchmark                         old MB/s     new MB/s     speedup
BenchmarkRegexpMatchEasy0x32      246.50       0.93         0.00x
BenchmarkRegexpMatchEasy0x1K      3083.54      0.95         0.00x
BenchmarkRegexpMatchEasy1x32      292.74       0.95         0.00x
BenchmarkRegexpMatchEasy1x1K      989.54       0.99         0.00x
BenchmarkRegexpMatchMediumx32     4.97         0.44         0.09x
BenchmarkRegexpMatchMediumx1K     14.21        0.90         0.06x
BenchmarkRegexpMatchHardx32       8.22         0.03         0.00x
BenchmarkRegexpMatchHardx1K       8.92         0.02         0.00x

Clearly there's some work to be done ☺
Remove allocations in the match loop.

With and without:
benchmark                         old ns/op     new ns/op     delta
BenchmarkRegexpMatchEasy0x32      34046         27073         -20.48%
BenchmarkRegexpMatchEasy0x1K      1064493       764539        -28.18%
BenchmarkRegexpMatchEasy1x32      33871         23985         -29.19%
BenchmarkRegexpMatchEasy1x1K      1034456       632842        -38.82%
BenchmarkRegexpMatchMediumx32     2233          6010          +169.14%
BenchmarkRegexpMatchMediumx1K     1093939       729869        -33.28%
BenchmarkRegexpMatchHardx32       956303        499880        -47.73%
BenchmarkRegexpMatchHardx1K       45523530      23684231      -47.97%

benchmark                         old MB/s     new MB/s     speedup
BenchmarkRegexpMatchEasy0x32      0.94         1.18         1.26x
BenchmarkRegexpMatchEasy0x1K      0.96         1.34         1.40x
BenchmarkRegexpMatchEasy1x32      0.94         1.33         1.41x
BenchmarkRegexpMatchEasy1x1K      0.99         1.62         1.64x
BenchmarkRegexpMatchMediumx32     0.45         0.17         0.38x
BenchmarkRegexpMatchMediumx1K     0.94         1.40         1.49x
BenchmarkRegexpMatchHardx32       0.03         0.06         2.00x
BenchmarkRegexpMatchHardx1K       0.02         0.04         2.00x
Quickly fail on obvious non-matches.

With and without:
benchmark                         old ns/op     new ns/op     delta
BenchmarkRegexpMatchEasy0x32      27073         5603          -79.30%
BenchmarkRegexpMatchEasy0x1K      764539        47084         -93.84%
BenchmarkRegexpMatchEasy1x32      23985         4238          -82.33%
BenchmarkRegexpMatchEasy1x1K      632842        45276         -92.85%
BenchmarkRegexpMatchMediumx32     6010          4406          -26.69%
BenchmarkRegexpMatchMediumx1K     729869        77179         -89.43%
BenchmarkRegexpMatchHardx32       499880        489945        -1.99%
BenchmarkRegexpMatchHardx1K       23684231      23179424      -2.13%

benchmark                         old MB/s     new MB/s     speedup
BenchmarkRegexpMatchEasy0x32      1.18         5.71         4.84x
BenchmarkRegexpMatchEasy0x1K      1.34         21.75        16.23x
BenchmarkRegexpMatchEasy1x32      1.33         7.55         5.68x
BenchmarkRegexpMatchEasy1x1K      1.62         22.62        13.96x
BenchmarkRegexpMatchMediumx32     0.17         0.23         1.35x
BenchmarkRegexpMatchMediumx1K     1.40         13.27        9.48x
BenchmarkRegexpMatchHardx32       0.06         0.07         1.17x
BenchmarkRegexpMatchHardx1K       0.04         0.04         1.00x
Cache machines in the Regexp.

With and without:
benchmark                         old ns/op     new ns/op     delta
BenchmarkRegexpMatchEasy0x32      5603          1366          -75.62%
BenchmarkRegexpMatchEasy0x1K      47084         41247         -12.40%
BenchmarkRegexpMatchEasy1x32      4238          1368          -67.72%
BenchmarkRegexpMatchEasy1x1K      45276         40968         -9.51%
BenchmarkRegexpMatchMediumx32     4406          247           -94.39%
BenchmarkRegexpMatchMediumx1K     77179         71019         -7.98%
BenchmarkRegexpMatchHardx32       489945        490462        +0.11%
BenchmarkRegexpMatchHardx1K       23179424      23500015      +1.38%

benchmark                         old MB/s     new MB/s     speedup
BenchmarkRegexpMatchEasy0x32      5.71         23.42        4.10x
BenchmarkRegexpMatchEasy0x1K      21.75        24.83        1.14x
BenchmarkRegexpMatchEasy1x32      7.55         23.38        3.10x
BenchmarkRegexpMatchEasy1x1K      22.62        24.99        1.10x
BenchmarkRegexpMatchMediumx32     0.23         4.04         17.57x
BenchmarkRegexpMatchMediumx1K     13.27        14.42        1.09x
BenchmarkRegexpMatchHardx32       0.07         0.07         1.00x
BenchmarkRegexpMatchHardx1K       0.04         0.04         1.00x
A bunch of minor optimizations.

With and without (helps a lot on the "hard" cases):
benchmark                         old ns/op     new ns/op     delta
BenchmarkRegexpMatchEasy0x32      1366          1205          -11.79%
BenchmarkRegexpMatchEasy0x1K      41247         32430         -21.38%
BenchmarkRegexpMatchEasy1x32      1368          1191          -12.94%
BenchmarkRegexpMatchEasy1x1K      40968         32490         -20.69%
BenchmarkRegexpMatchMediumx32     247           240           -2.83%
BenchmarkRegexpMatchMediumx1K     71019         40530         -42.93%
BenchmarkRegexpMatchHardx32       490462        110919        -77.38%
BenchmarkRegexpMatchHardx1K       23500015      5487409       -76.65%

benchmark                         old MB/s     new MB/s     speedup
BenchmarkRegexpMatchEasy0x32      23.42        26.55        1.13x
BenchmarkRegexpMatchEasy0x1K      24.83        31.57        1.27x
BenchmarkRegexpMatchEasy1x32      23.38        26.86        1.15x
BenchmarkRegexpMatchEasy1x1K      24.99        31.52        1.26x
BenchmarkRegexpMatchMediumx32     4.04         4.16         1.03x
BenchmarkRegexpMatchMediumx1K     14.42        25.26        1.75x
BenchmarkRegexpMatchHardx32       0.07         0.29         4.14x
BenchmarkRegexpMatchHardx1K       0.04         0.19         4.75x
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).