Performance Considerations

[jbartlau]

I'm currently evaluating the usage of csly to replace an existing language parser. I use the "Simple Expression Evaluator" sample as a reference and benchmark the evaluation of 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20 in order to have a first rough comparison.

The "old" library resides in C++ code, needs heavy P/Invoke and also works with VARIANT a lot. I was assuming that alone this overhead would cause a lot of performance drain. However using Benchmark.NET the results are surprising:

// * Summary *

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3593/23H2/2023Update/SunValley3)
11th Gen Intel Core i5-11500 2.70GHz, 1 CPU, 12 logical and 6 physical cores
.NET SDK 8.0.105
[Host] : .NET 8.0.5 (8.0.524.21615), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI

Job=MediumRun Toolchain=InProcessNoEmitToolchain IterationCount=15
LaunchCount=2 WarmupCount=10

Method	Mean	Error	StdDev
DoEvaluateWithSomeOtherLibrary	49.49 us	0.653 us	0.894 us
DoEvaluateWithCsly	691.33 us	21.806 us	31.963 us

// * Hints *
Outliers
Program.DoEvaluateWithSomeOtherLibrary: MediumRun -> 3 outliers were removed (52.59 us..52.79 us)
Program.DoEvaluateWithCsly: MediumRun -> 1 outlier was removed (817.96 us)

// * Legends *
Mean : Arithmetic mean of all measurements
Error : Half of 99.9% confidence interval
StdDev : Standard deviation of all measurements
1 us : 1 Microsecond (0.000001 sec)

// ***** BenchmarkRunner: End *****

Any thoughts how performance could be improved? Admittedly, the expression is not a real world example, however I'd need to add some 250 keywords to the language to have a real comparison, so this was my first shot for an easy benchmark.

[jbartlau]

Ah, for a fair comparison I'd need to remove the parser building from the benchmark code as this is probably done globally in the C++ DLL as well. However, parsing and evaluation are fair to compare. The full benchmark method looks line this:

[Benchmark]
public void DoEvaluateWithCsly()
{
    // Define the expression to parse
    var expr = "1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20";

    // Parse the expression
    var parser = BuildResult.Result.Parse(expr);
    var _ = parser.Result;
}

This still gives a - albeit much more favorable - difference:

// * Summary *

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3593/23H2/2023Update/SunValley3)
11th Gen Intel Core i5-11500 2.70GHz, 1 CPU, 12 logical and 6 physical cores
.NET SDK 8.0.105
[Host] : .NET 8.0.5 (8.0.524.21615), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMI

Job=MediumRun Toolchain=InProcessNoEmitToolchain IterationCount=15
LaunchCount=2 WarmupCount=10

Method	Mean	Error	StdDev
DoEvaluateWithSomeOtherLibrary	49.85 us	0.804 us	1.178 us
DoEvaluateWithCsly	79.07 us	2.154 us	3.224 us

// * Hints *
Outliers
Program.DoEvaluateWithSomeOtherLibrary: MediumRun -> 1 outlier was removed (55.06 us)
Program.DoEvaluateWithCsly: MediumRun -> 1 outlier was removed (88.02 us)

// * Legends *
Mean : Arithmetic mean of all measurements
Error : Half of 99.9% confidence interval
StdDev : Standard deviation of all measurements
1 us : 1 Microsecond (0.000001 sec)

// ***** BenchmarkRunner: End *****

[b3b00]

I've done some benchmark with existing opt-in optimizations and the broaden token window optimization gives some slightly better results :

Method	Memoize	Broaden	Mean	Error	StdDev	Median	Gen0	Gen1	Allocated
Simple Expression	False	False	313.7 μs	18.13 μs	52.30 μs	320.0 μs	82.0313	0.4883	336.3 KB
Simple Expression	False	True	259.0 μs	12.82 μs	37.59 μs	253.5 μs	81.0547	0.9766	332.55 KB
Simple Expression	True	False	426.6 μs	19.36 μs	56.48 μs	409.9 μs	104.4922	25.3906	430.18 KB
Simple Expression	True	True	456.8 μs	24.69 μs	70.43 μs	445.5 μs	104.4922	3.4180	427.68 KB

[jbartlau]

Thanks for your effort, will test ASAP

[jbartlau]

Strange enough, both optimizations draw on performance rather than yielding gains on my end:

With DoMemoize:

Method	Mean	Error	StdDev
DoEvaluateWithCsly	147.1 us	3.65 us	5.00 us

With BroadenTokenWindow:

Method	Mean	Error	StdDev
DoEvaluateWithCsly	87.41 us	3.946 us	5.784 us

To make sure the system is still comparable, retested without optimizations:

Method	Mean	Error	StdDev
DoEvaluateWithCsly	84.07 us	2.297 us	3.294 us

[b3b00]

Hello, indeed I've found that this optim can be bad for some kind of parsers (notably json parser, see #435 ).
My benches yesterday were surely not sufficient. Thanks for reporting. Expression parsing is already quite well optimized. I think that C++ is there outperforming in term of CPU (no need for JIT), and memory consumption (no GC). Maybe memory consumption could be oprimized if had time for this 😊.

Maybe this performance issue is not that important on real world situation ? For now I can not help further, I real busy at work 😒.

Thanks for trying CSLY, it gives me improvement things to investigate.

[b3b00]

If performance is a real concern for your use case I would recommend to go for ANTLR which is really performant (have tested it in my professional life).

[jbartlau]

Thanks for the frank reply. I also recognized quite many allocations, especially the generation of generic lists causes a lot of allocations. Maybe removing them wherever possible might help with performance, too (great session on the topic here). Will have to check if we change direction here or if performance is sufficient. Anyway, thanks for your help and keep up the great work here.

[b3b00]

Hello @jbartlau a other axis for improvment is to use C# source generators as suggested by #466. It could bring perf improvment in 2 ways :

• reduce the reflection API which is a known source of slowliness
• allow for AOT

I Will start to really think about it. It is quite challenging as I want to keep backward compatibility and so will require an important rewrite of the CSLY internal APIs.

[b3b00]

Hello @jbartlau ,

I have done some work on using Source Generators. It is already available as an alpha version. Take a look at this for more detail.
I still have to do some benchmark to see if there is any performance gain.