regexp/syntax: character class negation is slow

[func25]

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

[gabyhelp]

Related Issues and Documentation

• regexp/syntax: fix >10000x slower Regexp.String() #69304
• regexp: MatchString run time could be independent of the string length #39480 (closed)
• Dramatically speed down regexp while grow difficulty it #14167 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[gopherbot]

Change https://go.dev/cl/611300 mentions this issue: regexp/syntax: Optimize calcFlags() for OpCharClass fold case