Dramatically speed down regexp while grow difficulty it

[rekby]

When I try to search some more difficult then simple substring (for example one of two substring) speed of regexp will very very slower.

For emaxple few simple regexps for 10Mbytes empty array

package main

import (
    "fmt"
    "regexp"
    "time"
)
var f []byte

func test(s string) {
    r := regexp.MustCompile(s)
    fmt.Print(s + ": ")
    start := time.Now()
    r.FindAllIndex(f, -1)
    fmt.Println(time.Now().Sub(start))

}

func main() {
    f = make([]byte, 10*1024*1024)
    test("aaa")
    test("bbb")
    test("aaa.*")
    test("aaa.*bbb")
    test("aaa|bbb")
    test("aaa|bbb|ccc")
}

Output for my laptop:

aaa: 2.265268ms
bbb: 1.154115ms
aaa.*: 1.053976ms
aaa.*bbb: 995.438µs
aaa|bbb: 1.675626998s
aaa|bbb|ccc: 2.518271136s

[bradfitz]

It's true that some regexps are faster than others. But they all execute in linear time with the length of the string being matched.

This bug is too general to be actionable. There are more specific regexp performance bugs open, such as #11646.