Improve matching of regular expressions with literals

[lpereira]

The match function in the _sre module works by iterating over the pattern, one op at a time, advancing the input pointer if necessary. While this works just fine, we're not taking advantage of vector instructions, that would (potentially) improve the performance.

One of my ideas here is, if the pattern has a SRE_OP_LITERAL opcode, we use a fast search mode (e.g. memmem(), memchr(), or similar things). If the literal isn't found in that alternation, we can skip to the next one. If the literal is found, we have three possible options:

1. The SRE_OP_LITERAL opcode is the first thing in that alternation. In this case, we proceed forwards as usual.
2. There is something before SRE_OP_LITERAL in that alternation, but the pattern ends in that literal. In this case, we match the pattern backwards until we reach the beginning of the pattern.
3. There's something both before and after the SRE_OP_LITERAL. In this case, we both go backwards, and then forwards.

In the cases we go backwards, we can stop iterating if we find another SRE_OP_LITERAL in the same alternation. This is not necessary to do when going forwards because we're already handling that.

If we have a run of literals, it should be possible to combine them into a single SRE_OP_LITERAL_RUN or something like that, and use a fast substring search rather than searching a single character/unicode rune.

(The same ideas are valid for the locale-ignoring versions, and even more so, in fact.)

I believe this can yield a sizable performance improvement to how we match regular expressions, and would be a good place to start. There are many other things that can be explored, such as:

• For repeating literals with a reasonable length (e.g. a{1,8}), we can transform this into two instructions: in the previous example, aa{0,7}, which would generate a SRE_OP_LITERAL(a) and a SRE_OP_REPEAT_ONE(a, 0, 7). This would let us take advantage of the already optimized SRE_OP_LITERAL before we get into the current implementation for SRE_OP_REPEAT_ONE.
• For ranges, e.g. [0-7a-f], generate the range and use something like strspn() (or something similar that would work with unicode characters) to find any ocurrence of, in the previous example, any character from the string "01234567abcdef".
• And so on and so forth. The idea is to find other opportunities that would let us use fast scanning instructions or functions provided by the C standard library that take advantage of vector instructions, and prioritize those operations first before we go back to the usual implementation of other SRE ops.

Thoughts?

[gvanrossum]

I worry that it's hard to exactly replicate the matching semantics of forward matches when going backwards, unless it's something simple like .*abc. Could you prototype this just for case (1) and do a little microbenchmarking?

[lpereira]

Yeah, I imagined this would be a problem. An alternative to going backwards is using a fast byte scan to find a literal and skip the alternation if it wouldn't match anyway; everything else would be the same as today, retaining the semantics.