[wasm] Compiled regexes in interpreter ~25-50x regression

[kg]

At some point recently, performance for BDN's compiled regex tests under the interpreter on wasm regressed by around 25-50x. See https://pvscmdupload.blob.core.windows.net/reports/allTestHistory/refs/heads/main_x64_ubuntu%2022.04_CompilationMode=wasm_RunKind=micro/System.Text.RegularExpressions.Tests.Perf_Regex_Common.MatchWord(Options%3a%20IgnoreCase%2c%20Compiled).html for one example.

I tested this in isolation and was able to reproduce bad performance, but I couldn't identify the cause, and the code involved is very complex so I couldn't make sense of what was going on. I didn't notice any misbehavior on the jiterpreter side of things for this scenario.

See dotnet/perf-autofiling-issues#29881 for diff range.

[dotnet-policy-service]

Tagging subscribers to this area: @BrzVlad, @kotlarmilos
See info in area-owners.md if you want to be subscribed.

[dotnet-policy-service]

Tagging subscribers to 'arch-wasm': @lewing
See info in area-owners.md if you want to be subscribed.

[stephentoub]

Maybe #98791 ? It would suggest that the interpreter doesn't currently play nicely with SearchValues<string>, e.g. using IndexOfAny to search a ReadOnlySpan<char> with private static readonly SearchValues<string> s_words = SearchValues.Create(["tempus", "magna", "semper"], StringComparison.OrdinalIgnoreCase);.

[kg]

Maybe #98791 ? It would suggest that the interpreter doesn't currently play nicely with SearchValues<string>, e.g. using IndexOfAny to search a ReadOnlySpan<char> with private static readonly SearchValues<string> s_words = SearchValues.Create(["tempus", "magna", "semper"], StringComparison.OrdinalIgnoreCase);.

It's possible, I wouldn't expect that to cause this big of a regression but iirc this regression set also included some SearchValues-related regressions.

[lewing]

you can still see the regression https://pvscmdupload.z22.web.core.windows.net/reports/allTestHistory/refs/heads/main_x64_ubuntu%2022.04_AOT=true_CompilationMode=wasm_RunKind=micro/System.Text.RegularExpressions.Tests.Perf_Regex_Common.MatchWord(Options:%20IgnoreCase,%20Compiled).html and the range is 9da5359...79dd9ba

[lewing]

cc @vitek-karas

[BrzVlad]

This performance issue is not related to mono interpreter, it is indeed caused by the Regex change linked above: commit.

@stephentoub The issue is related to support for RuntimeFeature.IsDynamicCodeCompiled/Supported. The commit above heavily degrades performance when the runtime doesn't use compiled dynamic code, impacting mono interpreter. Consider the following microbenchmark https://gist.github.com/BrzVlad/a2345bac59cf0ee472e27b7365a2379f. Running this testcase locally with CoreCLR, before your change it runs in 1.3s and after your change it runs in 0.75s. This looks great, however, if I forcefully disable the dynamic code support switches in CoreCLR in file, before your change it runs in 1.8 and after your change it heavily degrades to 71s, which is consistent to the regressions we are seeing on mono interpreter.

[stephentoub]

This performance issue is not related to mono interpreter, it is indeed caused by the Regex change linked above:

Per my comment in #99553 (comment), you don't see SearchValues<string> performing poorly in such cases?

[BrzVlad]

I think I benchmarked that API some time ago and I didn't notice perf problems. Anyhow, as I mentioned above, the same regression would still happen on CoreCLR if dynamic code is disabled, so this should rule out potential problems with missing interpreter optimizations. The hottest methods detected by interpreter in this benchmark are the following, starting with the hottest:

