Add benchmarks

[lppedd]

I'd like to setup a couple of benchmarks using kotlinx-benchmark.
The benchmarks should measure something we can compare with other ANTLR implementations, e.g., antlr4ng.

@mike-lischke hey! Would you be ok for us to reproduce the same benchmarks for antlr-kotlin?

[mike-lischke]

Absolutely! It's all open source 😄

[lppedd]

Thank you!

To recap, it seems you:

1. read a sample file
2. split it based on a delimiter (but it's not a real split, you seem to use only the range to substring from the original file)
3. for each range, create a new parser instance, so the single time measurement is for that single range
   Edit: nope, looks like the measurement is for the entire file

Is that correct?

[mike-lischke]

Top down it's rather so:

1. The splitter test -> not relevant for you as it is only to measure how long it takes to determine statement ranges in a file. This hasn't to do with parsing and is just an additional number I wanted.
2. Run the parser test once (cold run) -> collect the execution times and print them.
3. Runt the parser 5 more times (warm run) -> collect the execution times.
4. Remove the 2 slowest runs from step 3.
5. Compute the average of the remaining 3 and print them.

A parser run consists of n loops, determined by the testFiles list. For each file:

1. Determine statement ranges (not taken into the overall time needed).
2. Go over each range and check if it matches a certain version number. I copied the tests from my VS Code unit tests where this matters. You could settle on a single version and remove all entries that don't it from the statements file. If the version matches, take a copy of the string part and parse that using a "parsing service", which is created on app start and kept in a separate class. So the parser is reused (otherwise you couldn't measure warm run times).
3. Print any error found during parse.
4. Compute the needed time and push it to the result list. So the length of the list correlates to the number of test files.

[lppedd]

Thanks!

I've managed to emulate the same workflow in Kotlin, and now I find myself dealing with a stack overflow on the JVM with this statement:

SELECT
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
1
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

java.lang.StackOverflowError
	at com.strumenta.antlrkotlin.benchmarks.generated.MySQLParser.simpleExpr(MySQLParser.kt:45124)
	at com.strumenta.antlrkotlin.benchmarks.generated.MySQLParser.bitExpr(MySQLParser.kt:44062)
	at com.strumenta.antlrkotlin.benchmarks.generated.MySQLParser.predicate(MySQLParser.kt:43685)
	at com.strumenta.antlrkotlin.benchmarks.generated.MySQLParser.boolPri(MySQLParser.kt:43457)
	at com.strumenta.antlrkotlin.benchmarks.generated.MySQLParser.expr(MySQLParser.kt:43137)
	at com.strumenta.antlrkotlin.benchmarks.generated.MySQLParser.exprList(MySQLParser.kt:50557)
	at com.strumenta.antlrkotlin.benchmarks.generated.MySQLParser.simpleExpr(MySQLParser.kt:45278)

Removing it completes the run successfully tho.

[mike-lischke]

Yes, that's a tough one. When parsing this in a thread in C++ it crash that thread unless you are on a platform that allows to set the thread stack size. This is a big problem in ANTLR as crashing a thread usually crashes the entire app (nice DDOS attack)!

The problem is the unlimited lookahead and the way prediction is implemented (as recursion instead of iteration). And additionally, expressions in MySQL (and many other languages) are highly nested so one opening par alone can result in a dozen or more sub rule invocations. That's why I love this one as a stress test.

Can you increase the stack size during execution?

[mike-lischke]

btw. please share numbers once you got it all running! And while you are on it, can you also run it against plain Java? I'm really interested in comparing everything.

[KvanTTT]

This is a big problem in ANTLR as crashing a thread usually crashes the entire app (nice DDOS attack)!

Some runtimes have methods that could check if there is enough free space in thread stack for one more recursive call. For example, EnsureSufficientExecutionStack in C#. In theory, such check can be integrated into targets that support such feature. For other runtimes, it's possible to use manual recursive call counter and calculate its limit empirically (maximum number of recursive calls).

