Custom Token Patterns too inefficient

[dhlolo]

Using RegExp as token pattern seems to be fast, but when I use custom_payload function:
function matchCustomToken(text, startOffset) { return REG.exec(text.substring(startOffset)); }.
It costs about 20s to solve 500 lines, one and a quarter minutes to solve 1000 lines.

[bd82]

Hello @dhlolo

There are some optimizations that are only performed when no custom tokens are used.
However, these should not cause such a large performance difference.

• chevrotain/packages/chevrotain/src/scan/lexer_public.ts

  Lines 333 to 339 in bd5c2a2

  	if (this.hasCustom) {
  	this.addToken = this.addTokenUsingPush
  	this.handlePayload = this.handlePayloadWithCustom
  	} else {
  	this.addToken = this.addTokenUsingMemberAccess
  	this.handlePayload = this.handlePayloadNoCustom
  	}

The main thing that could affect the performance in this chase is not automatically using the "starting character optimization" when a custom token is used. See the documentation below how to resolve this:

• https://chevrotain.io/docs/guide/performance.html#ensuring-lexer-optimizations

In general even without these optimizations the numbers you posted seems really high.

• Are these numbers of lexer only phase or for both lexing and parsing?
• What are the numbers like if you use a pure regexp?

[bd82]

switching to discussion

[dhlolo]

• It is used not only in lexing but also in parsing.
• With regExp, it just cost like a few sec.

I print the called times of 'pattern' callback, it get obviourly slow after 250+ call times in a file. I seriously doubt that there is a memory leak. U can see the code here and maybe find some wxml files to try.

[NaridaL]

A few comments:

• at a glance, it seems like you're doing too much in the lexing stage, in general, you want to have simple tokens such as "<", "/", or \w+ and use the parser for the different possible combinations.
• try using negated character classes instead of negative lookahead, as I'm not sure that is optimized in the same way; i.e. [^<] instead of (?!<).
• can you use the regex sticky flag to avoid calling substring everytime it tries to parse a token? that does indeed seem like it would have O(n^2)

[bd82]

I print the called times of 'pattern' callback, it get obviourly slow after 250+ call times in a file. I seriously doubt that there is a memory leak. U can see the code here and maybe find some wxml files to try.

Hi again @dhlolo

This kind of potential issue really does need a more focused and minimal and easy to use reproduction to properly explore, e.g:

• A lexer without any custom patterns
• Same Lexer with a single custom pattern replacing one of the Token definitions
• A benchmark comparing these two lexers.
• The benchmark

Generally it requires far too much time otherwise to investigate, particularly considering this is a free time OSS project...
Anyhow @NaridaL provided some tips above.

And I took a peek at https://github.com/wxmlfile/wxml-parser/pull/25/files#diff-5389a63321fd22d5c5d63717ea8ea9aa42da16ea3bf04392b36b6d657613213bR115-R123

Now I can't really tell which version of the code is relevant as there are multiple versions commented out in this PR.
What I can see is:

• There seems to be multiple regular expressions matched in the same custom matcher which generally means more work.
• Try to extract the regexp from the matcher function so it would not get re-created every time the function is entered.
• As @NaridaL mentioned the regular expressions you are using seem quite complex (lookahead , empty negated character class(??) ect...) perhaps they could be simplified...

Cheers.
Shahar

[dhlolo]

I do appreciate for your patience in teaching and replying. Actually I found that I can use another lexer mode to avoid custom pattern callback which made more work. But as DSL become more complicated, I guess that custom pattern can not always be skipped. I must admit that I'm not very skilled with 'chevrotain'. And I wonder if 'chevrotain' has a demo parser implement for Tmlanguage.

[bd82]

And I wonder if 'chevrotain' has a demo parser implement for Tmlanguage.

Are you referring to defining a Chevrotain parser using a TextMate grammar?
If so something similar was discussed here:

• Generating languages for Monarch / Monaco Editor #1761

Note the last comment in the above thread
refers to Langium which may be relevant for your use case.

[dhlolo]

Thanks so much. I saw what you guys were discussing, and I noticed there were the javascript and css definition.
Further is there an html Chevrotain parser?
What I am doing is made a html parser which allows javascript expression in attribute value and content.
Kinda like vue-compiler.

[bd82]

Further is there an html Chevrotain parser?

Unfortunately I am not familiar with one.