regexp: Optimize for inputs that are provably too short

[sylvinus]

I'm following up on my work on regexp performance from #21463 with a couple smaller patches. This one is somewhat related.

For many patterns we can compute the minimum length of the input at compile time. For instance, an HTTP router might use a pattern like \/(path1|path2)\/(.+)\.html, which has a minimum input length of 13 bytes.

If the input is shorter than that, as may happen quite frequently, we can return early and get a huge speedup.

Some benchmarks are included in the CL.

Feedbacks welcome!

[gopherbot]

Change https://golang.org/cl/171023 mentions this issue: regexp: optimize for provably too short inputs

[bcmills]

CC @rsc @matloob for regexp.

[dgryski]

It's interesting to note that Perl's regex engine contains a number of these kinds of fail-fast optimizations: https://perldoc.perl.org/perlreguts.html#Peep-hole-Optimisation-and-Analysis

[sylvinus]

@dgryski yes it does! I plan to implement many of them if there's interest.

[gopherbot]

Change https://golang.org/cl/188800 mentions this issue: regexp: optimize for provably too long inputs