Another way is to emulate recursive calls using separated stack. But it requires much more implementation effort.

Can you increase the stack size during execution?

Yes, it should be possible, but it's not a reliable resolving of the problem. SO exception should not occur in any case.

[mike-lischke]

The root cause should be removed instead of all these workarounds. In my next generation ANTLR project I plan to convert the recursive prediction code to become iterative and add an iteration limit. This has been requested before, to limit lookahead to some max value.

[lppedd]

Preliminary benchmark results on a i7-7820HQ - 32GB
The JS results are taken with measureTime, as kotlinx-benchmark for JS is blocked by Kotlin/kotlinx-benchmark#185

File	JS	WASM	JVM	mingwX64	ANTLR4NG
statements.txt	523.2868 ms	226.27428 ms	102.962 ms	1481.9423 ms	668.6744333306 ms
bitrix_queries_cut.sql	282.2195 ms	123.57261 ms	56.586 ms	742.65691 ms	388.6220333178 ms
sakila-data.sql	21531.5333 ms	8683.92242 ms	3652.251 ms	58584.12632 ms	28444.441866676 ms

[lppedd]

I think on K/JS the major performance issue is the use of a string for the generated ATN, which must then be converted to a char array, and decoded to an int array. The JS and TS runtimes use an array of integers directly.

@KvanTTT not sure if we can do something to differentiate based on the platform.

[ftomassetti]

The root cause should be removed instead of all these workarounds. In my next generation ANTLR project I plan to convert the recursive prediction code to become iterative and add an iteration limit. This has been requested before, to limit lookahead to some max value.

@mike-lischke About your NG project, do you think that some ideas could be contributed to the just started effort on ANTLR 5?
I am just asking out of curiosity as both your project and ANTLR 5 seem to aim to build the next generation of ANTLR and there is surely ground to cross-pollinate ideas

[KvanTTT]

The root cause should be removed instead of all these workarounds. In my next generation ANTLR project I plan to convert the recursive prediction code to become iterative and add an iteration limit.

Yes, it's a good solution, I also said about that.

I think on K/JS the major performance issue is the use of a string for the generated ATN, which must then be converted to a char array, and decoded to an int array.

I'm not sure it's a hot path since this String is being deserialized only once on app startup. But anyway I think using array of Int instead of String is a better option (it requires some effort on JVM side because it crashes on big arrays, but it's possible to split one huge int array to several more smaller ones).

@mike-lischke About your NG project, do you think that some ideas could be contributed to the just started effort on ANTLR 5?
I am just asking out of curiosity as both your project and ANTLR 5 seem to aim to build the next generation of ANTLR and there is surely ground to cross-pollinate ideas

It's a great idea but I'll email you about the current situation (not sure it's public info).

[lppedd]

@KvanTTT Terence once wrote

Java does not properly handle static initialized integer arrays

So what he meant was that the JVM simply crashes?

There is a big difference between 150/200ms of antlr4ng and 300/600ms of K/JS, so I wonder what's so heavy on our side.

[KvanTTT]

So what he meant was that the JVM simply crashes?

True, unfortunately JVM can't handle huge arrays unlike other runtimes out of box. But it's probably possible to use direct memory or splitting into several smaller arrays. Actually, this array is only required only once during ATN deserialising and there is no need to keep it in memory.

There is a big difference between 150/200ms of antlr4ng and 300/600ms of K/JS, so I wonder what's so heavy on our side.

What's about other parsing stages? Probably they consume much more time.

[mike-lischke]

Preliminary benchmark results on a i7-7820HQ - 32GB The JS results are taken with measureTime, as kotlinx-benchmark for JS is blocked by Kotlin/kotlinx-benchmark#185

File JS JVM
bitrix_queries_cut.sql 300ms 58ms
statements.txt 600ms 107ms

The different machines might have an impact here. Have you tried running the pure JS benchmarks? My box is a Mac Studio M1 Max - 32 GB.