Skip to content

regexp: implement backtracking search #4154

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.

Sign up for GitHub

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
Closed
rsc opened this issue Sep 25, 2012 · 11 comments
Closed

regexp: implement backtracking search #4154

rsc opened this issue Sep 25, 2012 · 11 comments
Labels
FrozenDueToAge Suggested Issues that may be good for new contributors looking for work to do.
Milestone
Go1.5

Comments

@rsc
Copy link
Contributor

rsc commented Sep 25, 2012 

In the spirit of RE2's multiple implementations, one possible way to make regexp faster
for easy regexps is to use actual backtracking. We'd only do this for those regexps
where we can compute that backtracking is okay. It would be something like the BitState
execution in RE2 but perhaps the details would be different. We do have a reliable
stack, unlike in C++.
@rsc
Copy link
Contributor Author

rsc commented Dec 10, 2012

Comment 1:

Labels changed: added size-l.

@robpike
Copy link
Contributor

robpike commented Mar 7, 2013

Comment 2:

Labels changed: removed go1.1maybe.

@rsc
Copy link
Contributor Author

rsc commented Jul 30, 2013

Comment 3:

Labels changed: added go1.3maybe.

@robpike
Copy link
Contributor

robpike commented Aug 20, 2013

Comment 4:

Labels changed: removed go1.3maybe.

@gopherbot
Copy link
Contributor

Comment 5 by jservletpro:

I have been wondering how C++ RE2 could be 13 times faster than Go in the benchmark
shootout. Now, I kind of know. C++ is dynamically assessing the cost of the execution
and chooses the algo that fits most. Almost like how SQL is executed in a database. I
read your papers regarding regexp multiple times last week and read the source of the
current "regexp" package. The currently code implements Thompson's algo faithfully. I
could not have imagined a better way to improve it. But adding "backtracking" to the
assessment will do! I hate to see Go's current regexp is slower than PHP and Python in
easy cases. Once "backtracking" is added, more Rubist, Python writer and PHP writer
would have one less excuse to switch over. 
Thanks for your outstanding papers that make me understand regexp more clearly!
Please add "backtracking" into the coming releases.
Best Regards,
GoPro

@rsc
Copy link
Contributor Author

rsc commented Nov 27, 2013

Comment 6:

Labels changed: added go1.3maybe.

@rsc
Copy link
Contributor Author

rsc commented Dec 4, 2013

Comment 7:

Labels changed: added release-none, removed go1.3maybe.

@rsc
Copy link
Contributor Author

rsc commented Dec 4, 2013

Comment 8:

Labels changed: added repo-main.

@ianlancetaylor
Copy link
Member

Comment 9:

Labels changed: added suggested, removed priority-later.

@rsc rsc added accepted Suggested Issues that may be good for new contributors looking for work to do. labels Apr 2, 2014
@rsc rsc self-assigned this Apr 2, 2014
@cespare
Copy link
Contributor

cespare commented Jan 7, 2015

@rsc How does your comment on https://golang.org/cl/2153 relate to this issue?

@bradfitz
Copy link
Contributor

bradfitz commented Jan 7, 2015

So I guess the community should work on their own regexp package if the stdlib one is going to be pure and slow?

@mikioh mikioh added this to the Go1.5 milestone Mar 23, 2015
@golang golang locked and limited conversation to collaborators Jun 24, 2016
@rsc rsc removed their assignment Jun 22, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge Suggested Issues that may be good for new contributors looking for work to do.
Projects
None yet
Milestone
Go1.5
Development

No branches or pull requests
7 participants
@bradfitz @mikioh @rsc @cespare @ianlancetaylor @robpike @gopherbot