regexp/syntax: character class negation is slow #69303
Description
I've submitted a benchmark and a fix at #69304.
New benchmark:
goos: darwin goarch: arm64 pkg: regexp/syntax cpu: Apple M1 BenchmarkString/^(.*);$|^;(.*)-8 4972814 232.1 ns/op 56 B/op 3 allocs/op BenchmarkString/(foo|bar$)x*-8 5602014 212.6 ns/op 56 B/op 3 allocs/op BenchmarkString/[^=,]-8 21872083 53.84 ns/op 8 B/op 1 allocs/op BenchmarkString/([^=,]+)=([^=,]+)-8 5726475 207.3 ns/op 56 B/op 3 allocs/op BenchmarkString/([^=,]+)=([^=,]+),.*-8 4588252 259.2 ns/op 56 B/op 3 allocs/op PASS ok regexp/syntax 7.603s Go version
1.23 darwin/arm64
What did you do?
I received a report at VictoriaMetrics/VictoriaMetrics#6911 and ran a benchmark for Regexp.String().
What did you see happen?
Some regexes are extremely slow, even when they're simple. The negate [^] causes calcFlags to run over a large character space to find a fold case.
goos: darwin goarch: arm64 pkg: regexp/syntax cpu: Apple M1 BenchmarkString/^(.*);$|^;(.*)-8 4594401 253.2 ns/op 56 B/op 3 allocs/op BenchmarkString/(foo|bar$)x*-8 5006730 236.1 ns/op 56 B/op 3 allocs/op BenchmarkString/[^=,]-8 256 4227434 ns/op 8 B/op 1 allocs/op BenchmarkString/([^=,]+)=([^=,]+)-8 151 8032660 ns/op 56 B/op 3 allocs/op BenchmarkString/([^=,]+)=([^=,]+),.*-8 146 8095255 ns/op 56 B/op 3 allocs/op PASS ok regexp/syntax 9.011s