GeezerVison

Summary

re.compile() on main is about 16-19% slower than 3.15 for ordinary
patterns. The regression comes from gh-152214, which added a set-operation
fusion pass to the pattern compiler (re._optimizer). That pass walks the
whole parsed tree unconditionally, looking for ||, && and --
constructs. Patterns without those constructs pay for the walk and get
nothing back.

This PR lets the parser record whether the tree contains anything the
fusion pass can actually rewrite, and skips the walk when it does not.

Root cause

Since gh-152214, re._optimizer.optimize() always calls _walk():

def optimize(pattern):
    _walk(pattern.data)
    return pattern

_walk() recurses over every node of the parsed tree and calls the
peepholes (_fuse_difference, ...) on each node. For a pattern like
\d{4}-\d{2}-\d{2} there is nothing to fuse: the walk visits the whole
tree and rewrites nothing. Profiling re.compile() over a corpus of 110
distinct patterns collected from the stdlib and site-packages shows no
pattern that the fusion pass rewrites.

Approach

The parser is the only place that knows whether a fusable construct is
present, so it records that in State.fusable:

• State.fusable starts as None, meaning "unknown": the tree was not
  produced by parse() (for example, re.Scanner assembles one by hand).
  The optimizer must still walk those trees.
• parse() sets it to False, and the parse paths that can produce
  something the optimizer understands set it to True: | between
  one-character alternatives (_parse_sub, _union), -- (_difference)
  and negative lookbehind ((?<!...)).
• optimize() walks only when the marker is not False.

Behaviour is unchanged: for 1504 patterns (both str and bytes, taken
from the stdlib, site-packages and test_re), the bytecode produced by
main and by this branch is identical, and the same 8 patterns fail to
compile with the same errors.

Skipping the walk based on a plain boolean would change behaviour for
hand-assembled trees: re.Scanner builds patterns without calling
parse(), and those still need optimization. The tri-state marker keeps
that path working.

Benchmarks

The official pyperformance regex_compile benchmark, run with pyperf
on Release builds, CPU affinity pinned to one core, Windows 11,
i5-12450H, CPython 3.16.0a1+ (a497a11c46):

Paired by run, this branch is 1.16x-1.19x faster than main and back in
the range of 3.15.2. The machine is noisy (the 3.15.2 runs differ by 25%
between themselves), so I would not read anything into the remaining
few percent.

Tests

• python -m test test_re: 173 tests, 4 skipped, all pass.
• New test test_optimizer_walk_only_for_fusable_patterns pins the
  parser marker for fusable and non-fusable patterns, and checks that a
  hand-built State() keeps the "must optimize" default.

AI assistance

Developed with AI assistance for the analysis, the patch draft and the
benchmark scripts. I reviewed every line, ran the tests and benchmarks
myself, and can explain the change in my own words.

• Issue: Regression in re.compile() performance #161125