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

Why is it called _antimirovDelta and is there something more generic it could be called?

The naming _antimirovDelta, _antimirovStatearray, _antimirovStatearrayInverse as well as the boolen flag _antimirov reflect that these mirror the values of NFA in _antimirov mode (NFA mode) as opposed to the default DFA (_delta and _statearray) in Brzozowski mode. The names could also be _nfaDelta, _nfaStatearray, and _nfaStatearrayInverse, but the names reflect that the intent that the concerned algorithms use Antimirov-style derivatives (leading to NFA) vs Brzozowski-style derivatives (leading to DFA). We may end up renaming these names as some later point, not sure. In general the name delta is often used for a transition function of an automaton. So long story short, the name _antimirovDelta is really _nfaTransitionFunction.

The failing tests are unrelated to the changes in this pr (or so it looks to me).

The algorithm names and the distinction seems like the sort of thing that would live happily in a complex comment that explains the difference for users. The variable names being nfa or dfa would be both clear and more approachable than using the algorithm authors' names to me.

Point taken, we will probably end up doing a separate phase of renamings addressing the terminology issue in general, as a separate PR for this, e.g., renaming _antimirov to _nfaMode, etc., there are other similar cases in the code. We have been discussing this on and off for a while.

@veanes, I rebased your commits on main and fix up all the merge conflicts. I also added a commit that cleans up a few things, including avoiding the ToArray call in the NFA mode on every transition.

Before doing further work locally in your branch, you'll want to sync to these changes, which you can do with:

git fetch --all
git reset --hard origin/antimirov

If you've already done further work locally, don't do the above until you've made a backup of that work, e.g. by creating a new branch from it:

git checkout -b antimirovtemp
git commit -a -m "fix todos"

then doing the earlier commands, and then cherry-picking your last commit.

FYI, in its current state this ends up really regressing perf. I see a few obvious things I'll fix...

Thanks a lot for the rebase! I don't have any pending work other than a unit test case I was debugging the watchdog issue. I'll just stash this change and apply the first option above. I think perf could be addressed with SparseIntMap (@olsaarik know best how to apply it)

I think perf could be addressed with SparseIntMap

That's not the issue I'm fixing. Every time CurrentState is being created, it's creating new lists and sets... even when in DFA mode. I'll push a new commit here shortly.

I don't have any pending work

There are a variety of TODOs in the code, e.g. for OrderedOr. What's the plan for those? We're at a point where I'd like to avoid checking in lots of new open issues. If they're of the form "we could consider using XYZ to improve perf", that's fine, and we should have an issue tracking it. But if they're of the form "I'm not sure if this is functionally correct; we should investigate whether we need to be doing something different here", I'd like to address that as part of the change.

The plan for OrderedOr:
We get rid of Or and only have OrderedOr. The unordered Or case could be realized by ordering the elements in the OrderedOr collection by using hashcodes (if this would be needed, but I think not, since we want to now follow the exact (or best effort) same semantics for matches as in backtracking, in which case Or needs to be ordered always). In particular this would essentially get rid of SymbolicRegexSet used for _alts (conjunction case can be added back later as a form of And-collection using binary representation as in OrderedOr but not relevant now)

Regarding the continuous creation of CurrentState, this happens only when a shift happens from DFA to NFA mode, the intent was that this should not happen very often, but I may have been wrong here (which is why I did not think allowing null initializing them to null would make much difference)

I think perf could be addressed with SparseIntMap

That's not the issue I'm fixing. Every time CurrentState is being created, it's creating new lists and sets... even when in DFA mode. I'll push a new commit here shortly.

I pushed a commit to fix some of the perf regressions. In particular, the change was allocating multiple lists/sets every time a new CurrentSet was created, even when in DFA mode, which was causing allocations to skyrocket and having a very measurable impact on throughput.

Even with that, though, there are some substantial perf regressions. Here's what the "sherlock" perf tests:
https://github.com/dotnet/performance/blob/996fb443bf081a976a2f92a0fc14d5f1c212f6f7/src/benchmarks/micro/libraries/System.Text.RegularExpressions/Perf.Regex.Industry.cs#L127-L169
look like for me when I run them locally:

