proposal: regexp: Optimize fixed-length patterns

[sylvinus]

The regexp package has 3 different matchers (NFA, onepass, backtrack). One of them is selected depending on the pattern.

I suggest adding a 4th matcher optimized for fixed-length patterns like a.ab$ on strings.
I wrote a proof-of-concept implementation which provides constant-time matching relative to the size of the input string in many cases, whereas the current matchers from regexp perform linearly. Performance becomes close to what can be achieved with methods like strings.Index.

Here is a sample benchmark result of regexp.MatchString("a.ab$", strings.Repeat("a", M)+"b"):

M=1000
BenchmarkRegexpBypass/DotSuffix/bypass-8   	30000000	    109 ns/op  # New matcher implementation
BenchmarkRegexpBypass/DotSuffix/std-8      	   50000	  69882 ns/op  # Go's current standard library
BenchmarkRegexpBypass/DotSuffix/pcre-8     	  100000	  41359 ns/op  # PCRE
BenchmarkRegexpBypass/DotSuffix/rust-8     	20000000	    157 ns/op  # Rust regexp engine

I've added more details, benchmarks and tests (with fuzzing!) to the repository. Not sure how much should be inlined here.

The obvious cons of this proposal are:

• Adding more code to the standard library
• Adding more work at compilation time.

The pros are:

• Constant-time matching for many simple regexps (relative to the size of the input string)
• No overhead for regexps that are not supported
• Go's regexp package is usually considered immature performance-wise. This proposal plays a small role in fixing that by adding optimizations that can reasonably be expected from the end-user.
• This matcher keeps very little state and bypasses the mutex from regexp.go
• There are already 3 different matchers in the standard library (4 with the upcoming DFA), so adding a new one for a specific kind of patterns is not surprising.
• regexp.MatchString("(?:png|jpg)$") could obviously be rewritten as strings.HasSuffix("png") or strings.HasSuffix("jpg") but sometimes it is not practical because the pattern to be matched is user-supplied or part of a long list of patterns. Examples include interactive log search or lists of paths in HTTP routers.
• Limited risk due to exhaustive tests in the standard library and additional fuzzing

Feedback would be highly appreciated. Thanks!!

[ianlancetaylor]

CC @rsc

[cespare]

It would be interesting to examine a large corpus of Go code (perhaps https://github.com/rsc/corpus), extract all the regular expressions (at least the constant ones), and categorize them as to whether this matcher would apply.

[steren]

I looked in the BigQuery GitHub public dataset for constant regular expressions used with regexp.MatchString:

matcher applies	cnt
yes: ^([\w\d\s]+\|?)+$	206
yes: ^[\w\d\s\.]+$	47
yes: [\w\d\s\.]+\$	59
no: ^[^\\^\\$]+$	422
no: [\*\+\?]	1182
maybe	548

13% of the time, the matcher applies. 65% of the time, it does not.

Feel free to add comments or suggestions to the query, I can re-run it and update the results here.

[sylvinus]

Great idea & thanks for the stats!

Regarding BigQuery, I think we should also match calls to (Must)?Compile, as this proposal isn't limited to MatchString (though my prototype implementation currently is). Also, it might be difficult to decide if the matcher applies based only on a regexp, so another technique could be dumping all the patterns to a CSV and then testing them one at a time. Finally, the matcher has a "firstpass" mode of operation where it extracts anchored fixed-length prefixes and suffixes before delegating to the other matchers, so that should be counted separately.

I'm going to update the repository with a more exhaustive list of supported regexps to make things clearer.

[cznic]

The pros are:

• Constant-time matching for many simple regexps

I'm not aware of any theory making that possible. Can you please explain?

[sylvinus]

I have updated the repository with a clearer table of supported patterns.

@cznic I meant constant-time like strings.HasSuffix is. I'm not sure of the exact complexity of string slicing in Go, but for practical purposes I have observed it to be constant. I made a chart of the benchmark of regexp.MatchString("a.ab$", strings.Repeat("a", M)+"b") as an example:

[cznic]

I meant constant-time like strings.HasSuffix is.

I don't think strings.HasSuffix is O(1) either.

I made a chart of the benchmark ...

Nice chart, but the N parameter is used in the wrong place. Actually, the data are for constant N, no wonder it flat-lined.

More importantly, theory needs to talk. Can you refer to a theory enabling/explaining constant time regexp matching?

Don't get me wrong, none of the above means your contribution does not improve performance.

[sylvinus]

I don't think strings.HasSuffix is O(1) either.

I'm not sure if it is in theory, but I just added a benchmark for it and it does seem constant even with a 1Gb string.

The actual function being used to read the input string for a.ab$ is utf8.DecodeLastRuneInString, I'd be interested to know its theoretical complexity.

Nice chart, but the N parameter is used in the wrong place. Actually, the data are for constant N, no wonder it flat-lined.

Sorry if I missed something. I'm using the strings returned by getString(n int) as input, those do seem to grow and I'm sending the same input to both implementations so I'm not sure there is an error.

I'm happy to change "constant" to something else if it's not actually the case but so far I haven't seen any linear behaviour (relative to the size of the input string) in the benchmarks for these simple patterns.

[cznic]

I'm not sure if it is in theory, but I just added a benchmark for it and it does seem constant even with a 1Gb string.

The N you're looking for is the length of the matched pattern, not the length of the string searched. But you're using a constant length pattern, so you can only get a constant result.

Normally, two parameters should be considered, length of the pattern (let's call it N) and length of the string (M). If the computation can take advantage of knowing the location of the end of the string in O(1) and perform the match from the end, it reduces to considering N only. But I'm not aware of any way to perform the match in O(1) wrt to N only. Therefore, regardless of the complexity wrt M, the overall one cannot be constant time. Known theory says O(NM), which is O(N) for strings.HasSuffix.

[sylvinus]

@cznic OK I see what you mean. I did mean "constant" relative to the size of the input string only. I will add that clarification where needed and change N to M to match theory. I'm obviously not claiming it to be constant relative to the size of the pattern itself. Thanks!

[steren]

I used this query to extract constant regular expressions used with MatchString, Compile and MustCompile in the the GitHub public dataset: CSV file

Feel free to run an analysis on it.

[sylvinus]

Thanks a lot @steren! I just added the dump to the tests, here are the stats:

Total occurences                    76341
Invalid                             2545 (3.33%)
Unsupported                         48006 (62.88%)
Supported total                     25790 (33.78%)
 Supported with byPassProgLinear    14714 (19.27%)
 Supported with byPassProgAlternate 450 (0.59%)
 Supported with byPassProgFirstPass 10626 (13.92%)

33% is much higher than I expected!