ANTLR4 WebAssembly target

[mike-lischke]

Hi all,

Today I announced the development start of a new ANTLR4 target: antlr4wasm, a WebAssembly port of the C++ runtime, in the ANTLR4 announcement list (Google group):

This is to let you know that I started the development of a WebAssembly runtime for ANTLR4 - an idea that is floating around since years already. I just published the first batch of files (https://github.com/mike-lischke/antlr4wasm) for early testing.

Early testing here means: parsing does not work, not even lexing input, but ground has been laid to have a foundation to work with and many of the initial (and sometimes difficult) problems have been solved (or at least understood enough, to know limitations or to provide workarounds). Typescript type definitions exist for many of the runtime classes and some of them can already be used standalone (like the vocabulary).

If there's any interest for this new runtime, especially to help with getting it to work, I'd happily provide more details.

Main motivation for this new target is to get high performance parsing in modern web applications, with nearly native C++ speed.

Eric already replied and suggested to move this to an own discussion:

this is great news. I was considering doing the same, and have language targets all use the same WebAsm runtime, for a future version of antlr.

So, here we go, exchanging ideas what could be done with this new project, coordinating help and so on to make this reality as fast as we can.

[ericvergnaud]

Hi Mike,

since WebAssembly is not per se a 'language', it'd be great to clarify what integration patterns you have in mind ?

[mike-lischke]

Well, the textual form can be considered to be an own language, but we don't work with that directly, right? It's always the binary form (*.wasm) and currently I only follow the path to use that in a JS/TS environment. The generated wrapper JS file makes that easy and provides a lot of tooling that helps to work with the wasm binary.

I have not thought yet about other use cases, just want to finish one for now :-) But if would be possible to use the assembly in other languages then this would be a tremendous simplification of the target landscape we have now in ANTLR4. A quick search showed me that there's python-wasmer to run webassembly in Python. Imagine we would only need to write the wrappers and have to maintain just one core runtime (C++, beside Java as reference implementation)! That would be awesome.

[ericvergnaud]

Yes there are WebAsm wrappers for JS, Python, C++, Java, C#...

Some time ago I started exploring a gradual migration of the JS runtime, using AssemblyScript to generate the WebAsm byte code, but that proved to be counter-performant i.e. the cost of serializing/deserializing was monstrous.

Then I looked at using AssemblyScript as a full-fledged target and that was pretty disappointing too, since AssemblyScript looks like TS, relies on TS tools, but you only find at compile time that many required constructs are not supported... In my experience it's close to unusable for a big project.

IIRC, the major hurdle I bumped into at the time was the lack of inheritance.

WebASM is evolving slowly, and some RFCs aim to fill fundamental gaps:

• native string support
• struct support
• gc

I suspect this will take a couple of years, hence my thinking that it would be more reasonable to target a unified antlr runtime for a future antlr.

But although I didn't at all explore C++, I believe the above gaps are filled by the available C++ wrapper. So maybe starting with C++ would be a more rapidly achievable small win, and provide a good basis for other targets. The general idea would be to convert the generated lexer and parser to wasm using existing tools.

[mike-lischke]

AssemblyScript was my first approach, but it misses too many important core aspects, so I gave up on that. For wasm the situation is completely different, because it's not the language which uses the code that is converted, but the library being used. I tested first with simple things like adding an interval to an interval set 10 million times and found that this is slower using wasm, compared to native JS. Which shows it is very important not to cross boundaries for hot paths. But that's a perfect scenario for parsing input. We only pass in text and get back a parse tree + diagnostics. So I expect that to be much faster.

What's also critical for adoption is the tooling in the consuming language. The generated JS wrapper has a lot of handling already built-in, like accessing the underlying wasm memory directly, conversion of primitive types (like strings), checks for wrong parameters, duplicate type names and many more. I wouldn't want to write that by hand.

GC is a different matter, since C++ doesn't have that. But by using smart pointers that can be mitigated. This is something I still have to check once there's a first working version.

