Add prefixes to regex terminals

[jahav]

I am working on a replacement of a handcrafted parser for library ClosedXml (a library to manipulate xlsx files) with the XLParser. Because xlsx can have hundreds of thousands of formulas, I would like to improve performance of XLParser.

I would like to add prefixes to the RegexBasedTerminals.

Irony uses a first character prefixes to build a table of a char->possible terminals (terminals without prefix are always considered). This table is then used to speedup a calculation of current terminal.

I would also like to change grammar to be case sensitive (small, but measurable improvement) and terminals already use both cases, where necessary (e.g. a-zA-Z).

I have tried to change regex options of the terminals (through reflection) - RegexOptions.ExplicitCapture (as recommended in best practices), RegexOptions.Compiled, RegexOptions.CultureInvariant . but there wasn't significant improvements.

I have run a benchmark on EnronFormulasParseTest (test was modified to be single threaded). Parser version with prefixes runs 44% faster.

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.856/21H2)
AMD Ryzen 5 5500U with Radeon Graphics, 1 CPU, 12 logical and 6 physical cores
.NET SDK=6.0.302
  [Host]     : .NET 6.0.7 (6.0.722.32202), X64 RyuJIT AVX2
  Job-JFUIAS : .NET 6.0.7 (6.0.722.32202), X64 RyuJIT AVX2

IterationCount=3  LaunchCount=1  WarmupCount=1

With prefixes

Method	Mean	Error	StdDev
EnronDataSet	26.496 s	3.6721 s	0.2013 s
EusesFormulasParseTest	2.852 s	0.0582 s	0.0032 s

Without prefixes

Method	Mean	Error	StdDev
EnronDataSet	47.295 s	2.5500 s	0.1398 s
EusesFormulasParseTest	4.738 s	0.3636 s	0.0199 s

[kenleese]

@jahav This might also be of interest https://devblogs.microsoft.com/dotnet/performance_improvements_in_net_7/#regex

[jahav]

@kenleese Thanks, I knew about improvements in NET5, but not about further developments.

We need to stay compatible with netstandard 2.0 (net framework support will stay for a long time), but I will check out the regex source generators (netstandard2.0 should be sufficient). Because it is a compile time generated, it could improve be used for all code.

[jahav]

I checked out the source generator and the generated code is not compatible with netfx (it uses some new API, mostly methods with Span signatures and some others). Unfortunately, my idea to reuse them for netstandard2.0 project is not feasible.

XLParser spent only 60% of the time in regex matching (at least that is what my saved dotTrace snapshot tells me, not sure which version is it from), so even if I optimization speed up the regex matching by 50%, overall parsing will be only 30% faster. Great, but not orders of magnitude better.

The prefixes are a simple and uncomplicated way to improve performance. netcore will improve regex on its own and netfx is a dead man walking (that I will support for a long time, but I don't really care about performance of netfx too much).

EDIT:
I checked out which terminals are most expensive (made a bunch of TermXY classes and replaced each RegexBasedTerminal with a different one) and ExcelFunction terminal might be worth optimizing a little (there is a lot of backtracking), it is simple enough.

    internal class Term5 : RegexBasedTerminal
    {
        public Term5(string name, string pattern, params string[] prefixes) : base(name, pattern, prefixes) { }
        public override Token TryMatch(ParsingContext context, ISourceStream source) => base.TryMatch(context, source);
    }