Feature or enhancement
Proposal:
When the regex engine tries the alternatives of a|b|..., it skips an alternative without entering it if the alternative starts with a literal or a character set that cannot match the current character. But the check only looks at the very first opcode, so alternatives starting with a capturing group — (foo)|(bar), and in particular tokenizer-style patterns (?P<KW>...)|(?P<NUM>...)|... — are never skipped: every mismatching alternative is entered, writes its group mark, fails and backtracks. The same applies to alternatives starting with a repeat with a nonzero minimum, like a+x|b+y.
Extend the quick check to look through MARK ops and into the repeated item of such a repeat. Plain alternations are unaffected: the existing checks are performed first and unchanged.
Benchmarks with realistic patterns, ./python -m timeit, non-PGO release builds:
| Benchmark |
main |
patched |
speedup |
dispatch on (GET)|(HEAD)|(POST)|(PUT)|(PATCH)|(DELETE) |
114 nsec |
93 nsec |
1.23x |
number/word/space lexer ([0-9]+)|([A-Za-z]+)|([ \t]+) |
970 nsec |
913 nsec |
1.06x |
the tokenizer example from the re docs, one statement |
1.86 usec |
1.78 usec |
1.04x |
string.Template.substitute |
1.04 usec |
1.02 usec |
1.02x |
Commands
./python -m timeit -s "import re; m = re.compile('(GET)|(HEAD)|(POST)|(PUT)|(PATCH)|(DELETE)').fullmatch" "m('DELETE')"
./python -m timeit -s "import re; f = re.compile(r'([0-9]+)|([A-Za-z]+)|([ \t]+)').finditer" "for m in f('x1 = 42 + foo'): pass"
./python -m timeit -s "import re; spec = [('NUMBER', r'\d+(?:\.\d*)?'), ('ASSIGN', r':='), ('ID', r'[A-Za-z]+'), ('OP', r'[+\-*/]'), ('NEWLINE', r'\n'), ('SKIP', r'[ \t]+'), ('MISMATCH', r'.')]; f = re.compile('|'.join('(?P<%s>%s)' % p for p in spec)).finditer; line = 'total := total + price * quantity\n'" "for m in f(line): m.lastgroup"
./python -m timeit -s "from string import Template; t = Template('Dear \$name, your order #\$order ships \$date.'); m = {'name':'Ada','order':'1042','date':'Monday'}" "t.substitute(m)"Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Linked PRs
Feature or enhancement
Proposal:
When the regex engine tries the alternatives of
a|b|..., it skips an alternative without entering it if the alternative starts with a literal or a character set that cannot match the current character. But the check only looks at the very first opcode, so alternatives starting with a capturing group —(foo)|(bar), and in particular tokenizer-style patterns(?P<KW>...)|(?P<NUM>...)|...— are never skipped: every mismatching alternative is entered, writes its group mark, fails and backtracks. The same applies to alternatives starting with a repeat with a nonzero minimum, likea+x|b+y.Extend the quick check to look through MARK ops and into the repeated item of such a repeat. Plain alternations are unaffected: the existing checks are performed first and unchanged.
Benchmarks with realistic patterns,
./python -m timeit, non-PGO release builds:(GET)|(HEAD)|(POST)|(PUT)|(PATCH)|(DELETE)([0-9]+)|([A-Za-z]+)|([ \t]+)redocs, one statementstring.Template.substituteCommands
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Linked PRs