Thanks. Could you explore variations, in particular for overall parse time, like not doing any reduction (other than maybe removing Group) until the end, and then reducing until it stabilizes?

I explored several variations of deferring reduction to the end. Here's a summary of the experiments and findings.

Setup: 15,817 unique regex patterns from a real-world JSON corpus, Release build, DOTNET_TieredCompilation=0, 15 iterations, 5-round warmup. All timings are average per-pattern cost in microseconds (mean +/- 1 stddev across iterations).

Experiment 1: Baselines

Measured the cost of FinalReduce as implemented in this PR (reduce during parse + one FinalReduce pass at end):

Experiment 2: Phase profiling (this PR)

Instrumented each phase to understand where time is spent:

Experiment 3: Naive deferral -- ReduceMinimal in AddChild

Replaced Reduce() in AddChild/InsertChild with a minimal reducer (Group unwrap + 0/1-child Concatenation/Alternation unwrap + IgnoreCase strip), keeping full Reduce only in ReplaceChild (used by FinalReduce).

Result: 183/431 PatternsReduceIdentically tests fail. The optimization passes (FindAndMakeLoopsAtomic, EliminateEndingBacktracking) produce different results when operating on unreduced trees.

Adding a FinalReduce call before the optimization passes reduced failures to 23. The remaining 23 fail because reduction methods like ReduceAlternation internally create new nodes via AddChild and depend on those nodes being fully reduced. So swapping Reduce for ReduceMinimal in AddChild breaks the reducers themselves.

Experiment 4: Parser-level deferral -- AddChildMinimal for parser only

Created a separate AddChildMinimal method (calls ReduceMinimal) and changed all 13 AddChild calls in RegexParser to use it. AddChild itself still calls full Reduce(), so reduction methods work correctly. FinalReduce runs both before and after the optimization passes. Also moved the initial FinalReduce outside the RTL/NonBacktracking guard since those patterns also need reduction.

Code: danmoseley@75612fc (diff vs this PR)

Result: All 1,043 tests pass, but slower:

Deferred phase breakdown:

Deferring saves ~0.4 μs/pattern during parse but adds 0.8 μs for the pre-optimization FinalReduce tree walk.

Conclusions

The deferred approach is both more complex and slower:

1. More code: Needs a new AddChildMinimal method, changes to 13 parser call sites, FinalReduce moved outside the RTL/NonBacktracking guard, and two full tree-walk reduction passes instead of one.
2. Slower: 4.29 vs 4.08 μs/pattern (5% regression, statistically significant). The parse-time savings from skipping full Reduce are more than offset by the additional tree walk.
3. Fundamental constraint: Reduction methods (ReduceAlternation, etc.) create new nodes via AddChild and depend on full reduction happening there. You can't simply remove Reduce from AddChild -- you need a two-track system (minimal for parser, full for reducers).

The current PR approach -- reduce during parse + one FinalReduce at end -- appears to be the simplest correct approach. The integrated parse-time reduction is essentially free (no extra tree walk), and only one post-optimization FinalReduce pass is needed.

Doing some more investigations

• Recap how many patterns actually benefit from FinalReduce and whether it might be a better tradeoff to not change this at all
• Is there a way to make FinalReduce cheaper (one possibility, dirty flag to skip patterns that don't benefit)
• Are there real world patterns where FinalReduce is a significant cost ie., what is the cost distribution tail.

Follow-up: Deep analysis of FinalReduce impact and cost distribution

After the initial experiments, I ran three deeper investigations to understand FinalReduce's real-world behavior and whether the overhead can be reduced.

Investigation 1: How many patterns actually benefit from FinalReduce?

Tested all 15,810 parseable patterns from the corpus. FinalReduce produces a different tree for only 88 patterns (0.6%). Those 88 patterns had 104 total nodes changed (avg 1.2 per pattern). The remaining 99.4% get a full tree walk that finds nothing to change.

Investigation 2: Can we skip FinalReduce when it's not needed?

I prototyped a dirty-flag approach: set a ThreadStatic boolean in MakeLoopAtomic and EliminateEndingBacktracking when they create potentially-reducible structures (Atomic wrappers, Empty/Multi node conversions, type changes under existing Atomic parents). Then skip FinalReduce when the flag isn't set.

Results:

• 79% of patterns skip FinalReduce entirely (flag not set)
• The flag requires annotations in 6 locations with precise conditions (e.g., "set flag only when parent is Atomic")
• All 431 PatternsReduceIdentically tests still pass

The early-exit saves ~0.3 us/pattern, cutting overhead from +16% to +8%. However, it requires maintaining dirty-flag annotations across 6 code locations in two complex methods, and the conditions are subtle (e.g., only flag when parent is Atomic). Missing a flag causes silent correctness loss. Not worth the complexity for <0.3 us.

Investigation 3: Per-pattern FinalReduce cost distribution

Measured FinalReduce cost individually for each of the 15,810 patterns:

Distribution buckets:

The top 1% of patterns (158) account for 15.3% of total FinalReduce cost. The expensive tail is dominated by large alternation patterns -- timezone name lists, mobile UA detection strings, SQL keyword lists, and cron expressions. These patterns have deep trees with many nodes to walk.

Conclusions

1. FinalReduce's overhead is dominated by the tree walk, not actual reduction. 99.4% of patterns walk the tree and find nothing.
2. An early-exit optimization is possible but the complexity-to-benefit ratio is poor: 6 flag locations for 0.3 us savings.
3. The per-pattern cost is well-behaved: median 0.3 us, p99 at 4.5 us. The expensive tail (>10 us) affects only 0.2% of patterns and those are inherently large patterns where all parse phases are proportionally more expensive.
4. The current approach (unconditional FinalReduce) is the right tradeoff: simple, correct, and the 0.57 us/pattern overhead is small relative to the 3.51 us baseline parse cost.