You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
What does 'go version' print?
go version devel +82edfcdee1bc Thu Mar 06 13:15:09 2014 +1100 linux/amd64
What steps reproduce the problem?
If you run `^(?:x{1,1000}){1,1000}$` on "xxxxxxxx ...(5000 times)... y",
FindString does not return. If the repetition is short, it will return immediately.
http://play.golang.org/p/uh55Y8ajc6
The text was updated successfully, but these errors were encountered:
It's not exponential. You can't prove an exponential run time with a single data point.
It's linear in the size of the repetition with a very large constant (derived from the
size of the regexp, and the size of that regexp is ~ 1 million).
That said, IsOnePass - added during the 1.3 cycle - is taking far too long to analyze
the regexp and is blowing out the stack. That needs to be fixed for 1.3.
package main
import (
"regexp"
"strings"
"time"
"fmt"
)
func main() {
re := regexp.MustCompile(`^(?:x{1,1000}){1,1000}$`)
println("compiled")
for i := 5; i < 5000; i *= 2 {
s := strings.Repeat("x", i) + "y"
t := time.Now()
re.FindString(s)
fmt.Println(i, time.Since(t))
}
}
The text was updated successfully, but these errors were encountered: