feat: improve performance for specific grammars with deeply nested closures and build CJS version

Codeneos commented 6 months ago

Both the antlr4ng and antlr4 implement a custom HashMap and Set that is compatible with their Java counterparts. Feature wise the implementations are correct but with certain grammars and specific source files that have deeply nested closures the Set class is stressed unproportionally.

This PR optimizes the methods of the Set and HashMap which yields a significantly performance improvement in parsing time. For me parsing of 2318 sources improved from ~165.365s to ~28.300s. This doesn't improve performance for all grammars.

This was tested using APEX, which is a c-style programming language for Salesforce CRM. The grammar file used was derived from Java which is what APEX is loosely based on.

Before

 [JavaScript]:
   ticks  total  nonlib   name
    304    3.2%   13.4%  JS: *<anonymous> C:\repos\antlr4ng\dist\antlr4.cjs:600:39
    223    2.4%    9.8%  JS: *addDFAEdge C:\repos\antlr4ng\dist\antlr4.cjs:7953:13
     84    0.9%    3.7%  JS: *closure_ C:\repos\antlr4ng\dist\antlr4.cjs:7683:11
     35    0.4%    1.5%  JS: *closureCheckingStopState C:\repos\antlr4ng\dist\antlr4.cjs:7620:27
     34    0.4%    1.5%  JS: *<anonymous> C:\repos\antlr4ng\dist\antlr4.cjs:602:21
     23    0.2%    1.0%  JS: *execATN C:\repos\antlr4ng\dist\antlr4.cjs:3609:10
     20    0.2%    0.9%  JS: *updateHashCode C:\repos\antlr4ng\dist\antlr4.cjs:879:19
     20    0.2%    0.9%  JS: *updateHashCode C:\repos\antlr4ng\dist\antlr4.cjs:274:17
     20    0.2%    0.9%  JS: *execATN C:\repos\antlr4ng\dist\antlr4.cjs:6954:10
     20    0.2%    0.9%  JS: *<anonymous> C:\repos\antlr4ng\dist\antlr4.cjs:6764:7
     17    0.2%    0.7%  JS: *hashATNConfig C:\repos\antlr4ng\dist\antlr4.cjs:2803:21
     16    0.2%    0.7%  JS: *update C:\repos\antlr4ng\dist\antlr4.cjs:313:9
     15    0.2%    0.7%  JS: *optimizeConfigs C:\repos\antlr4ng\dist\antlr4.cjs:2912:18
     12    0.1%    0.5%  JS: *updateHashCode C:\repos\antlr4ng\dist\antlr4.cjs:1025:17
     11    0.1%    0.5%  JS: *precedenceTransition C:\repos\antlr4ng\dist\antlr4.cjs:7814:23
     11    0.1%    0.5%  JS: *getConflictingAltSubsets C:\repos\antlr4ng\dist\antlr4.cjs:6762:34

After

 [JavaScript]:
   ticks  total  nonlib   name
     60    3.0%    7.3%  JS: *closure_ C:\repos\antlr4ng\dist\antlr4.cjs:7672:11
     24    1.2%    2.9%  JS: *execATN C:\repos\antlr4ng\dist\antlr4.cjs:3598:10
     21    1.1%    2.6%  JS: *updateHashCode C:\repos\antlr4ng\dist\antlr4.cjs:857:19
     21    1.1%    2.6%  JS: *hashATNConfig C:\repos\antlr4ng\dist\antlr4.cjs:2792:21
     21    1.1%    2.6%  JS: *execATN C:\repos\antlr4ng\dist\antlr4.cjs:6943:10
     19    1.0%    2.3%  JS: *updateHashCode C:\repos\antlr4ng\dist\antlr4.cjs:274:17
     19    1.0%    2.3%  JS: *getConflictingAltSubsets C:\repos\antlr4ng\dist\antlr4.cjs:6751:34
     18    0.9%    2.2%  JS: *closureCheckingStopState C:\repos\antlr4ng\dist\antlr4.cjs:7609:27
     17    0.9%    2.1%  JS: *add C:\repos\antlr4ng\dist\antlr4.cjs:2857:6
     15    0.8%    1.8%  JS: *updateHashCode C:\repos\antlr4ng\dist\antlr4.cjs:1003:17
     14    0.7%    1.7%  JS: *update C:\repos\antlr4ng\dist\antlr4.cjs:313:9
     13    0.7%    1.6%  JS: *<anonymous> C:\repos\antlr4ng\dist\antlr4.cjs:6753:7
     11    0.6%    1.3%  JS: *computeReachSet C:\repos\antlr4ng\dist\antlr4.cjs:7195:18
      9    0.5%    1.1%  JS: *sync C:\repos\antlr4ng\dist\antlr4.cjs:13424:7
      8    0.4%    1.0%  JS: *precedenceTransition C:\repos\antlr4ng\dist\antlr4.cjs:7803:23
      7    0.4%    0.9%  JS: *hasConflictingAltSet C:\repos\antlr4ng\dist\antlr4.cjs:6686:30
      7    0.4%    0.9%  JS: *getCachedContext C:\repos\antlr4ng\dist\antlr4.cjs:3133:19

Analysis

