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: Optimize for inputs that are provably too short #31329

Closed
sylvinus opened this issue Apr 7, 2019 · 5 comments
Closed

regexp: Optimize for inputs that are provably too short #31329

sylvinus opened this issue Apr 7, 2019 · 5 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Go1.13

Comments

@sylvinus
Copy link
Contributor

sylvinus commented Apr 7, 2019 •
edited

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

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

@bcmills bcmills added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Apr 8, 2019
@bcmills
Copy link
Contributor

bcmills commented Apr 8, 2019

CC @rsc @matloob for regexp.

@dgryski
Copy link
Contributor

dgryski commented Apr 8, 2019

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

sylvinus commented Apr 8, 2019

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

@bradfitz bradfitz added this to the Go1.13 milestone May 15, 2019
@sylvinus sylvinus mentioned this issue Aug 5, 2019
Open
@gopherbot
Copy link

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

@golang golang locked and limited conversation to collaborators Aug 5, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Go1.13
Development

No branches or pull requests
5 participants
@bradfitz @sylvinus @dgryski @bcmills @gopherbot