I don't think any of those are exercising the NFA mode (?), so this is a hit to the DFA perf.

Regarding the continuous creation of CurrentState, this happens only when a shift happens from DFA to NFA mode

It happens multiple times per match operation.

I am puzzled by this, as CurrentState is passed by reference in Delta and TakeTransition and should only be created once (unless NFA mode kicks in, at least this was the intent).
Ohhh, I see, the issue is that it should be reused when new initial (DfaMatchingState) is created, as opposed to be recreated in FindEndPosition, FindStartPosition etc. CurrentState should be passed into those methods as parameter. -- my bad.

Unless you are editing this right now I would suggest a fix this by passing the ref to CurrentState in FindEndPosition and FindStartPosition and FindFinalStatePosition and creating it in FindMatch once.

I'm fixing it right now.

Unless you are editing this right now I would suggest a fix this by passing the ref to CurrentState in FindEndPosition and FindStartPosition and FindFinalStatePosition and creating it in FindMatch once.

That will still create the lists/sets once per match operation. The fix I have here creates them once per runner, allowing those lists/sets to be reused across matches, which is something we'll want to maintain.

If we can go further and pass the current state by ref into those helpers instead of also passing in PerThreadState and creating a new CurrentState in each of those, great. But I'm not clear how that relates to the argument being passed in to CurrentState in each of those locations... it's already going to be in the right state?

I'm not currently editing this (and don't plan to this evening). Please feel free to pull it down and tweak it according to your recommendation.

Thanks.

CurrentState is really a ref for holding the actual state, when passing it in it initially it will passed say as the first argument to
FindFinalStatePosition,

s =new CurrentState<TSetType>(_dotstarredInitialStates[GetCharKind(input, i - 1)])
FindFinalStatePosition(s, ... old arguments)

Well, I'll fix this and push the fix later this evening.

Oh,, I forgot to pull your edits @stephentoub .. so now I'm getting just collisions, we were doing similar things in slightly different ways ... essentially perThreadData vs passing the ref to CurrentState (that is per thread obviously due to being created in the method call), not sure what the best option is here exactly, but I think using CurrentState as it was intended to (i.e., fixing my bug, just creating it once and passing it by ref is still the right thing to do). At the same time, I think that the Boolean _antimirov should be per thread data also, currently it is not.

I merged the conflicts, kept both edits, so passing the perThreadData, I think _antimirov should be a flag in perThreadData (currently it is not, it is in the builder).

I think _antimirov should be a flag in perThreadData (currently it is not, it is in the builder).

I don't understand how _antimirov is supposed to work. The code is flipping it back to false for phase 2/3; doesn't that mean the next match performed will start off creating new nodes as DFA even if it already exceeded the threshold?

Why do we need this flag at all? e.g. why not just decide when lazily creating a new transition whether it should be DFA or NFA, based on the current size of the graph (or based on whether we've initialized the NFA state lists/sets), rather than based on a persisted bool?

I've got the regression mostly addressed. But I'm trying to figure out now why the we're never ending up with antimirov set to true. I don't think it's from my changes, so maybe from something in Margus' initial changes here. I'll keep looking at it and push a new commit soon.

Here's my idea fleshed out in code: https://github.com/olsaarik/runtime/blob/antimirov-fix/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs#L797-L900 . One change that seemed necessary was to not pass in the ICurrentState as ref, since an assignment to that at the end would necessarily do the boxing (although only once per match, so might be fine).

What I have in my local changes is a CurrentState struct that's just a discriminated union of DfaMatchingState and an NfaMatchingState. We pass that around by ref, and we do the same static interface constraint we currently do in main, with DfaStateHandler and NfaStateHandler types implementing those interfaces, which operate over the ref CurrentState passed in.

I think I like the sound of your solution better. The recursive call into the same function with a different type that I had to do is a bit surprising.

Funny, I was thinking the same about yours. :-) I'll experiment with a hybrid.

By the way in my solution I think the check for antimirov should actually happen at the start of the outer loop rather than at the end to avoid new match calls temporarily being in DFA mode when they should be in NFA already.

