Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
pracucci opened this issue Jun 26, 2020 · 4 comments
Open

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

pracucci opened this issue Jun 26, 2020 · 4 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Backlog

Comments

@pracucci
Copy link

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
Copy link
Contributor

martisch commented Jun 26, 2020 •
edited

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
Copy link
Member

mvdan commented Jun 26, 2020

Perhaps a duplicate of #21463? CC @sylvinus

@dmitshur
Copy link
Contributor

dmitshur commented Jul 1, 2020

/cc @matloob per owners.

@dmitshur dmitshur added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance labels Jul 1, 2020
@dmitshur dmitshur added this to the Backlog milestone Jul 1, 2020
@matloob
Copy link
Contributor

matloob commented Jul 1, 2020

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.

@pracucci pracucci mentioned this issue Jul 2, 2020
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Backlog
Development

No branches or pull requests
5 participants
@martisch @pracucci @dmitshur @mvdan @matloob