The 2 anonymous functions on line 600 (1) and 602 (2) are from the length function of the HashSet. Changing the length function to a more simpler function that doesn't use map or reduce significantly improves performance. As the length function alone counts for 15% of the execution time.

  get length() { 
    return Object.keys(this.data).map((key) => { // 600:39
      return this.data[key].length;
    }, this).reduce((accumulator, item) => { // 602:21
      return accumulator + item;
    }, 0);
  }

I suspect this is due to how Object.keys and map work in that both methods allocate new arrays which is a relatively costly operation.

Solution

As both the Set and HashMap in the antlr4 runtime only support add, contains and get operations making them collection types from which no elements can be removed thus optimizing them is relatively simple.

By stored the actual data of both collections in an array we can speed up accessing both the keys and the values of the collections. Next the length property can be determined by checking the length of the values array avoiding Object.keys and map.

The hash buckets instead of storing the actual value will store a reference to the index in the array. Arrays in JS are spares by design so you can add an element at index 100 without needing to set the previous 99 indices. Also you will not get an out of bounds error when accessing an index beyond the length of an array, you will simply get undefined. But as the Set and HashMap do not support removal of entries this doesn't matter that much :).

Other changes

Build CommonJS version - for my use case I want to integrate antlr4ng with a project that currently uses CommonJS. Changing this to ESM is difficult as some dependencies do not work properly any more.
CharStream as Interface - migrating from the standard antlr4 runtime I was implementing the CharStream, with antlr4ng I cannot implement the CharStream anymore due to it's #private property.

mike-lischke commented 6 months ago

Great, thanks @Codeneos! I'm a bit ambivalent to bring back CJS builds, but maybe it's better that way to ease usage with plain Node.js.

The implementation of these classes was on my mental todo list anyway (as is the entire optimization of the runtime). Just today I implemented a HashMap with MurmurHash as hasher for my ST4 port. I guess that could later be merge with this code here.

Codeneos commented 6 months ago

For me the problem with ESM only is that it doesn't work for everything yet. For example VSCode extensions need to be written in CJS format as ESM is not yet supported by VSCode. There are some workarounds converting ESM back to CJS but it isn't ideal. So if you would be okay with supporting CJS for the time being it would help me a lot!

I noticed optimizations are very specific, the HashMap and Set changes I did work great for my grammar and source code but when I run the benchmark it has no effect at all.

mike-lischke commented 6 months ago

I wonder why Git blocks merging, saying that all commits need to be signed. They are all signed....

mike-lischke commented 6 months ago

For me the problem with ESM only is that it doesn't work for everything yet. For example VSCode extensions need to be written in CJS format as ESM is not yet supported by VSCode.

When you bundle your extension (as you should) then you can generate a CJS bundle from any type of module (I do that with my extension already). But running with test frameworks needs a separate transformer, so a CJS bundle here simplifies things there.

Codeneos commented 6 months ago

For me the problem with ESM only is that it doesn't work for everything yet. For example VSCode extensions need to be written in CJS format as ESM is not yet supported by VSCode.

When you bundle your extension (as you should) then you can generate a CJS bundle from any type of module (I do that with my extension already). But running with test frameworks needs a separate transformer, so a CJS bundle here simplifies things there.

I am using webpack and esbuild but was getting some ERR about the ESM module not found when I ran quick test earlier today to see if I could move to ESM. Could be I missed something though somewhere.

mike-lischke commented 5 months ago

@Codeneos Unfortunately I had to revert your changes in HashSet and HashMap, because they broke the Java runtime tests. To my shame I have to admit that I did not run these tests for a while. Otherwise I would have seen that problem earlier. Only because I'm currently converting the Java runtime tests to TypeScript I saw this problem. If you want you can open a new PR with updated classes that also work well in the Java runtime tests.

Codeneos commented 5 months ago

Thanks for letting me know! I'll recreate the PR and fix the issue. Do you already have some pointers as to what is causing the Java tests to fail?

Oh and, for my knowledge how do I run the Java runtime tests? Are these part of the repo or do need something specific for that?

mike-lischke commented 5 months ago

Running the Java runtime tests is a pain. You need to build ANTLR4 locally and then symlink the JavaScript runtime folder in the ANTLR4 repo folder to the repo folder of antlr4ng.

The good news is however, that I managed to complete the TS port of the ANTLR4 runtime tests today. Clone this repo locally, run npm i in its root and then you should be able to run the tests using npm run test. Use npm link to replace the antlr4ng node package with a link that points to your local copy of antlr4ng and you should be able to run the tests with the current TS runtime.

It's all a bit rough yet and if you want to run a specific test you have to manually change the includedGroups and includedTests in RuntimeTests.runtimeTests(), but first run the tests as is and setup what I explained above. You can then replace HashSet and HashMap again with your version and run the tests again. You should then see which fail and use their groups and names to limit test runs to them.

Codeneos commented 5 months ago

Great that the tests already ported everything to TS!

I'll clone the repo and run the tests from there to pin point the issue.

mike-lischke commented 5 months ago

For your information I just reached a big milestone: All tests now use Jest and run in parallel, reducing total execution time to under 20s on my box. You can even debug individual tests, which should help you to better figure out why a test fails.

Codeneos commented 5 months ago

I've re-created the PR and made the changes I had intended to make from scratch again, this time I'm adding jest unit tests as I go to ensure that everything works as intended and keeps working as intended :)

mike-lischke / antlr4ng