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

regexp: implement backtracking search #4154

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
Assignees
Milestone

Comments

@rsc
Copy link
Contributor

@rsc 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 rsc commented Dec 10, 2012

Comment 1:

Labels changed: added size-l.

@robpike
Copy link
Contributor

@robpike robpike commented Mar 7, 2013

Comment 2:

Labels changed: removed go1.1maybe.

@rsc
Copy link
Contributor Author

@rsc rsc commented Jul 30, 2013

Comment 3:

Labels changed: added go1.3maybe.

@robpike
Copy link
Contributor

@robpike robpike commented Aug 20, 2013

Comment 4:

Labels changed: removed go1.3maybe.

@gopherbot
Copy link

@gopherbot gopherbot commented Sep 23, 2013

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 rsc commented Nov 27, 2013

Comment 6:

Labels changed: added go1.3maybe.

@rsc
Copy link
Contributor Author

@rsc rsc commented Dec 4, 2013

Comment 7:

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

@rsc
Copy link
Contributor Author

@rsc rsc commented Dec 4, 2013

Comment 8:

Labels changed: added repo-main.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 2, 2014

Comment 9:

Labels changed: added suggested, removed priority-later.

@rsc rsc self-assigned this Apr 2, 2014
@cespare
Copy link
Contributor

@cespare 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 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?

@robpike robpike closed this in 9323862 Mar 23, 2015
@mikioh mikioh added this to the Go1.5 milestone Mar 23, 2015
@golang golang locked and limited conversation to collaborators Jun 24, 2016
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.