StressTestDeepNestingOfConcat takes a lot longer on NonBacktracking than other engines

[stephentoub]

Here's how long the various tests took with the different engines:

StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"[a-d]?[a-e]?[a-f]?[a-g]?[a-h]?\", anchor: \"$\", input: \"abcda\", pattern_repetition: 400, input_repetition: 4): 42.1850199
StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"[a-e]*\", anchor: \"$\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 20): 22.9797034
StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"[a-z]\", anchor: \"\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 400): 2.0449147
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"[a-e]*\", anchor: \"$\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 20): 0.8606951
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"[a-e]*\", anchor: \"$\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 20): 0.6647422
StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"(a|A)\", anchor: \"\", input: \"aAaAa\", pattern_repetition: 2000, input_repetition: 400): 0.6331361
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"[a-d]?[a-e]?[a-f]?[a-g]?[a-h]?\", anchor: \"$\", input: \"abcda\", pattern_repetition: 400, input_repetition: 4): 0.6089077
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"[a-d]?[a-e]?[a-f]?[a-g]?[a-h]?\", anchor: \"$\", input: \"abcda\", pattern_repetition: 400, input_repetition: 4): 0.6065388
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"(a|A)\", anchor: \"\", input: \"aAaAa\", pattern_repetition: 2000, input_repetition: 400): 0.3276416
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"(a|A)\", anchor: \"\", input: \"aAaAa\", pattern_repetition: 2000, input_repetition: 400): 0.3066884
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"[a-z]\", anchor: \"\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 400): 0.1756175
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"[a-z]\", anchor: \"\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 400): 0.1623067

[ghost]

Tagging subscribers to this area: @eerhardt, @dotnet/area-system-text-regularexpressions
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Here's how long the various tests took with the different engines:

StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"[a-d]?[a-e]?[a-f]?[a-g]?[a-h]?\", anchor: \"$\", input: \"abcda\", pattern_repetition: 400, input_repetition: 4): 42.1850199
StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"[a-e]*\", anchor: \"$\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 20): 22.9797034
StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"[a-z]\", anchor: \"\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 400): 2.0449147
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"[a-e]*\", anchor: \"$\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 20): 0.8606951
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"[a-e]*\", anchor: \"$\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 20): 0.6647422
StressTestDeepNestingOfConcat(engine: NonBacktracking, pattern: \"(a|A)\", anchor: \"\", input: \"aAaAa\", pattern_repetition: 2000, input_repetition: 400): 0.6331361
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"[a-d]?[a-e]?[a-f]?[a-g]?[a-h]?\", anchor: \"$\", input: \"abcda\", pattern_repetition: 400, input_repetition: 4): 0.6089077
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"[a-d]?[a-e]?[a-f]?[a-g]?[a-h]?\", anchor: \"$\", input: \"abcda\", pattern_repetition: 400, input_repetition: 4): 0.6065388
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"(a|A)\", anchor: \"\", input: \"aAaAa\", pattern_repetition: 2000, input_repetition: 400): 0.3276416
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"(a|A)\", anchor: \"\", input: \"aAaAa\", pattern_repetition: 2000, input_repetition: 400): 0.3066884
StressTestDeepNestingOfConcat(engine: Compiled, pattern: \"[a-z]\", anchor: \"\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 400): 0.1756175
StressTestDeepNestingOfConcat(engine: Interpreter, pattern: \"[a-z]\", anchor: \"\", input: \"abcde\", pattern_repetition: 2000, input_repetition: 400): 0.1623067

Author:	stephentoub
Assignees:	-
Labels:	area-System.Text.RegularExpressions
Milestone:	7.0.0

[stephentoub]

cc: @veanes, @olsaarik

[veanes]

I'm suspecting large overhead due to overlapping derivatives in unions (regexes) that are created due to ?. Looking at the alternative SymbolicNFA for computing derivatives to see a comparison as to how much these large unions (internally represented by dictionaries and hash-sets of SymbolicRegexNode) contribute would be a way to see if we can leverage SymbolicNFA, this is something I'll investigate with @olsaarik . At this point this is speculative.

[stephentoub]

@veanes, I just tried this test again, and it's gotten way worse than before. After minutes of it running, I attached a debugger, and I see the builder's node count in the hundreds of millions:

Can you please take a look? It seems like something has gone off the rails.

[veanes]

I'm investigating it. Been debugging and stepping through the code paths.
The problem is related to CreateDerivative of nested Concat with captures and OrderedOr with
simulateBacktracking=true, that causes the blowup. Some of this control-flow is new to me. To fully understand it I may need to discuss it with @olsaarik, I'll keep investigating for now to pinpoint the problem more exactly.

[stephentoub]

Thanks.

[veanes]

I was a bit stuck on this, but after a meeting yesterday with Olli, we figured out the cause.
The intermediate OrderedOr nodes are internalized as nodes in NFA mode (that must not happen) that causes the blowup and essentially defeats the purpose of the NFA mode.
I'm in the process of fixing this now.

[joperezr]

@veanes was this fixed by #68307?

[veanes]

working on it still, not fully fixed yet, but in the process

[joperezr]

Got it, that's fine I know that you are working on some related changes but I was just wondering if this particular one could be closed or not.

[veanes]

I think they would be closed, I am currently implementing and testing necessary simplification rules that keep the derivatives small, e.g. ones such as Y|XY --> X?Y
and more importantly a rule such as X{0,n}?Y | X^nXY --> X{0,n+1}?Y where X^n stands for n explicit repetitions of X (X and Y are arbitrary regexes here)
otherwise the blowup of alternations still cause a intermediate blowup (despite the earlier fixes) in the stress tests

[veanes]

The issue is now fixed, by #69530.