Thanks for helping out with this this!
Looks like there is definite progress.
I'm busy today with a presentation I have to give tomorrow so had to switch context.

So here's a fun "alternative" approach: https://github.com/olsaarik/runtime/blob/0d51dc4174e0ef726ce6f75734af79719a5ef04f/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexMatcher.cs#L866-L878 DfaMatchingState.Next throws that NoMoreDfaException when it would create a new state over the antimirov bound and then the whole thing switches over to NFA mode. It only happens once per match call and due to the "zero cost" nature of exceptions shouldn't slow down DFA mode at all.

Not sure this is a serious proposal, but I love using exceptions for control flow :D

@olsaarik, @veanes, @joperezr, I pushed a new set of changes. Please take a look. From the commit description:

Overhaul SymbolicRegexMatcher to avoid DFA perf regressions from NFA changes
This does a few things:

• The previous changes for Antimirov changed the representation from being represented as a DfaMatchingState to instead being a list of states. Unfortunately, this came at the expense of a significant increase in overhead for the DFA mode. This commit melds the old and new design, by still using a CurrentState struct that can be either a DFA state or an NFA state, but with a simplified representation that lacks any processing. The processing is left to two separate structs that implement static abstract interface methods, as was previously done, using that to provide streamlined, generic-specialized processing for the DFA path.
• Overhauled how we switch from DFA mode to NFA mode. Previously, the builder would store whether we were in NFA mode, and any matching after it had been switched over immediately started in NFA mode. We now always start in DFA, and only switch over to NFA if we try to create a new state but doing so would exceed the graph size constraint.
• Overhauled how we handle the outer/inner loop logic. Previously we wanted to remain in a tight inner loop and so would use some "leeway" to allow us to go beyond the graph size constraint in order to avoid having to check too frequently whether we'd exceeded that size. Now, the transition function itself returns whether we need to exit out to the outer loop in order to upgrade from DFA to NFA, and until/unless that happens, we can stay in the inner loop.
• Avoids inlining huge amounts of NFA code that can result in worse DFA code
• Renamed Brzozowski and Antimirov to DFA and NFA.
• Added a lot of comments to SymbolicRegexMatcher
• Fixes "watchdog" issue with captures
• A few other renames / cleanups.

I still see some variance in the perf tests, but nothing like before. Most of the tests are now +/- 10% from where they were before. A few tests get better by upwards of 20% while a few get worse by a similar margin. There's also still room for microoptimization on the fast path, but I'd like to look at that separately.

I wanted to add that I went through all the new changes involving use of IStateHandler. It looks really clean to me and I'm happy to see the use of SparseIntMap. Definitely looks very solid and clear, I'm really happy this is converging. I do not have very strong viewpoint on the special case of one state. But I know one thing for sure. Having single state in NFA transitions is very common (e.g. the current test cases are like that, I debugged and checked), most if not all nondeterminism is because of the set not because of the NFA state also possibly being nondeterministic. So special casing could make sense if there is even a small gain.

I was actually thinking of the List of states in the NFA transition function ... Still having a single state in the set itself may also occur, as the state becomes "deteriministic" temporarily, and could continue to be so for while, this obviously depends on a combination of circumstances triggered by a particular input that makes the behavior deterministic for that particular case (e.g. returning to the "initial" state that just loops around in it, if the initial state is special cased and not split into a set --- an optimization we discussed with @olsaarik )

Concretely, one optimization would be in NfaStateHandler:
public static bool IsInitialState(ref CurrentState state) =>

            if  state.NfaState!.NfaStateSet.Count == 1 then 
            builder.GetCoreState(nfaState.NfaState!.NfaStateSet[0].IsInitialState)
            else false

This would allow the top-level loop to know that we are still in initial state and take advantage of the related optimizations used in DFA mode (initial prefix search etc)

Obviously, this calls for a proper NFA mode set of benchmarks we currently don't have.

Concretely, one optimization would be in NfaStateHandler

Thanks. Let's look at that subsequently. I didn't apply it for now as that would also require changing the main loop that assumes NFA states are never initial and thus only looks to see whether the current state is a DFA initial state.

Sounds good, just wanted to point this out, to keep this in mind.