eaburns/T — pull request #21 by eaburns (2014-12-20 01:22:05+00:00)
Title: Implement a better Regexp.Match.

Here's a comparison with the old implementation:
benchmark old ns/op new ns/op delta
BenchmarkRegexpMatchEasy0x32 1214 842 -30.64%
BenchmarkRegexpMatchEasy0x1K 32534 13973 -57.05%
BenchmarkRegexpMatchEasy1x32 1203 841 -30.09%
BenchmarkRegexpMatchEasy1x1K 32699 13950 -57.34%
BenchmarkRegexpMatchMediumx32 244 442 +81.15%
BenchmarkRegexpMatchMediumx1K 40159 21300 -46.96%
BenchmarkRegexpMatchHardx32 102727 14134 -86.24%
BenchmarkRegexpMatchHardx1K 4766294 272032 -94.29%

benchmark old MB/s new MB/s speedup
BenchmarkRegexpMatchEasy0x32 26.35 37.99 1.44x
BenchmarkRegexpMatchEasy0x1K 31.47 73.28 2.33x
BenchmarkRegexpMatchEasy1x32 26.59 38.01 1.43x
BenchmarkRegexpMatchEasy1x1K 31.32 73.40 2.34x
BenchmarkRegexpMatchMediumx32 4.09 2.26 0.55x
BenchmarkRegexpMatchMediumx1K 25.50 48.07 1.89x
BenchmarkRegexpMatchHardx32 0.31 2.26 7.29x
BenchmarkRegexpMatchHardx1K 0.21 3.76 17.90x

Here's a comparison with Go's implementation ☺:
benchmark old ns/op new ns/op delta
BenchmarkRegexpMatchEasy0x32 129 842 +552.71%
BenchmarkRegexpMatchEasy0x1K 332 13973 +4108.73%
BenchmarkRegexpMatchEasy1x32 109 841 +671.56%
BenchmarkRegexpMatchEasy1x1K 1034 13950 +1249.13%
BenchmarkRegexpMatchMediumx32 201 442 +119.90%
BenchmarkRegexpMatchMediumx1K 72060 21300 -70.44%
BenchmarkRegexpMatchHardx32 3893 14134 +263.06%
BenchmarkRegexpMatchHardx1K 114819 272032 +136.92%

benchmark old MB/s new MB/s speedup
BenchmarkRegexpMatchEasy0x32 246.50 37.99 0.15x
BenchmarkRegexpMatchEasy0x1K 3083.54 73.28 0.02x
BenchmarkRegexpMatchEasy1x32 292.74 38.01 0.13x
BenchmarkRegexpMatchEasy1x1K 989.54 73.40 0.07x
BenchmarkRegexpMatchMediumx32 4.97 2.26 0.45x
BenchmarkRegexpMatchMediumx1K 14.21 48.07 3.38x
BenchmarkRegexpMatchHardx32 8.22 2.26 0.27x
BenchmarkRegexpMatchHardx1K 8.92 3.76 0.42x

The Go implementation is much faster for easy matches, because it has a more sophisticated algorithm for skipping literal prefixes.