regexp: fast path for prefix/suffix literals matching on anchored regexps

[pracucci]

To my understanding, currently there's no fast path for anchored regular expressions starting/ending with a literal, like ^something.*$ or ^.*something$. I'm wondering if you have considered adding a specific optimisation for this use case.

Use case

I'm raising this issue, because in Prometheus we do a large use of anchored regexps (for labels matching) and having prefix/suffix literals in the regex looks to be quite a common use case.

In past few days I've worked on a small optimization in Prometheus (PR) to detect safe cases when we can circuit break the regex matching with a strings.HasPrefix() and strings.HasSuffix(), and it showed to bring significant benefits for our specific use case.

[martisch]

As an extension the regexp does not even need to be anchored. Some overuses of regex I have seen are just matching a constant string which can usually optimized by using strings.Contains for the simple Match(String) case.

[mvdan]

Perhaps a duplicate of #21463? CC @sylvinus

[dmitshur]

/cc @matloob per owners.

[matloob]

Yeah, I think this would be addressed through a combination of #21743, and Russ's first suggestion in #21463 (comment).

I think in the case of ^something.*$, it looks like go through the fast path of checking a literal prefix, and then get bogged down scanning the rest of the string to handle the .*$. And if we could scan backwards as in #21743, we'd be able to handle the second case too.