Inheritance on the other hand is pretty well supported. With some glue code I can extend a C++ class in JS/TS (as we need that for for generated lexer + parser). Not sure how this is handled in other user land languages (like python). To see if a unified ANTLR4 runtime is feasible will require some investigation into the individual consuming languages and their wasm support.

But to make it clear(er): I don't want to compile the generated files to wasm! All I want is to have a wasm based runtime, which is then consumed by the generate files. They are not time critical, but having to compile them to wasm would require much more extra work and additional build tools. My vision is to just publish the wasm + target language wrapper and continue using the current approach of generating the parser/lexer files.

[ericvergnaud]

Looks like we started from the same simple stuff (interval sets) and reached the same conclusion...
Since the generated parser/lexer keeps calling the runtime, I fear the performance might be disappointing, hence my thinking of also converting the generated files. Then indeed you provide a string and get a parse tree in return, on which you can run a visitor or listener.
But let's see if your intermediate approach is beneficial already.

[mike-lischke]

I got lexing working. See here: mike-lischke/antlr4wasm#3

[mike-lischke]

The first version of the wasm runtime works now and I collected a few performance numbers.

Runtime	Query Collection Cold	Query Collection Warm	ratio	Large (Binary) Inserts Cold	Large (Binary) Inserts Warm	ratio
C++	3.96s	0.437s	1.0	13.2s	12.2s	1.0
WebAssembly	6.17s	1.77s	4.05	56.5s	60s	4.93
antlr4ts	12.3s	0.84s	1.9	44.85s	43.6s	3.57
JavaScript	72.5s	5.2s	11.9	248.9s	250.2s	20.5

Looks pretty good for input that doesn't use left recursion much. However, the memory household is currently mostly uncontrolled. Need to find a way to manage it.

[ericvergnaud]

Goff stuff!
Just being curious, is this using the dev branch JS runtime ? It fixes a webpack issue that hit performance strongly

[mike-lischke]

I used the NPM version, so might not have got the latest fixes. I can certainly test with the latest code if that has improvements!

[mike-lischke]

@KvanTTT Would you be interested in changing your benchmarks to use a really heavy grammar (MySQL) and do the same execution like I did for the results above? I guess that would be a pretty good performance overview for all available targets. Though I guess we have to leave out PHP then. It will probably take days to finish.

[ericvergnaud]

It does, please check it out.Envoyé de mon iPhoneLe 26 août 2023 à 15:35, Mike Lischke ***@***.***> a écrit : I used the NPM version, so might not have got the latest fixes. I can certainly test with the latest code if that has improvements! —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>

[mike-lischke]

I just tried the latest JS target in the ANTLR4 dev repository and I'm speechless. What by all means did you change there? With that version it became the fastest runtime I have ever seen, even faster than C++ and the optimized TS target (and I have enabled parse trees for verification). The parse trees look good, but I cannot imagine what led to this extreme improvement. Here are the numbers:

Query Collection (cold): 10.2s
Query Collection (warm): 0.25s

Large Inserts (cold): 11.8s
Large Inserts (warm): 11.7s

The optimized TS version needs 45s and 44s for the large inserts file, respectively. The wasm version is even slower.

Can you explain in more detail what you did? The used memory tips at 2.6GB on my box, so it really looks like that is no fake.

[mike-lischke]

I checked the git history for the source files for the JS runtime and found no significant changes since the last release 3 months ago, so how can the code in the repo be so much faster compared to the NPM module? That makes no sense.

[ericvergnaud]

What changed is that we’re no longer letting webpack convert for es5. I couldn’t believe it myself when a guy mentioned the numbers …Envoyé de mon iPhoneLe 27 août 2023 à 12:44, Mike Lischke ***@***.***> a écrit : I checked the git history for the source files for the JS runtime and found no significant changes since the last release 3 months ago, so how can the code in the repo be so much faster compared to the NPM module? That makes no sense. —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>

[mike-lischke]

OK, targeting only ES6 can explain a certain speed increase, but not this huge amount. How can the JS suddenly be faster than antlr4ts (which is an optimized target) and C++ (which by nature is a very fast target)? How can a script language be faster than a compiled language? That simply makes no sense.

[mike-lischke]

Meanwhile I read the pull request for this improvement and see you were as much surprised as I am now :-) So, let's accept the fact that JS is pretty fast. I'll arrange the same MySQL tests with the C++ runtime and the latest grammar, to see if that's faster than the older one (with which I tested so far). I'll come back with the results later.

Ah, btw: you should publish a new node package asap. People will love it, for sure!

[mike-lischke]

@ericvergnaud I started to consolidate the benchmarks in my antlr4wasm branch and installed the latest antlr4 JS/TS target from NPM, However this is terribly slow again. Have you already released that change which fixes the ES5 issue mentioned above? I'm using the ESM import for the benchmark.

[ericvergnaud]

I learned 20 years ago that runtime based languages force us to think differently about optimization because you need to factor in the speed of the runtime itself. In this case it seems that an ES6 class is much much faster than a prototype based ES5 compatible class. It makes sense because a manually built ‘vtable’ might not be as easy to optimize by the v8 engine than an ES6 one which is deemed immutable (appreciate JS let’s you change things manually but I wouldn’t be surprised if doing so broke the performance).Envoyé de mon iPhoneLe 27 août 2023 à 12:44, Mike Lischke ***@***.***> a écrit : I checked the git history for the source files for the JS runtime and found no significant changes since the last release 3 months ago, so how can the code in the repo be so much faster compared to the NPM module? That makes no sense. —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: ***@***.***>

[jimidle]

Don’t use the MySQL grammar in the contributed grammars. In my opinion we should remove it as it is essentially unusable. It will stress the system though, I’ll say that ;)

…

On Sat, Aug 26, 2023 at 20:26 Mike Lischke ***@***.***> wrote: @KvanTTT <https://github.com/KvanTTT> Would you be interested in changing your benchmarks <https://github.com/KvanTTT/AntlrBenchmarks> to use a really heavy grammar (MySQL) and do the same execution like I did for the results above? I guess that would be a pretty good performance overview for all available targets. Though I guess we have to leave out PHP then. It will probably take days to finish. — Reply to this email directly, view it on GitHub <#4362 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMA5NSRANU3ZBQDUETLXXHTQBANCNFSM6AAAAAA2PY4ERA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[mike-lischke]

Jim, which of the grammars do you mean? I'm the maintainer of the one from Oracle. Unfortunately, I'm legally not allowed to publish the grammar itself in the grammar repository (which is why there's only a readme with links), but there are at least 2 open source implementations on Github with it (which I both maintain as well), that work very well.

And because of the language complexity this is a perfect grammar for benchmarks. Testing a parser with a mini grammar like this one has only a very limited usefulness.

For real benchmarking and stress tests a large grammar is the better option. It doesn't need to be MySQL. It's just the grammar I know best.

[kaby76]

The sql/mysql/Positive-Technologies is bad, that is true. For example, on examples/bitrix_queries_cut.sql, the CSharp code runs in ~45s, Java ~14s, and JavaScript ~700s. (I'm not sure why it's not tested for Java, as that is faster than CSharp, which is tested. The list of viable targets was computed many months ago via script, which may have had a bug in it.)

For examples/bitrix_queries_cut.sql, the parse with perf information contains a large number of ambiguities. perf.txt.

But, since it is the only version in the repo for mysql, we shouldn't remove it until we have something better than the status quo.

[mike-lischke]

fyi, with the Oracle MySQL grammar I get these numbers with a warm C++ runtime:

    Found 935 statements in statements.txt.
    Parsing all statements took: 101 ms
    Found 57 statements in sakila-db/sakila-data.sql.
    Parsing all statements took: 3603 ms
    Found 529 statements in bitrix_queries_cut.sql.
    Parsing all statements took: 54 ms

and that grammar is for multiple MySQL versions (min. is 8.0.0) and 100% complete.

[mike-lischke]

In this case it seems that an ES6 class is much much faster than a prototype based ES5 compatible class.

Do you wanna say that ES6 does not use prototypes? I wonder, because that's not true.

It makes sense because a manually built ‘vtable’ might not be as easy to optimize by the v8 engine than an ES6 one which is deemed immutable (appreciate JS let’s you change things manually but I wouldn’t be surprised if doing so broke the performance).

Sorry, but I don't buy that. Regardless how much V8 or any other JS interpreter can optimize the JS code, it will always be slower than natively compiled code. I'm still baffled.

[ericvergnaud]

What I mean is that the following code:

class A extends O {
    constructor() { super(); }
    m1() {}
}

is not the same code as:

function A() { O.call(this); return this; }
A.prototype = Object.create(O.prototype);
A.prototype.constructor = A
A.prototype.m1 = function() {}

The latter is what webpack/babel generates from the former for supporting ES5.
Although ES6 supports both, I suspect V8 is able to optimize the former much better than the latter.

Re compiled code vs "interpreted" code, just like the JVM and the CLR, V8 has a JIT compiler(named Crankshaft), so when running a benchmark, the JS code is only interpreted for the first few iterations. On a large number of iterations I don't expect the difference would be measurable. The compilation itself is done in a separate thread so it comes at no cost on a modern processor.

Also, GC has (probably unplanned) side effects that notably maintain frequently used data in the processor L1 cache. This avoids cache misses that are costly in terms of actual execution. See http://igoro.com/archive/gallery-of-processor-cache-effects/ for in-depth analysis of the cost of cache misses. If you've done some OpenMP stuff, you'll know how much this stuff matters when optimizing loops. I learned this the hard way when benchmarking SQLServer Mobile in 2006. 2 MS experts came along, both implementing the same application code, one in C#, the other one in C++. Implementing the benchmark took 1 hour for the C# guy, 1 day for the C++ guy, only to find that the C++ version was slower! It took the C++ guy another day to equal the performance of C#. In the following weeks, we then spent some time digging into the topic, and with the help of some MS gurus to which they had access we got the above explanation.

Another topic for performance analysis is pipelining, which lets the processor execute consecutive instructions in parallel if they rely on distinct processor submodules (and drops unused results to restore logic). I haven't digged into that as much as in the processor cache stuff.

The assumption that "less instructions" run faster than "more instructions" is a reasonable but sometimes incorrect assumption because it lies on the false assumption that the execution time of an instruction is deterministic, when it may actually vary a lot depending on the execution context (such as L1/L2 cache content).

A good JIT will take advantage of the actual processor architecture, which is not something a static compiler can do (I recall building and distributing multiple versions of the same C++ code to benefit from vector instructions in the late 90s).

[mike-lischke]

I see, thanks for the explanation!

[mike-lischke]

I created an own command line test app just for C++ and now the results look much more sane:

Runtime	Query Collection Cold	Query Collection Warm	ratio	Large (Binary) Inserts Cold	Large (Binary) Inserts Warm	ratio
C++	1.04s	0.099s	1.0	3.62s	3.6s	1.0
WebAssembly	6.17s	1.77s	17.9	56.5s	60s	16.7
antlr4ts	12.3s	0.84s	8.5	44.85s	43.6s	12.1
JavaScript	10.3s	0.25s	2.5	10.7s	10.2s	2.83

while the current wasm code is super slow. I guess I need to move more of the generated TS code to C++, to avoid frequent border crossing.

[ericvergnaud]

Yes I believe you want to cross the border only once forth to provide the input and only once back to return a serialized parse tree (that doesn't work for sempreds but I'd suggest tackling the simple use case to start with).
This strategy requires converting the generated lexer and parser to WASM automatically, which is not trivial...

[mike-lischke]

Not only would that require to generate wasm versions, but it would require to have the full emscripten build env on your box. I want to avoid that at all costs. I'd rather give up on wasm than forcing devs to use that.

btw. someone else went exactly this way: https://github.com/dbryan17/wasm-antlr

What I have in mind is to generate a different form of the parser and lexer files, passing the states for the individual rule methods as an array to C++ and only callback for sempreds and actions. Something along this line...

[mike-lischke]

After optimizing the generated parser to avoid some of the wasm border crossing, I got a pretty good speed increase (speed doubled). Still not as close to the C++ target as I hoped for and I'm not sure I can do much more, other than moving generated code to C++ (with the consequences mentioned already). There's simply too much back and forth between JS/TS and C++. The current target seems to be free of mem leaks (at least neither ASAN nor the SAFE_HEAP option do report anything). Here are the latest numbers:

Runtime	Query Collection Cold	Query Collection Warm	ratio	Large (Binary) Inserts Cold	Large (Binary) Inserts Warm	ratio
C++	1.04s	0.140s	1.0	5.13s	5.14s	1.0
JavaScript	10.5s	0.25s	1.78	12.93s	12.9s	2.5
WebAssembly	3.2s	0.95s	6.78	27.6s	28.5s	5.5
antlr4ts	12.3s	0.84s	6	44.85s	43.6s	8.5

While antlr4wasm is now on par with antlr4ts (or even faster for the heavy recursive input), I'm not sure if I should follow that path for now. Instead it seems more promising to me to use the JS target instead, even though it still feels odd to me that JS is so close to C++, which is another reason why I would like to have benchmarks for all current ANTLR4 runtimes (@KvanTTT) and they should be part of the tests. This would also help to avoid regressions like the one we had for the JS runtime.

Also, @parrt is understandably very reluctant to add yet another ANTLR4 runtime, so this sounds like the better option overall (but I may follow the wasm road in a different way in the future, though).

But as I mentioned before, there's quite some stuff missing in the JS target and particularly the type definitions miss many things. I can create the full typings for JS, but I'd really prefer to use the same folder and file structure like the Java runtime (flattened, like in the C++ runtime), except for JS specific stuff. Maybe in a second step we can convert the JS files to TS, later? For the node package this makes no difference, webpack will transpile the sources. What do you think @ericvergnaud about this plan? Any objections to change the structure?

[ericvergnaud]

@mike-lischke
I absolutely welcome contributions for adding missing classes such as ParserInterpreter.

Re the structure , the reason I changed it is because the Java one is not good enough for me. As an example, I don't understand why Exception classes are at the top level, aside utility classes such as ProxyErrorListener, or even worse RuleContextWithAltNum... Imho, the top-level should only directly contain classes necessary for implementing basic parsing. And the ATN folder also contains way too many classes. So how about aligning all runtimes on the JS runtime structure (not saying there isn't room for improvement in it) ?

Re d.ts files, I suspect we have somewhat different philosophies: I only want to expose what people need, such that I limit backwards compatibility issues, whereas it seems you want to expose everything. Not sure we can find common grounds here...

As per the js -> ts conversion, given your benchmark results, I'd suggest thinking about it 7 times at least... In theory, antlr4ts should be faster thanks to an optimized algorithm, but in practice it's actually slower. It's very possible that this slowness comes from the ts -> js conversion.

[mike-lischke]

Re the structure , the reason I changed it is because the Java one is not good enough for me. As an example, I don't understand why Exception classes are at the top level, aside utility classes such as ProxyErrorListener, or even worse RuleContextWithAltNum...

I understand your concerns and know you would have created a different structure had you created this project, but we inherit the structure from the main language and should mostly follow it. One big advantage is that it becomes much easier to compare two targets to see what exists already and what needs to be added/changed.

Imho, the top-level should only directly contain classes necessary for implementing basic parsing. And the ATN folder also contains way too many classes. So how about aligning all runtimes on the JS runtime structure (not saying there isn't room for improvement in it) ?

Our personal preferences are certainly different and as you probably already assumed, I'm not so happy with the JS structure. There's no universal best fit for everyone here, that's why I recommend to stay with what we got from Java, unless there are very compelling reasons not to do so. From a user standpoint it doesn't matter how the structure is, after all what gets imported is the top level index file (which hides all the internal details).

Re d.ts files, I suspect we have somewhat different philosophies: I only want to expose what people need, such that I limit backwards compatibility issues, whereas it seems you want to expose everything. Not sure we can find common grounds here...

Yes, correct. You never know what people come up with and how they use the library. I, for example, need a number of less commonly used classes for my grammar debugger, ATN visualization and other IDE support. There's basically no class in ANTLR I have not used in one or the other way.

As per the js -> ts conversion, given your benchmark results, I'd suggest thinking about it 7 times at least... In theory, antlr4ts should be faster thanks to an optimized algorithm, but in practice it's actually slower. It's very possible that this slowness comes from the ts -> js conversion.

Right, this needs to be checked carefully. That's why I suggested to do that as a second step. After all the resulting code is JavaScript, so maybe it's a similar problem like you had with Babel that made the target slower. As I suggested before, we should have a benchmarking tool to see regressions in performance of a target.

[ericvergnaud]

On the long term (ANTLR5?), I believe that a WASM-only runtime would make sense. The tool would generate:

• a lexer and parser in a WASM-able language (Rust?), ultimately compiled to WASM
• wrappers for these WASM lexer and parser, for each target
• wrappers for context classes, for use by Listener and Visitor implementations
  With that approach, every target would have the same behavior and high speed, with less maintenance overall.

[mike-lischke]

On the long term (ANTLR5?), I believe that a WASM-only runtime would make sense.

Depends on how we can optimize that to avoid performance degradation. Currently only some targets would profit from it (maybe Python and Go). But without a benchmarking tool for all languages, that's hard to predict.

The tool would generate:

• a lexer and parser in a WASM-able language (Rust?), ultimately compiled to WASM

I would love to see a comparison of Rust and C++, but I don't know Rust enough to write one for that language. Using Rust is certainly the better choice (provided it is on par with C++), because it aligns better with the memory management of languages with GC (practically every other target, but C++). I found these benchmarks (Rust vs C++) which indicate that one can expect around the same performance, but we need to do a comparison in our realm.

• wrappers for these WASM lexer and parser, for each target
• wrappers for context classes, for use by Listener and Visitor implementations
  With that approach, every target would have the same behavior and high speed, with less maintenance overall.

This should probably be taken to a different discussion, as a number of fundamental design decisions need to be made and how the idea aligns with ANTLR4 and Ter's plans.

[mike-lischke]

Looks like there's no further interest in this discussion, so I'm closing it...

[ftomassetti]

I just found it and I am very interested in it. If this discussion stays closed, how can I follow the progress on this?

[mike-lischke]

Hey Federico, it turned out that the WebAssembly variant of the runtime is slower than the JS runtime, so it does not really pay off to follow that road further. Why take all the burden to use wasm, if you can get the same, but with just plain JS/TS code? The embind code is pretty large and there are many details to consider (and not everything is really clear right now, especially regarding memory management), so I decided to put that on hold and improve code that is proven to work well.

[ftomassetti]

Hi Mike, Well, I was hoping to be able to produce a single WASM file (possibly based on WASI) and then use it both in the browser and load it from all languages offering a WASM runtime. Perhaps one can achieve the same compiling JS/TS code? Cheers, Federico

…

On Fri, 15 Sept 2023 at 16:16, Mike Lischke ***@***.***> wrote: Hey Federico, it turned out that the WebAssembly variant of the runtime is slower than the JS runtime, so it does not really pay off to follow that road further. Why take all the burden to use wasm, if you can get the same, but with just plain JS/TS code? The embind code is pretty large and there are many details to consider (and not everything is really clear right now, especially regarding memory management), so I decided to put that on hold and improve code that is proven to work well. — Reply to this email directly, view it on GitHub <#4362 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADLGJTZNV6OFY65PHG44F3X2RPKHANCNFSM6AAAAAA2PY4ERA> . You are receiving this because you commented.Message ID: ***@***.***>

-- Software Architect & Founder at Strumenta (https://strumenta.com) Technical blog at https://tomassetti.me GitHub https://github.com/ftomassetti Twitter @ftomasse linkedin.com/in/federicotomassetti

[mike-lischke]

Oh, yes, that's what Eric suggested too, but I wanted to have a runtime compiled by me only and let users have their parsers + lexers in JS/TS, so they don't need emscripten etc. Generating everything in C++ and compile all that to wasm probably gives even better performance (I linked a repo above where someone did exactly that), but that was not my design goal. For special purposes that might be a way to get even better speed in a JS/TS environment.