Optimize symbolic regex Antimirov mode to avoid so much allocation

[stephentoub]

When in Antimirov mode, we logically maintain a list of states we're currently in and, for each step, generate a new list of states based on looking at each current state and determining all the states it could lead us to. However, rather than something like:

HashSet<Node> nextStates = _nextStates;
HashSet<Node> currentStates = _currentStates;
foreach (Node current in currentStates)
{
    foreach (Node next in Transition(current))
    {
        nextStates.Add(next);
    }
}
currentStates.Clear();
_nextStates = currentStates;
_currentStates = nextStates;

it's implemented using an immutable SymbolicRegexNode, where every additional state found involves unioning in the new state into the next states node, which means generating one or more new nodes for each additional state we union in.

[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

---

When in Antimirov mode, we logically maintain a list of states we're currently in and, for each step, generate a new list of states based on looking at each current state and determining all the states it could lead us to. However, rather than something like:

HashSet<Node> nextStates = _nextStates;
HashSet<Node> currentStates = _currentStates;
foreach (Node current in currentStates)
{
    foreach (Node next in Transition(current))
    {
        nextStates.Add(next);
    }
}
currentStates.Clear();
_nextStates = currentStates;
_currentStates = nextStates;

it's implemented using an immutable SymbolicRegexNode, where every additional state found involves unioning in the new state into the next states node, which means generating one or more new nodes for each additional state we union in.

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

[stephentoub]

@veanes, I believe you're working on this or a very related optimization, right?

[veanes]

Yes, started but got sidetracked a bit, will try to get this done soon (within a few days), essentially improving the overhead in the Antimirov mode, regarding state-set representation (using a more lightweight def, initially just HashSet<int>, Olli has then in mind a specialized very efficient "small integer set" data structure (similar to what is in use for NFA simulation ie Antimirov-like mode, in other tools like re2) to optimize further and can swap that out then.)

[veanes]

The PR #65637 should fix this issue, once this has been validated.