eaburns/T — pull request #15 by eaburns (2014-12-15 12:06:54+00:00)
Title: 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).