The ANTLR4 benchmarks repository is ready

[mike-lischke]

I finally managed to realize an idea I had for a long time: creating a repository for comparing performance numbers of different ANTLR4 runtimes, for different grammars (only a selection of course). Currently only the MySQL grammar is used, but I hope to add more.

@kaby76, @KvanTTT, @parrt, @jimidle, @ericvergnaud, @ftomassetti, @lppedd, @bkiers, I would like to invite you to work with me on this repository. What is it you could do?

• Add benchmarks for other targets to existing benchmark groups (e.g. Go, C# and Java for the MySQL grammar)
• Add a new benchmark group for a grammar of your choice, for the target you are familiar with. Others will hopefully help to add more targets.
• Verify and discuss results and maybe even possible improvements.
• Suggest/discuss grammars that are worth to be included here.

What's in for you guys?

• The efforts towards ANTLR 5 will receive an opportunity to compare how good the new implementation is compared to ANTLR 4. At some point we may even add benchmarks for different tool versions.
• Target specific code can be developed here and later taken over to the grammar repository. The benchmark repo is a perfect development bed to figure out the minimal code needed to make a grammar run on a specific target.
• This is also a place where grammars can be improved, where needed.
• Code in this repo can serve as example/demonstration of how to use a grammar with a specific target.
• For target developers it is good to compare their runtime with others, to see where they stand.

Hopefully I can convince some of you to be part of this effort!

Thanks, Mike

[bkiers]

Hey @mike-lischke, no problem. Great initiative 👌

My languages of choice are Java and C#. I'll have a look at your current benchmarks this weekend and will add them for Java and C# (if someone doesn't beat me to the punch).

[mike-lischke]

Great! Just ask if you need something clarified.

[bkiers]

Just looking into the Java benchmark, and I notice there's quite some code w.r.t. processing SQL files (splitting them into separate SQL statements). Right now you have all that code in a separate .ts file (the function determineStatementRanges) that is shared among the code base. However this means that much code will need to be ported to other languages (Java, C#, Python, etc). Would it not be better to preprocess these .sql files and separate them in single SQL statement-files beforehand so that not every language would need to create their version of determineStatementRanges?

In other words, instead of data/sakila-db/sakila-data.sql with delimiters, you'd have:

data/sakila-db/sakila-data/statement001.sql
data/sakila-db/sakila-data/statement002.sql
...
data/sakila-db/sakila-data/statement???.sql

without delimiters. Every statement???.sql will contain just 1 single SQL statement.

Also, information is retrieved from rdbms-info.json. If that JSON is to be parsed in Java, you'd need a 3rd party library. If the objective is to run these benchmarks without too much hassle, I think it'd be better to create a flat text file containing the character sets from rdbms-info.json without the need to first parse it. Otherwise you'll need to include the JAR of the JSON library in this repository (because you don't want a full build system that resolves these dependencies).

[mike-lischke]

I took this code from unit test code I have written for other projects, hence they are as they are. But of course that doesn't mean to keep them forever like that. Separating out individual statement files might be an option, but that would mean we have about 1000 files for the benchmarks. Unfortunately, we cannot just make each statement a single line, as line breaks are valid identifier chars, when quoted. Let me think a bit about that...

For the charsets: they don't need to be in a JSON file. The names can just be hard code like here. I'll change the TS implementation to avoid the need of a JSON file.

[mike-lischke]

What if you just read the statement file and split it at what are the delimiters now ($$)? I think they do not appear in any of the queries. If they do I can change the statement files to use something more unique.

[mike-lischke]

@bkiers I pushed some changes, so that the JSON file is no longer necessary (charsets are hard coded now) and the statement files have unique delimiters ("$$$"), so you can just load the file and split it using this separator to get the individual statements.