27% System.Text.RegularExpressions.RegexInterpreter:TryMatchAtCurrentPosition (System.ReadOnlySpan`1<char>)
40% System.Text.RegularExpressions.RegexInterpreter:SetOperator (System.Text.RegularExpressions.RegexOpcode)
52% System.Text.RegularExpressions.RegexInterpreter:Backtrack ()
58% System.Text.RegularExpressions.RegexCharClass:CharInClass (char,string,uint[]&)
64% System.Text.RegularExpressions.RegexInterpreter:Advance (int)
68% System.Text.RegularExpressions.RegexInterpreter:Operand (int)
72% System.Text.RegularExpressions.RegexRunner:EnsureStorage ()
75% System.Text.RegularExpressions.RegexInterpreter:Scan (System.ReadOnlySpan`1<char>)
78% System.Text.RegularExpressions.RegexInterpreter:Forwardcharnext (System.ReadOnlySpan`1<char>)
81% System.Text.RegularExpressions.RegexInterpreter:TrackPush (int)
84% System.Text.RegularExpressions.RegexInterpreter:Goto (int)
86% System.Text.RegularExpressions.RegexRunner:CheckTimeout ()
88% System.Text.RegularExpressions.RegexInterpreter:Forwardchars ()
90% System.Text.RegularExpressions.RegexFindOptimizations:TryFindNextStartingPositionLeftToRight (System.ReadOnlySpan`1<char>,int&,int)
92% System.Text.RegularExpressions.RegexInterpreter:TrackPeek ()
93% System.Text.RegularExpressions.RegexInterpreter:TrackPush ()
94% System.Text.RegularExpressions.RegexInterpreter:TrackPop ()

[stephentoub]

Thanks, @BrzVlad. I still need to validate this, but I expect the problem then is that optimizations which used to kick in for such situations now aren't.

This particular test has this regex pattern: "tempus|magna|semper". Previously, that would have resulted in the regex looking for the next match by doing an IndexOfAny for e.g. the third character of each, so IndexOfAny('m', 'g'). Now with the SearchValues<string> support, it's going to instead prefer to do a search for the actual words rather than just one character of each. That happens here:

runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexFindOptimizations.cs

Lines 145 to 150 in 16506b7

	if (!interpreter) // this works in the interpreter, but we avoid it due to additional cost during construction
	{
	if (RegexPrefixAnalyzer.FindPrefixes(root, ignoreCase: true) is { Length: > 1 } caseInsensitivePrefixes)
	{
	LeadingPrefixes = caseInsensitivePrefixes;
	FindMode = FindNextStartingPositionMode.LeadingStrings_OrdinalIgnoreCase_LeftToRight;

After choosing to do that, it's then actually creating the SearchValues:

runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexFindOptimizations.cs

Lines 152 to 155 in 16506b7

	if (usesRfoTryFind)
	{
	LeadingStrings = SearchValues.Create(LeadingPrefixes, StringComparison.OrdinalIgnoreCase);
	}

But, it's only doing so if it thinks it's going to need it, and it would only need it for non-compiled, because this instance would be created elsewhere for compiled. That logic isn't taking into account the possibility, however, that something which claims to be compiled isn't actually compiled. If dynamic code isn't compiled, then later on when it goes to actually do the compilation, it'll instead fall back to using the interpreter, which means we will have selected to use this multi-string search, but we won't actually have the SearchValues<string> instance to do it. When the interpreter then goes to find the next location to consider doing a match, it'll try to do the multi-string search, find it unexpectedly doesn't have the SearchValues, and bail:

runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexFindOptimizations.cs

Lines 699 to 707 in 16506b7

	case FindNextStartingPositionMode.LeadingStrings_LeftToRight:
	case FindNextStartingPositionMode.LeadingStrings_OrdinalIgnoreCase_LeftToRight:
	{
	if (LeadingStrings is not SearchValues<string> searchValues)
	{
	// This should be exceedingly rare and only happen if a Compiled regex selected this
	// option but then failed to compile (e.g. due to too deep stacks) and fell back to the interpreter.
	return true;
	}

which means it'll end up trying the full match at every position. So whereas previously in this situation it would have been doing the full match only at places where IndexOfAny('m', 'g') matched, now it's doing it everywhere.

Assuming I'm right, the fix is likely to just always do:

runtime/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/RegexFindOptimizations.cs

Line 154 in 16506b7

LeadingStrings = SearchValues.Create(LeadingPrefixes, StringComparison.OrdinalIgnoreCase);

rather than guarding it with an if, and accept the small extra overhead in the compiled case where it'll be throwaway. (We could pass around more state to avoid that, but it's probably not worth the churn.)

[lewing]

Calling this closed, we can track improvements in net10 separately