I guess I should also simplify the target code even more (it's already stripped down a lot, but may contain code not relevant for benchmarking).

[kaby76]

I will need to think about this, but performance is an interest of mine.

I just added a PR for the grammars-v4 repo for a workflow to test performance changes in a PR for a grammar. (antlr/grammars-v4#4023) One problem of a FOSS repo of Antlr4 grammars is making sure any change to a grammar doesn't screw it up any more than it is. The new workflow tests the "before" and "after" versions of a grammar change, running the examples for the grammar up to 40 times ("grouped", approximately equal to a "warmed up" parser) to gather information about how the grammar performs. The test uses Octave to perform a Welch 2-sample test to see if there is a "statistical significant" difference, and a drop in the ratio of the mean performance by a few percent for a "practical significant" difference. Of course, if the test input files for a grammar don't exercise all parts of the grammar, then it's likely the workflow won't find anything. And, for many grammars, the test input don't test even 25% of the entire grammar. (antlr/grammars-v4#3511)

[mike-lischke]

Not sure the benchmark repo can help with performance regressions. But maybe you can help to improve the benchmarks? I don't know if it makes sense to do more than just parse some input and measure the time taken, but we can find that out.

Why do you run the tests like 40 times? Does this give more precise results than running only, say, 10 times?

[kaby76]

I had a hunch that there was a problem with some PRs to sql/plsql in the last month. So I started writing a script to test PRs and plot out the mean runtime vs PR in a bar char. I initially picked a sample of 10 off the top of my head (antlr/grammars-v4#4014 (comment)), sort of a compromise because the parse of the 100+ files took a minute or two. But, I noticed that 10 runs wasn't enough to "show" a difference in the bar chart visually. I then bumped that to 40 times, and the bar chart looked much better. It showed a clear drop in performance with one particular PR (antlr/grammars-v4#4014 (comment)).

Now, it turns out that that wasn't really necessary. With Student's t-test or Welch test, it's possible to show a "statistically significant" degradation in performance without the bar chart "showing" the diff visually. 40 times may not be necessary.

The main issue is how long people are willing to wait to see a result. I figured 20 minutes would be acceptable. So, assuming "before" and "after" run times for a parse, 10 minutes for each "before" and "after" PR would be possible. Therefore, the number of repetitions is computed: min(40, 600 seconds / time-to-run-parse-of-examples/*). Whether this works or not, I don't know for sure. It's just a stab in the dark, just something to try to get bad PRs from coming into play.

[mike-lischke]

Ah, I see. Of course, the more runs you have, to bigger is the difference. On the other hand, how significant is a drop in performance if you need many loops to shown an impact?

Anyway, this is (at least currently) not in the focus of this project, where I first want to create benchmarks to compare ANTLR4 runtimes. Which grammar is used for that is relatively unimportant, but of course the "heavier" a grammar is, the better you see the performance differences. Heavier means here: the length of possible sentences (for recursions), predicates and actions count.

[kaby76]

On the other hand, how significant is a drop in performance if you need many loops to shown an impact?

"Show" is a relative term. For a bar chart, one can "see" visually a difference better as more samples are done. But, people aren't going to like workflow that take hours. Stats have be applied. A statistical test can "show" significance even though it doesn't look so clear cut in a bar chart.

For comparing runtimes, we should test both "good" and "bad" grammars (ones with a lot of ambiguities and fall backs). For some runtimes, I have seen an "individual" parse work faster than a "grouped" parse. This seems counterintuitive because all that caching in the interpreter is supposed to speed things up.

[ericvergnaud]

Interesting. Am I correct in observing that testing grammar performance is different from testing runtime performance ? And that the latter may trigger different results from one grammar to another ?Would it make sense to provide simple means to check for grammar coverage and for runtime coverage ?Envoyé de mon iPhoneLe 28 mars 2024 à 20:44, Ken Domino ***@***.***> a écrit : I will need to think about this, but performance is an interest of mine. I just added a PR for the grammars-v4 repo for a workflow to test performance changes in a PR for a grammar. (antlr/grammars-v4#4023) One problem of a FOSS repo of Antlr4 grammars is making sure any change to a grammar doesn't screw it up any more than it is. The new workflow tests the "before" and "after" versions of a grammar change, running the examples for the grammar up to 40 times ("grouped", approximately equal to a "warmed up" parser) to gather information about how the grammar performs. The test uses Octave to perform a Welch 2-sample test to see if there is a "statistical significant" difference, and a drop in the ratio of the mean performance by a few percent for a "practical significant" difference. Of course, if the test input files for a grammar don't exercise all parts of the grammar, then it's likely the workflow won't find anything. And, for many grammars, the test input don't test even 25% of the entire grammar. (antlr/grammars-v4#3511) —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you were mentioned.Message ID: ***@***.***>

[mike-lischke]

Hmm, interesting thought. The focus in this repo is currently on runtime performance, but right, this could be extended to grammar performance tests, to figure out whether grammar changes have good or bad impact on the performance.

[kaby76]

Am I correct in observing that testing grammar performance is different from testing runtime performance ?

Correct. There is a difference in grammar performance vs runtime performance.

Testing the changes in a grammar of a PR should help to clarify whether the PR introduces "badness" (e.g., ambiguity). I'm hoping the workflow will help, but I don't know until I see it in action for the next month or so.

And that the latter may trigger different results from one grammar to another ?

Correct. I have seen some really weird caching issues that exist in some runtimes but not others.

Would it make sense to provide simple means to check for grammar coverage and for runtime coverage ?

I have a tool that displays the coverage of the parse of a collection of input. It outputs an html file with the grammar colorized according to rule usage in all the parses by checking the types of nodes in all of the parse trees outputted.

However, it doesn't colorize the grammar that AdaptivePredict() goes through to arrive at an alt decision. The Intellij plugin colorizes the input for ambiguities, but I want to turn that on head and show how that appears in the grammar, for what rules are hit. I think there are different ways to view a problem across input, grammar, and runtime.

[KvanTTT]

Interesting! I'll try it when I complete my own ANTLR runtime (more or less).

[mike-lischke]

In fact, I have started to adopt your benchmarks that you wrote years ago. The first one is https://github.com/mike-lischke/antlr4-runtime-benchmarks/tree/main/src/ConstantFolding, which I implemented for TypeScript and C++. I might try your Python version, but I'm not really a Python developer.

I would love it if you could help add the other benchmarks as well, but please make sure they are as easy to build and run as possible. A simple download (like for Node.js, Python, clang, javac, etc.) should be enough to get everything built and running. No fancy build system (like Maven or Cmake) should be necessary, as this increases the barriers to trying out the benchmarks and even adding your own later.

[KvanTTT]

I might try your Python version, but I'm not really a Python developer.

Python is not complex language, especially compare to C++ 🙂

No fancy build system (like Maven or Cmake) should be necessary

Why not Gradle? Maven is outdated build system and it doesn't support important features (especially regarding Kotlin). Gradle is standard de facto.

[mike-lischke]

I would like to make it as simple as possible. For small projects like a benchmark you only need a few source files and a compiler to create a binary from that. Input comes from a file or is hardcoded, output is done to the terminal/console, which all languages we consider here have built-in.

Having to set up a full build system raises the barrier significantly for people who just wanna try things out here. Ideally, the entire setup should consists of only 2 downloads (beside the repo): a compiler (where needed) and the ANTLR tool to generate files.

[mike-lischke]

Given this premise, I'm thinking of removing the antlr4wasm benchmark, because setting up emscripten is a pretty complicated job. At least I don't plan to add another wasm benchmark to any new grammar benchmark set.

[kaby76]

I'd recommend that you set up a standardized Docker or virtual machine for Ubuntu so we don't need to try to figure out the environment. For scripts, use Bash.

[kaby76]

Question about the MySQL grammar. You have the grammar in this repo, in multiple places. It is not in target-agnostic format, nor in StringTemplate format, which is why there are many copies here for Cpp, here for Antlr TypeScript 4.13.1, here for Antlr4ng, here for Antlr4ts. Presumable, you'd have to make ports for any other targets like Java, CSharp, Go, Python3, JavaScript, and Dart. (Note, I am ignoring PHP because it is so full of serious hash code errors to be useless, and I cannot convince the author that the code is all wrong.)

Why is the grammar not in target-agnostic or a StringTemplate format?

Can I please add this grammar to grammars-v4/sql/mysql/Oracle/mysql-version-such-and-such and make it target-agnostic format? I have a huge ecosystem to analyze this grammar, but I cannot do that if not in one or the other format. (It has to be in target-agnostic format for grammars-g4 because everyone expects the .g4 to be used as is, not preprocessed via StringTemplates as Trash can handle.)

[mike-lischke]

The grammar contains lots of target specific code (predicates, actions, token emit etc.) I wonder how you want to make that target agnostic. Don't forget you have to add also the imports for the specific base classes.

I'm not happy with that, but currently I see no other way than having a copy of the grammar with adjustments for each target. I'm open for better solutions, but would like to avoid another 3rd party library/tool.

For publishing the grammar in the grammar repo let's discuss this separately.

[kaby76]

Target agnostic is possible for any grammar, but it either requires hacks like transformGrammar.py to fix the grammar for the target, or a StringTemplate solution. The main issue is placing the semantic predicate code in a base class rather than use @members, but that's not hard compared to the effort to implement the target-specific code in @members.

[mike-lischke]

I don't use the @members named action. I already have all target specific code in base classes, but still, you have to import these classes and the calls to methods are different (depending on the target). Additionally, member names of the parser/lexer classes differ sometimes (e.g. _type vs. type).

[kaby76]

I don't use the @members

Sorry, you are right. I just noticed that you already have the code in base classes.

but still, you have to import these classes and the calls to methods are different (depending on the target)

Yes, that is true, but that's exactly what "transformGrammar is all about. Yes, it is a totally disgusting hack, but it allows for the grammar to be shared for all targets.

Rather than have all these different syntax, the grammar always uses "this." in all actions, and transformGrammmar.py replaces the pattern with the appropriate syntax. To be really "target agnostic", you shouldn't even use operators like <, %, etc. I forgot, but there is one target for one grammar in grammars-v4 that had this issue.

For Cpp, the semantic action https://github.com/mike-lischke/antlr4-runtime-benchmarks/blob/a971852628d9ecca0ce79c7972e3c026017bdadc/src/mysql/targets/antlr4-cpp/MySQLLexer.g4#L474C90-L474C111 does not have a "this->", but is it required because the field is already declared in the base class. In most grammars, the "transformGrammar.py" hack is required to mutate "this." to "this->".

For JavaScript and TypeScript, "this." must be used https://github.com/mike-lischke/antlr4-runtime-benchmarks/blob/a971852628d9ecca0ce79c7972e3c026017bdadc/src/mysql/targets/antlr4/MySQLLexer.g4#L486C90-L486C116 . But, since we already require "this." for all field and method references for "target agnostic format", it's fine as is.

For Go, lexer predicates must be reference with "l." which parser predicates are "p.".

Etc., etc., etc.

A much better solution would be to provide a StringTemplate expansion for the target. A PR was added for this here: antlr/antlr4#4345 , but personally, I'd make the entire file a string template, and prefix or suffix the file with .st, and just apply ST through the whole file. Trash already does this. (You have to have a tool like trgen because Java requires base class code to be in a specific directory structure if you use a -package option for the Antlr tool.

[mike-lischke]

Hmm, to be honest, I don't consider StringTemplate a better solution. This is worse than pure JavaScript, from a usage standpoint. Because of the embedded native code you cannot do error checks, you don't know what the parameters are, which are passed to a template and what the type of them is, nor do you know what templates you have to implement actually in your group file.

On the other hand I know we (the group) have discussed this a long time already, how to make grammars target agnostic. With the current situation I see no good solution, seriously. For the grammar repo we only can strip down target code to the absolute minimum.

In a future iteration of ANTLR we can change that and think of a better solution. I have nothing against a language extension for ANTLR to make the action code abstract, but really, I don't want ST to be that extension. Instead I imagine actions like we have for lexer rules, which are translated to listener calls and the listener has to implement the actual code (or mock it for the grammar repo). This would require the introduction of more commands (like emitToken etc.), though I have to admit, I haven't fully thought through everything. I also think for a realistic implementation the possible commands should be limited, not like the current approach: everything is possible.

It's probably also not the right place here to discuss this. If you have too many moving targets, nothing gets really done. So, first let's get a couple benchmarks done and then do the next step, even if that means to do duplicate work...

[mike-lischke]

To be really "target agnostic", you shouldn't even use operators like <, %, etc. I forgot, but there is one target for one grammar in grammars-v4 that had this issue.

That could be replaced by a method (action) call. If we provide a "library" of possible APIs that can be used in action code, it should be easy for all runtime authors to add that to every generated listener (which would then be mandatory if a user wants to use such action code).

[kaby76]

You should read the PR antlr/antlr4#4345 and how it's used with the old Python3 grammar and 8 targets. https://github.com/kaby76/stg-python3.git .

The newline action has an applied occurrence of the template onNewLine. There's only one .g4 copy, and it works for all targets.

https://github.com/kaby76/stg-python3/blob/d74cb899fe539272e80159a2e07d5f24c5f9ca64/Python3Lexer.g4#L118C5-L118C18

The defining occurrence of the template is a target-specific template with no parameters, and you can use whatever target code as necessary in the template itself. By convention, I put these in different directories named after the target, with different .stg files for each grammar. But, the PR is pretty flexible for other ways of organizing the templates.

CSharp: https://github.com/kaby76/stg-python3/blob/d74cb899fe539272e80159a2e07d5f24c5f9ca64/CSharp/Python3Lexer.stg#L131-L168

Cpp: https://github.com/kaby76/stg-python3/blob/d74cb899fe539272e80159a2e07d5f24c5f9ca64/Cpp/Python3Lexer.stg#L99-L127

Java: https://github.com/kaby76/stg-python3/blob/d74cb899fe539272e80159a2e07d5f24c5f9ca64/Java/Python3Lexer.stg#L116-L151

The "plus" is that we only have one copy of the .g4's.

The PR limits templates to Antlr actions. I would prefer to widen that to anything in a grammar except string literals and comments. I only suggested a .st or .stg suffix because I already have a solution implemented with Trash. But, it does template expansion on the entire file--including string literals. Trash also needs to parameterize bits in the driver code, which the "action template PR" does not address. There's no input file for ST attributes, which is a real drag with ST--it's all native Java or CSharp data structures. The PR doesn't address the issue of packaging, which people want to parameterize.

It's probably also not the right place here to discuss this.

Agreed.

[mike-lischke]

I have now stripped out any code which is not needed for the benchmarks. Statement splitting for SQL benchmarks is done by splitting the file content at a known delimiter (here $$$), so the effort to port that to other languages should be minimal.

[KvanTTT]

I recommend using /*! and !*/ as markers instead of $$$. Comments don't break code correctness unlike $$$.

[mike-lischke]

You cannot use valid syntax elements as separators! Even $$ didn't work, because one file used that in a string. Keep in mind there's no scanner/tokenizer used anymore, so we cannot say if a char sequence is in a string or comment (like we could with the statement splitter).

[KvanTTT]

You cannot use valid syntax elements as separators!

Why not? Comments don't affect parsing, semantics.

Keep in mind there's no scanner/tokenizer used anymore, so we cannot say if a char sequence is in a string or comment

I understand that, but in most cases it's a comment and an extra char(s) make them practically unique, especially if an emoji symbol is used, for instance: /*❗, ❗*/. I use such an approach for diagnostics in my yantlr fork for convenient testing. They can be matched using regex instead of full tokenizer:

lexer grammar test;
x : 'a';
/*❗RuleRedefinition x 2:1*/x/*❗*/ : 'b';

Also, we use a similar approach for Kotlin compiler tests.

[mike-lischke]

We are talking about different things, it seems. My comment was about splitting test input, which is in a separate text file, a collection of MySQL statements, which use a unique delimiter to separate them. It's not about embedding data or similar in a test case.

[mike-lischke]

@bkiers, @kaby76 Have you had a chance to work on another target language for the MySQL benchmarks? It doesn't need to be that grammar, however. Pick any other you think it's worth to be included. I can then add a TypeScript and C++ variant.

@KvanTTT Have you thought about adding some of your other benchmarks to this repo? Would be fun to see how Python and PHP do in these benchmarks.

[KvanTTT]

Have you thought about adding some of your other benchmarks to this repo?

I haven't. Currently I'm busy with my official work and my yantlr fork. Unfortunately, I don't have enough time and resources.

[kaby76]

Have you had a chance to work on another target language for the MySQL benchmarks?

Neither have I. I am trying to deal with grammars-v4 issues, which led to finding regressions in Trash.

[mike-lischke]

Right, all a matter of priorities, no worries.

[bkiers]

Have you had a chance to work on another target language for the MySQL benchmarks?

I started a couple of weeks back and then stumbled upon the code that tokenizes the SQL input, which you have refactored. I'll merge your changes back into my branch and see if I can wrap that up. Not sure when exactly since I'll be on a trip at the end of the week. I'll let you know.

[jimidle]

Somewhat related, here is my original ANTLRV3 grammar for TSQL 2008R2 converted to v4. Feel free to test it, or put it into the benchmarks. It was max LL(3) in v3, but I have not analyzed t exactly in v4. But it is very efficient and suffers from none of the issue in the other grammars published in contributions (MIke's grammar excepted). https://github.com/jimidle/tsqlparser jimidle/tsqlparser: An implementation of an ANTLR4 TSQL grammar at the 2008R2 spec github.com

…

On May 4, 2024, at 13:47, Mike Lischke ***@***.***> wrote: Closed #1 <#1> as resolved. — Reply to this email directly, view it on GitHub <#1>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMGBXLMKWGVEPNUSSSTZAU3NBAVCNFSM6AAAAABFNCPNAOVHI2DSMVQWIX3LMV45UABFIRUXGY3VONZWS33OIV3GK3TUHI5E433UNFTGSY3BORUW63R3GEZDKOBWGI2Q>. You are receiving this because you were mentioned.

[mike-lischke]

Hey Jim, thanks for the suggestion. Seems to be a good candidate for another benchmark group.